主要思路
首先，不考虑原问题，只考虑最优策略，显然是当前能匹配的串越长越好。所以可以考虑二分答案，算当前拼接次数下能拼出来的最长的串，再将其与 \(n\) 进行比较。
Continue reading →首先，不考虑原问题，只考虑最优策略，显然是当前能匹配的串越长越好。所以可以考虑二分答案，算当前拼接次数下能拼出来的最长的串，再将其与 \(n\) 进行比较。
Continue reading →这个题还蛮有意思。
首先有个暴力，\(l\) 在 \(10^7\) 内可以直接 two-pointers；如果在 \(10^7\) 以上，那么发现 \(f(r) – f(l) \leq 1\)。那么我们可以考虑枚举这个连续段的长 \(L = x + y\)，其中 \(x\) 是 \(i\) 个 \(0\) 的部分，而 \(y\) 是 \(i + 1\) 个 \(0\) 的部分。有个等式：\(x \times i + y \times (i + 1) = (x + y)i + y = Li + y = S\)。所以枚举 \(L\) 的时候，如果 \(S \bmod L \equiv 0\)，那么说明 \(y = 0\)，你就把 \(10^i\) 内的左端点个数算出来（其实就是多减一个 \(L – 1\)）。如果 \(S \bmod L \neq 0\)，那么说明 \(x, y\) 确定了，那么就直接 ++ 即可。
Continue reading →刚看这题我人都是懵的…仔细看了看能大概想到，定一个根然后做 DP 得到方案，然后对于相同形态的子树进行方案分配即可。（但是不会写）
具体而言，转换成有根树的方法就是用重心来做根（如果有两个重心的话，就加一个虚根），并且每次 DFS 完之后用 Hash 值排序，然后进行分组转移。
转移的时候，可以给每一种情况进行标号，然后用前缀的组合意义来做转移即可。具体：\( dp[i] = \sum_{uniqueType \in subtree} {dp[uniqueType] + |subtree| – 1 \choose |subtree|} \)。
如果加了虚点，那就判一下就好了。
Continue reading →如果本身就不是回文串，那么答案就是 \(1\)；如果本身是的话，考虑找一个分割点使得左右都不是，那么答案就是 \(2\)；如果还是没找到，那么就是无解了，因为最后串要么就是个单纯串或者是个删完一次之后变成单纯串的东西。
主要还是需要注意设计状态。
我们称 \((-1, x)\) 为单对，称 \((-1, -1)\) 为双对。我们可以试着从大到小填数字，这样就可以避免取 \(\min\) 的问题了。考虑 \(dp[i][j][k]\) 为选到第 \(i\) 个数字，然后有 \(j\) 个待处理、\(k\) 个单对待处理。转移的话，可以试着进行讨论。如果这个数字是某个单对之一，那么一种方式是啥都不干，还有一种是尝试进行匹配，\(j -= 1\)。如果不是单对之一，那么要么匹配、要么晾着。
最后乘上一个双对个数的阶乘，使其有序。
这题好神仙啊。
首先介绍一个暴力的套路（虽然跟正解没关系，但我觉得碰上很多比赛的时候会用上）：我们设置 \(f[i][j]\) 当前为前 \(i\) 个数中第 \(j\) 小的贡献，那么有
\[ f[i][j] = \begin{cases} \sum_{k = 1}^{i – 1} f[i – 1][k] (s_{i – 1} = <) \\ \sum_{k = i}^{j} f[i – 1][k] (s_{i – 1} = >) \end{cases} \]