200

D

考虑鸽巢原理：枚举 \(201\) 种序列，必然存在两种方案之和模 \(200\) 同余。当序列长度为 \(8\) 时有 \(2^8=256\) 种子序列，足以覆盖全部情况。直接 dfs，时间复杂度 \(2^{\min(n,8)}\)。

E

拜谢 Kenma。
容易想到枚举 \(i+j+k\)，接着再确定 \(i,j,k\)。
考虑容斥。设 \(i+j+k=sum\)，方案数为 \(f_{sum}\)，若忽略 \(i,j,k\le n\) 的限制，则 \(f_{sum}=\dbinom{sum-1}{2}\)。此时对限制容斥一下：
\[f_{sum}=\binom{sum-1}{2}-3\cdot\binom{sum-n-1}{2}+3\cdot\binom{sum-2n-1}{2}-\binom{sum-3n-1}{2}\] 确定 \(i+j+k\) 后枚举 \(i\)，计算相同 \(i\) 下合法三元组数量即可。

201

D

比较基础的博弈 DP。

E

看到树上路径异或和首先转化为点到根的路径异或和，因为设 \(dis(u,v)\) 表示 \(u,v\) 路径的异或和，有 \(dis(u,v)=dis(1,u)\oplus dis(1,v)\)。则现在问题转化为：有数组 \(dis\)，求其中元素两两异或的结果之和。考虑拆位，设当前考虑到第 \(i\) 位，所有 \(dis\) 中第 \(i\) 位为 \(1\) 的有 \(cnt\) 个，这一位的贡献即为 \(cnt\times (n-cnt)\times 2^i\)。时间复杂度 \(O(n\log V)\)。

202

E

比较套路的题。一些带 \(\log\) 的方法比较高级，这里给出一个 Kenma 的朴素 \(O(n)\) 做法。
只需要开桶，进入子树前减去原本的贡献即可。

212

E

挺不错的题。考虑 DP，设 \(f_{i,j}\) 表示前 \(i\) 天，最终停留在 \(j\) 点的方案数。答案即为 \(f_{k,0}\)，边界 \(f_{0,1}=1\)。转移的话可以考虑容斥：设 \(sum=\sum_j f_{i-1,j}\)，则有
\[f_{i,u}=sum-f_{i-1,u}-\sum_{v\in e_u}f_{i-1,v}\]

214

E

一种比较简单的做法。贪心，首先以 \(r​\) 为第一关键字，\(l​\) 为第二关键字升序排序，使用并查集检查每个 \(l​\) 向后第一个可用的位置。设其为 \(p​\)，若 \(p>r​\) 则无解。值域问题使用 std::map 动态开点即可。

F

简单计数 DP。设 \(f_{i,j}\) 表示考虑前 \(i\) 个字符，最后一个字符为 \(j\) 的不同新字符串数量。则有转移：

\[f_{i,j}=\begin{cases}f_{i-1,j}&j\ne s_i\\1+\sum_{k} f_{i-2,k}&j=s_i\end{cases}​\]

215

F

看到最大化最小值容易想到二分答案。设枚举的答案是 \(d\)，check 考虑双指针，首先将点按照 \(x\) 排序，则可以框出一段左右界之差小于 \(d\) 的区域，只需在两端取点即可保证 \(|x_i-x_j|\ge d\)，那么，在两边取最大最小的 \(y_i,y_j\)，相减后检查与 \(d\) 的关系即可。预处理前后缀 \(\min,\max\) 可以做到时间复杂度 \(O(n\log V)\)。

308

G

好厉害的题。性质：对于三个非负整数 \(x,y,z\)，若 \(x<y<z\)，有 \(\min(x\oplus y,y\oplus z)<x\oplus z\)。
则答案必然是目前集合中所有数排序后所有相邻元素异或的最小值，这样我们只需维护线性的可能值，开两个 multiset，一个维护当前集合，一个维护异或值。时间复杂度 \(O(n\log n)\)。
还有一种线段树分治+01 Trie 的做法。

311

G

枚举最小值，那么就可以用单调栈 \(O(nm)\) 地找到符合条件的最大子矩形和，总体时间复杂度 \(O(nmV)\)。

359

E

设第 \(i​\) 个水箱的答案为 \(f_i​\)。
考虑分为两种水箱：

  • 是当前最高的，答案为 \(i\times h_i+1​\)；

  • 不是当前最高的，设上一个比它高的位置是 \(j\)，答案为 \(f_j+(i-j)\times h_i\)。

单调栈维护即可。

423

F

二项式反演板子。
设 \(g_i\) 表示至少 \(i\) 种蝉爆发的年份数，容易求出：
\[g_i=\sum_{|S|=i}\left\lfloor\frac{y}{\operatorname{lcm}_{j\in S}(a_j)}\right\rfloor\] 直接反演，得到答案：
\[ans=f_m=\sum_{i=m}^n(-1)^{i-m}\binom{i}{m}g_i\] 时间复杂度 \(O(n\log V2^n)\)。