我到底做了些什么题啊v1

ARC209

A

思考一下，一定是先把头尾匹配的括号取完，接着就是类似 \(l, l+1\) 匹配的括号，优先拿短的一边，剩下就不合法了。根据这种方式博弈一下就行了。

B

显然只能贪心，先分成众数多于一半和少于一半两种情况，后者直接每次去剩余数量最多的然后两次不交替地取即可。

前者，注意到肯定先均分更优，但这样会出现诸如 xxxxyxxxxyxxxx 的情况，于是我们在均分的基础上尽可能地将两个相邻的偶数段变成奇数段就对了。

D

还是分讨，如果 \(A_i\) 确定 \(A_{A_i}\) 确定那没招，如果 \(A_i = -1\) 那么考虑延后赋值。如果 \(A_i\) 确定但是 \(A_{A_i}\) 不确定，此时如果 \(A_i > i\) 那显然直接把 \(A_{A_i} = 1\)，否则考虑对于 \(A_{A_i}\) 要不选第一个 \(1\) 的位置，要不然选 \(i\) 之后的一个 \(-1\)。

代码细节比较多啊，调了很久。

C

整除分块也是分块。

考虑 dp，显然 \(a, b\) 中只需要记录一维，令 \(f_{i, j}\) 为当前到第 \(i\) 位，取了 \(j\)。会发现 \(f_i\) 内的极差不超过 \(1\)，且我们显然只需要记录更大的那个值 \(x\) 所对应的最小 \(j\) 和最大 \(j\)，不妨记作 \(L, R\)。分类讨论转移：

• \(P_i = 1\)。若 \(R \times X \geq S_i\)，\(x' \leftarrow x + 1\)，\(R' \leftarrow X\)，\(L' \leftarrow \lceil \frac{S_i}{R} \rceil\)；否则 \(x' \leftarrow x\)，\(R' \leftarrow X\)，\(L' \leftarrow 1\)。
• \(P_i = -1\)。若 \(L \geq S_i\)，\(x' \leftarrow x - 1\)，\(R' \leftarrow X\)，\(L' \leftarrow 1\)；否则 \(x' \leftarrow x\)，\(R' \leftarrow \min(X, \lfloor \frac{S_i - 1}{L} \rfloor)\)，\(L' \leftarrow 1\)。

会发现前者一定有 \(R = X\)，后者一定有 \(L = 1\)，而另一个值的取值显然只有 \(\sqrt{S}\) 种，于是所有的状态不超过 \(n \sqrt S\) 种。

我们从 \(1 \sim n\) 中途碰到询问就加进来，如果两个询问 \(L, R\) 相同那就用并查集合并起来即可。

ARC208

A

做的时候发现这个东西类似 Nim 游戏所以往异或方向考虑，大胆猜测判断条件是异或和等于或和，然后对了！

其实非常有道理啊，因为这个相当于 Nim 游戏每一位都要保证至少一个 \(1\)，所以把每一位的 \(1\) 剔除掉判断异或值是否为 \(0\)，和上述结论相同。

B

