2025 牛客暑期多校 Round 4 题解
A（待补）
B
记 r_{i,j} 表示在 (i,j) 时最远能到达哪一列，这个显然可以 \Theta(nm) 预处理。
然后搜索判断会不会出现 r_{x,y} \le y + k 且 r_{x,y} \neq m 即可。
C（待补）
D
好题。
先构造出如下矩阵：
显然该矩阵的行列式为 n，但是题目要求的是 0/1 矩阵，我们考虑令 a_{n-1}=a_{n-2}=-\lfloor\frac{n}{2}\rfloor，那么我们可以通过把第 n 行加上第 n-1,n-2 行的方式，将 n 变为 0/1。
现在问题变为如何把 a_{n-1},a_{n-2} 变为 0/1，我们令 a_{n-3}=a_{n-4}=\lceil\frac{-a_{n-1}}{2}\rceil，此时我们把第 n-1,n-2 行都加上第 n-3,n-4 行，则可以使 a_{n-1},a_{n-2} 变为 0/1。
依此类推，我们不断修改 a_i 的值后进行行加法变化，就可以得到一个仅有 0/1 构成的矩阵了。
E
还算比较有意思的题。
由 ab \ge a + b\ (a,b>1) 得，若路径上 >1 的数的和超过了 24，那么一定无解，在此之外，若路径上的 1 的数量能够补足和与 24 之间的差距，则一定有解。
形式化来说，将路径上 >1 的数之和记为 \text{sum}，路径上 1 的数量记为 \text{cnt}，则：
- 若 \text{sum} > 24，无解；
- 若 \text{sum} \le 24 且 \text{sum} + \text{cnt} \ge 24，有解。
那么现在只需考虑 \text{sum} + \text{cnt} < 24 的情况，显然此时路径长度 <24，暴力跳父亲取出路径上的所有数，DP 即可。
对于修改，用树状数组维护 \text{sum} 和 \text{cnt} 即可。
时间复杂度 \Theta(q(\log n + 23 \times 24))，实际上 23 \times 24 远远跑不满，可以通过。
F
假设原序列中 a_{x_1},a_{x_2},\dots,a_{x_k} 被交换至前 k 位，且 x_i 单调递增。
那么有交换次数 t = \displaystyle\sum_{i=1}^k x_i-i。
所以答案为 \displaystyle\sum_{i=1}^ka_{x_i}-c\left(\displaystyle\sum_{i=1}^k x_i-i\right)=\displaystyle\sum_{i=1}^ka_{x_i}-cx_i+\dfrac{ck(k+1)}{2}。
把 a_i-ci 排序取前 k 大即可。
G
如果能确定唯一的括号序列，那么最后一个 ( 与第一个 ) 一定不能交换。
形式化的描述是若最后一个 ( 为 i，第一个 ) 为 j，则有 \displaystyle\min_{i \le k < j}\left\{\text{sum}_k\right\} \le 1。
那么我们枚举 i，二分 + ST 表求出最小的 j，然后 \Theta(1) 计算贡献即可。
时间复杂度 \Theta(|S| \log |S|)。
H（待补）
I
首先根据墙将地图分为若干个连通块，显然每个连通块中的箱子和目标数量要相同。
然后对每个箱子，bfs 找到离他最近的目标的路径，若路径上存在其他箱子 a_1,a_2,\dots,a_k，则将 a_k 移动至目标，a_{k-1} 移动至 a_k，……，最后将该箱子移动至 a_1 即可。
时间复杂度 \Theta(nmk)，k 为箱子数量。
J（待补）
K
好题，学到生日悖论怎么用了。
首先由生日悖论可知，我们可以在 \Theta(\sqrt{M}) 的时间里找出两个与 M 同余的子集。
但是本题中 \sqrt{M}=10^{9}，仍然无法通过。
我们考虑将 n 分为 \sqrt{n} 个部分，每个部分用 \Theta\left(\sqrt[4]{M}\right) 的时间求出两个与 \sqrt{M} 同余的子集，计算他们和的差值。
然后我们将得到的 \sqrt{n} 差值除以 \sqrt{M}，现在对于 \sqrt{n} 个数差值，我们再套用上述方法用 \Theta\left(\sqrt[4]{M}\right) 的时间求出两个与 \sqrt{M} 同余的子集，即可得到最终答案。
时间复杂度 \Theta\left(\sqrt{N}\sqrt[4]{M}\right)。
L
假设 x 要先后与 a_l,a_{l+1},\dots,a_r 挑战，可以推导出答案为
那么容易发现，当 r-l+1 \ge 32 时，x=0 与 x=10^9 对答案的影响仅有 1。
那么我们可以先暴力做长度为 32 的一段，然后判断最终的答案是否需要 +1。
如何判断呢？我们注意到 \lceil\frac{x+a_i+1}{2}\rceil 与 \lceil\frac{x+1+a_i+1}{2}\rceil 最多也只相差 1，并且只有在 x+a_i+1 是偶数的时候相差 1。
那么要使 [l+33,r] 这一段最后的答案要 +1，当且仅当 [l+33,r] 中的每一位都满足 x+a_i+1 是偶数，这显然可以预处理出来。
因此我们只需暴力做长度为 32 的部分，剩余部分预处理即可。
时间复杂度 \Theta(q \cdot 32)。