1.CF1860D
link && submission
发现自己并不会处理纯纯的 dp 甚至自己根本不会dp！
定义 dp_{i,j,k} 状态表示前 i 个字符有 j 个 0， 01 的数量减去 10 的数量为 k 。转移比较显然了，答案是 这道题算是猫树板子题了，所以这道题的重点是讲猫树！
猫树本质上是预处理，可以在 O(nlogn) 的时间复杂度里预处理出一个序列所有 [l,r] 的信息，要求维护的信息有结合律。查询是 O(1) 的。考虑建一棵线段树，那么任意一对 [l,r] 区间在线段树上最后一次出现一定是在线段树上叶节点
所以异或相同的两种情况可以合在一个节点上，然后每个节点放两种状态进来分别的答案就好了。
7.CF1771F
link && submission
这题也是个好活。你看到奇数想到什么？没错，异或！但是直接用原数异或会有很多奇奇怪怪的错误，所以给每个值一个hash值然后在主席树上二分值域就好了。
8.AGC024E
link. && submission
神仙题！不知道是不是！但是我是常例的不会 dp ！
换一下顺序，考虑怎么由 \(a_i\) 生成 \(a_{i+1}\)，那么新插入的数一定要大于它后面的数。 假设现在我们生成到了第 \(i\) 个序列，用了前面 \(j\) 个数，然后现在插入的依然是 \(j\)。因为必须大于所以插入的位置是有限的，所以我们还需要限制一个 \(k\) 表示当前还可以插入的位置。dp 状态可以表示出来了 \(dp_{i,j,k}\) 表示生成到第 i 个序列，用了前 j 个数，有 k 个数小于 \(j\) 。这种定义下发现可以插入的位置是 k+1 个因为你可以在末尾补一个。
考虑转移。如果当前不插入 j 的话，那么相当于有一个本来可以插的位置但是你不插了，所以就是 dp[i][j][k-1]+=dp[i][j][k]。值得注意的是如果 k=0 那么说明当前这个数已经考虑完了所以转移是 dp[i][j+1][i]+=dp[i][j][k]；如果插入 j ，那么一共有 k+1 个位置可以插，而且注意到插入后下一个数能插入的位置的数量并不会改变，所以转移是 dp[i+1][j][k] = dp[i][j[k]*(k+1)。
答案就是 dp[n][m][0]。
9.AGC040E
link && submission
妙！妙！
如果只有操作一，你发现答案就是 \(a_i>a_j\) 的数量。现在有两种操作了。那么考虑每一个位置的数由操作一贡献 \(b_i\) 和操作二贡献 \(c_i\) 。设置状态 dp[i][j] 表示第 i 个数，\(b_i=j\) 时的最小代价。显然的转移是：$$dp_{i,j}=\min dp_{i-1,k} +[j<k] +[j<k+a_i-a_{i-1}]$$ 是 \(\mathrm{O(nV^2)}\) 的，V 是值域。
这道题有两个 nb 的地方，第一个就是一开始的分拆转换，第二个就是优化 dp。\(V^2\) ——> \(logV\) 是什么概念？！第一个性质是 \(\mathrm{dp[i]}\) 这个序列是递减的，这个很显然；第二个性质比较隐藏，考虑用更新 \(\mathrm{dp[i][a_i]}\) 的最优点更新 \(\mathrm{dp[i][0]}\)，那么真正的 \(\mathrm{dp[i][0]}\) 肯定不大于这个，所以就满足 \(\mathrm{dp[i][0]\le dp[i][a_i]}+2\)。
你发现整个序列 \(\mathrm{dp[i]}\) 的值被分成了三段。所以我们只需要对这三段 dp 就好了。找到每一段的位置可以固定左端点二分右端点。
10.ARC156D
link&&submission
好题。充分利用了异或的性质。
因为异或，所以一旦一个数出现两次就没了，所以如果所构造的序列 p 不是回文的，那么把这个 p 反过来就能让 \(\sum a_{p_i}\) 再出现一次，异或了就没了。所以能对答案产生贡献的序列一定是回文的。那么你直接每次截一半的贡献*2，再特判一下奇偶就行了。\(\mathrm{dp[i][j]}\) 表示长度为 i 的序列求和加上 j 的所有序列的异或和 ，这么定义的原因是奇数的回文中间可能会多出一个 j 来。
这做法才真正意义上对得起它所谓的 D 题难度，因为没什么深奥的理论了。