二分一下 \(a_n\) 然后从后往前每次减去 \(\min(\lfloor \frac{a_{i + 1} - 1}{2} \rfloor, k')\) 即可判断构造。

C

转化成 \(n \oplus C = kn +X\)，分讨 \(k = 0, 1, \geq 2\)。

\(k = 0\) 是容易的。

\(k = 1\) 时两边都有 \(n\) 不好做，考虑将 \(n \oplus C\) 转化成 \(n + c - 2(n \operatorname{and} C) = n + X\)，这样就好做了。

\(k \geq 2\) 的情况能够证明如果前两种都不满足则这种一定不满足。

ARC207

B

套路题啊，考虑如何区分走一步的点和走两步的点，直接使用二分图即可。将 \(1 \sim \lfloor \frac{n}{2} \rfloor\) 视作左部点，其余视为右部点，连边是简单的。

C

最终序列的每个数对应原始序列的一段。

令 \(f_i\) 为最多分为几段，\(g_i\) 为最小的最后一位数，\(s_j\) 为 \(j \sim i\) 的异或和。

一个 trick 是暴力更新 \(s\) 的复杂度是 \(O(n\log V)\)，因为实际上每个数最多被更新 \(\log V\) 遍，我们每次从右往左更新到不能更新就直接退出复杂度是对的。

然后考虑 DP 部分，显然有 \(f_i = \underset{s_{j + 1} \geq g_j}{\max}\{f_j\} + 1\)。由于 \(f\) 单调递增，\(s\) 单调递减，所以对于 \(g_i\) 来说一定是从最靠右的满足 \(s_{j + 1} \geq g_j\) 更新。 我们在更新 \(s\) 的过程中维护这个位置即可。

A

ABC435

G

考虑将相邻两个点连一条边，要求就是相邻的两条边不能同时选。

令 \(f_{i, j}\) 为 \(i \to i + 1\) 染 \(j\) 的方案，有 \(f_{i, j} \leftarrow S_{i - 2} - f_{i - 2, j}\)，\(f_{i, 0} \leftarrow S_{i - 1}\)。

这个东西，你考虑对于奇偶开两颗线段树，就可以直接线段树优化了。

我赛时怎么没看出来，愤怒。

萌萌题

P2566

唯一难点在于知道一个数如果被矩形包围则他右侧的直线有奇数条，根据这个进行状压即可。

CF53E

肯定要状压叶子，然后由于这是一个经典的不断往生成树中加边的形式我们不妨再状压已经加入的结点。有 \(f_{S, T}\) 表示已经加入 \(S\) 中的点，\(T\) 中的点为叶子，显然 \(T \subseteq S\)。转移简单，考虑去重，钦定一下加叶子的顺序即可。

P5369

考虑以最大前缀和的地方划分为两半，要求前一半的后缀和 \(\geq 0\)，后一半的前缀和 \(< 0\)。可以直接状压转移。

P2481

好牛的题，套路就是将递增的数列转化成 \(9\) 个后缀 \(111111\cdots\) 相加，先预处理出 \(g_i\) 表示模 \(P\) 余 \(i\) 的后缀有多少个，然后令 \(f_{i, j, k}\) 为做到 模 \(P\) 余 \(i\) 的后缀，已经选了 \(j\) 个，和模 \(P\) 余 \(k\) 的方案数。转移系数是个组合数，按照定义算一下即可。

P6190

最短路题 dp 的经典形式，令 \(f_{i, j, k}\) 为 \(i\) 到 \(j\)，用了不超过 \(k\) 次。当 \(k = 0\) 时就是 floyd，\(k = 1\) 可以特殊处理，否则我们有 \(f_{i, j, k} = \min{f_{i, u, k - 1} + f_{v, j, 1}}\)，显然满足结合律，可以矩阵优化。

P3647

考虑一定是三个东西连线的形式，有父亲两个儿子和一个点与父亲与儿子两种形式，一起处理不好做。但我们会发现第一种情况可以通过换根转化为第二种情况。

于是令 \(f_{u, 0/1}\) 表示点 \(u\) 是否为中间点，转移、换根比较常规。

P7706

找不到啥很好的性质，考虑直接用线段树维护。需要维护子树 \(a_i - b_j(j > i)\) 和 \(a_i - b_j(j < i)\) 的最值，以及 \(\max a_i\) 和 \(\min b_i\)，合并简单。

P5069

想想这个过程是什么，先找出最大值 \(a_x\)，那么 \(a_{x - 1}\) 和 \(a_{x + 1}\) 都会被杀掉。而 \(a_x\) 一定要一直做 \(a_x\) 遍才行。于是相当于相邻两个只能选一个。

考虑线段树直接维护答案，发现需要考虑左右两个端点是否选择，分成四种情况维护标记即可，十分难写，一坨打分。

P9130

还是考虑直接硬维护。

我们当前区间的答案需要考虑上一个区间给到的草，于是我们记录区间有多少天有草吃，能给后面的天数多少草。

维护区间答案的时候考虑记录左儿子对右儿子的贡献，比较难处理，考虑再写一个东西查询这个。那么相当于要查询 \(x\) 个草给到区间 \([l, r]\) 的答案。

对于区间 \([l, r]\)，如果填满左儿子后还有剩那就继续递归右儿子，否则递归左儿子（此时右儿子的贡献就是左儿子溢出的对右儿子的贡献，这个我们已经知道了）。于是你会发现这个东西是只会单侧递归的，于是复杂度就是 \(O(n\log^2n)\)。

P4314

历史最大值问题考虑矩阵维护，令向量 \([a, b, 0]\) 表示目前最大值和历史最大值，转移矩阵随便推一下。

P8868

要求 \(\sum_{L \leq l \leq r \leq R} \underset{l \leq i \leq r}{\max}{a_i}\underset{l \leq i \leq r}{\max}{b_i}\)，考虑离线下来 \(r\) 从 \(1 \to n\) 处理询问，则我们需要维护 \(l\) 的历史和。

先考虑 \(r\) 对与最大值的影响，可以通过单调栈得到影响的区间将区间赋值转化为区间加。

那么我们不妨维护矩阵 \([a, b, ab, c, len]\)，其中 \(c\) 为历史和，\(ab\) 为乘积和。那么转移矩阵是好构造的。

注意我们维护转移矩阵的时候某些原本为 \(0\) 的东西可能会改变，一共需要维护 \(9\) 个值。