ICPC 2025 陕西省赛题解

A

如果对 [1,n] 操作的话答案就是 n+w_c。

然后考虑原来一些已经是 c 的连续段不要涂色，发现答案变化为 w_c-len，贪心即可。

注意特判开头和结尾的连续段。

C

一开始令 x=b，然后不断让 x 除掉 (a,x)，最多进行 \log b 轮。

D

容易发现不论 + 和 \times 的顺序如何，一定都是按照数字从大到小的顺序填。

那么搜索的状态数就减少到 \dbinom{n}{\frac{n}{2}}，可以通过。

E

简单状压 DP 题。记 f_{S,i} 表示已经打出的字符串为 S，最后一个打出的字母为第 i 个字母。

暴力转移即可，时间复杂度 \Theta(2^nn^2)。

F

神秘贪心题。

显然 T 的路径只能是树上从 1 开始的一条链。

我们考虑 dfs 树，然后假设当前 dfs 到的节点为 T 的路径终点，那么我们其实需要做的就是维护一个集合，支持增删元素、查集合内前 k 大的和，使用权值线段树即可。

判断能否以某个点作为 T 的路径终点需要精细实现一下。

G

容易发现答案只有 1,2,3,4 四种。

其中 n=1 时答案为 1，序列两端分别为最大最小值时答案为 2，仅有一端为最大最小值答案为 3，其他情况答案为 4。

I

神秘妙妙题。

容易发现，在 x 上操作一次，则 \forall x - k + 1 \le p \le x, x + 1 \le q \le x + k，有 b_p+b_q 不变。

因此对于一次在 x 上的操作，\forall x - k + 1 \le p \le x，有 b_p+b_{p+k} 不变。

也就是说，不论如何操作，所有下标对 k 取模相同的位置上的和一定不改变。

我们将下标对 k 取模相同的位置上的数内部做前缀和，容易发现在一次操作中 k 组前缀和里各只有一个数增加了 t=b_{x+1}-b_x，这些数在 b 数组上下标为 x - k + 1 \sim x。

令 a_i = a_{i-k} + b_k（若 i<0 则 a_i=0），做差分 d_i = a_i - a_{i-1}，那么一次操作就是令 d_{x-k+1} 加上 b_{x+1}-b_x，d_{x+1} 减去 b_{x+1}-b_x。

由于

所以

即一次操作相当于交换 d_{x+1} 与 d_{x-k+1}。

那么现在问题简化为，给定一个数组，每次操作为交换差分数组的第 x+1 项与第 x-k+1 项，问最后的数组有多少种可能。

将所有下标对 k 取模相同位置的 d 取出来，多重组合数计算方案数，然后根据乘法原理将 k 个多重组合数相乘即可得到答案。

J

简单贪心题。

考虑需要添加的字母从少到多贪心即可，总共需要做四次贪心。

最后剩下来的 k 直接按照四个一组添加成 lose 即可。

K

狗屎题啊。

思路是简单的，考虑假设无私的奶牛里面有 k 个人选择 A，然后计算最大值即可。

注意特判 n,m,x,y 中存在 0 的情况，反正需要很多分类讨论，超级狗屎题。

L

猜个结论，沿着对角线选。

答案 n(n^2+1)。

M

首先容易发现在第 n 个时刻一定只剩下一个连通块，所以我们考虑按时间顺序模拟计算答案。

又可以发现，每个时刻进行的变化其实是，局部极大块的颜色不变，其他的块颜色相反。

那么我们维护局部极大块的集合，合并块使用并查集即可。