2025 牛客暑期多校 Round 2 题解
A
简单 DP。
记 f_i,0/1 表示 [1,i] 以 0/1 结尾的答案，g_i,0/1 表示 [1,i] 以 0/1 结尾的方案数。
容易列出转移，这里不再赘述。时间复杂度 \Theta(n)。
B
题意即判断是否存在 i,j 使得 a_i \oplus a_j < \max(a_i,a_j)。
由抽屉原理可知 n > 60 时一定存在，n \le 60 暴力即可。
C
哎呀这题官方题解怎么是错的有点太坏了。
首先可以发现连通块数量 = 异色边数量 +1。
那么我们记一组随机变量 Z_1,Z_2,\dots 表示子树内所有边的情况，1 表示同色边，0 表示异色边。
那么 \text{E}=sz_u - \sum \text{E}(Z_i)，\text{V}=\text{V}(\sum Z_i)=\text{E}\left(\left(\sum Z_i\right)^2\right)-(\sum \text{E}(Z_i))^2。
\sum \text{E}(Z_i) 是容易求的，考虑计算 \text{E}\left(\left(\sum Z_i\right)^2\right)=\sum_{i,j} \text{E}(Z_iZ_j)：
- i=j，有 \text{E}(Z_iZ_j)=\text{E}(Z_i)；
- i,j 无公共点，则 Z_i,Z_j 独立，有 \text{E}(Z_iZ_j)=\text{E}(Z_i)\text{E}(Z_j)；
- i,j 有公共点，此时 \text{E}(Z_iZ_j) 算得是三点同色的概率。
那么我们全部按照情况 2 考虑，再 -\sum \text{E}^2(Z_i)+\sum \text{E}(Z_i)-\sum_{i,j \in \text{case3}}\text{E}(Z_i)\text{E}(Z_j)+\text{E}(Z_iZ_j) 即可算出答案。
用树状数组维护子树的 \sum \text{E}(Z_i)、\sum \text{E}^2(Z_i)、\sum_{i,j \in \text{case3}}\text{E}(Z_i)\text{E}(Z_j)+\text{E}(Z_iZ_j)，由于点 i 的点度为 \displaystyle\sum_{k=i}^n\frac{1}{k} \sim \Theta(\ln n)，因此计算时暴力枚举与 u 距离不超过 2 的节点即可。
时间复杂度 \Theta((n + q)\ln^2 n)。
D
好题。
我们要求的是 \sum h_i - (V - \sum s_i)\sum d_i，考虑令 S = \sum s_i，我们就变成了物品价值为 h_i - (V - S)d_i 的背包，限制是背包容量为 S。
直接做时间复杂度是 \Theta(nV^2) 的，无法通过，考虑优化。
我们发现当背包容量为 S 时，对于大小为 i 的物品我们最多只会使用 \lfloor\frac{S}{i}\rfloor 个，因此我们可以将体积为 i 的物品按照价值从大到小排序，只取前 \lfloor\frac{S}{i}\rfloor 个。这样当背包容量为 S 时，物品数量是 \Theta(S \ln S) 的。
因此单次背包的时间复杂度优化为 \Theta(n + S^2 \ln S)，总时间复杂度 \Theta(nV + V^3 \ln V)。
E
记得到的完全平方数为 a^2p^2（p 是质数），那么原数即为 a^2p^2-p。
a^2p^2-p \le n \iff a \le \left\lfloor\sqrt{\frac{n+p}{p^2}}\right\rfloor
显然一个数最多只能通过操作得到一个完全平方数，所以答案即为 \sum \left\lfloor\sqrt{ \frac{n+p}{p^2} }\right\rfloor
这大约需要枚举到 10^9 级别的质数，但是太多了，仍然会超时。我们可以接受的是枚举到 10^7 级别的质数。
可以发现，当 p > 10^7 时，有 a \le 100，那么我们枚举 a=1 \sim 100，然后计算满足 a^2p^2-p\le n 的 p 的数量即可解决 p > 10^7 的情况。
使用 Meissel–Lehmer 算法计算质数数量。
F
取最长的一段 0，在其一端操作，贡献为 \max(x-T-1,0)-\max(x-2T,0)。
G（待补）
计算几何不会喵。
H
容易发现我们只会选择一条边操作到底。
那么对于一条边 x \to y，我们一定是走 1 \to x \to y \to n 的路径。
预处理 1 \to i 和 i \to n 的最短路，那么对于一条边 (u,v,t,w)，答案为 dis_{1 \to u} + dis_{v \to n} + t - k \times w。
这是一个关于 k 的一次函数，总共有 m 个一次函数，用李超线段树维护这些一次函数，查询即为查询树上某点的最小值。
I
x,y 仅有 1 个 1 时无解。
J
结论题。
需要观察到当 \sqrt{\ \ } 出现的次数足够多时，操作得到的值与 x 的初值几乎无关。
使用 set 维护 \sqrt{\ \ } 出现的位置，然后用线段树维护连续的一段 kx+b 得到的 k,b 和 sumk, sumb。
然后我们前 \log \epsilon^{-1} 次操作暴力枚举 set 中的位置，将线段树中每一段内容取出来进行模拟，而之后的部分直接套用在线段树上以某个初值为起点的预处理进行赋值与求和即可。
K
暴力题。
用后缀数据结构判断哪些子串 [l,r] 是合法的并打上标记。然后 \Theta(n^2) 暴力将这些串插入 01-Trie，查询时在 Trie 上二分即可。
L
将 (i,a_i) 连边，形成一个图。题意所求即为删去 2 个点剩下的图完美匹配方案数。
显然这个图由若干个环组成，首先若奇环数量 >2 显然答案为 0。
若奇环数量 =2，那么删掉的两个点一定分别来自两个奇环，断开的奇环贡献为 1，偶环贡献为 2。
若不存在奇环，那么两个点一定同属于一个偶环，根据每个偶环的长度计算贡献即可。
M
简单数位 DP 题，难点在代码实现。
首先 a=b \le c 的情况可以简单推式子得到。
对于 a < b < c 和 a < c < b 的情况，显然答案是 a < b < c 的两倍。
记 f[n][a == b][b == c][c == (s + 1)][a ^ b ^ c == (l + 1)][a + b ? c] 表示做到二进制下第 n 位的答案，最后一维是用于判断加法进位的。
转移比较简单，注意实现细节即可。