省流
A 挂了,写了一个小时头痛欲裂,2t寄了,还好是 vp。
9.22
内含剧透,请vp后再来。
不是题解!!!!!!!
赛前
这天白天基本什么没做,就补了几道水题,于是晚上 vp 一把试试。
赛时
开局读 A,完全理解错了题意,题目要求一段长度为 n 的段涂色要求对称,实际上是要求两侧颜色相同,而我误以为是要两侧恰好相反,浪费很多时间不提。十五分钟交了三发挂掉,于是去开 B 题。
B 题要求把给定 n 的数加上任意个 k,使这些数的 gcd 大于 1,但最多加上 k 个 k。一种简单的想法是给 x 加上 x 个 k,那么 x 就变成 x + x * k = x * (k + 1),所有的数都有 k + 1 这个公因子,但 x 可能大于 k 就挂掉了。但我们已经找到了一个公因子, 发现用 k + 1 对 x 取模之后每次加 k 就能让余数减少 1,那么只要加余数次就可以变成 k + 1 的倍数,而余数不会大于等于 k + 1, 故可以通过。
接着看 C, 要求给定一个序列,序列中偶数位置要大于等于两侧数的和,每次可以减少一个 1,问至少要减多少个 1.单独考虑第一个偶数位置,发现只有减它后面的那个数才可能对后面有利,所以每次只需要优先减后面的数就可以了。
此时时间过了四十分钟,我调了一会看错题目的 A 且并无进展,在一个小时左右看了一眼 D,感觉有点生理意义上的头痛就下班了,如果是实战又要掉大分。
赛后
早上起来重新看 A 没什么发现,看完题解后发现读错题目。那么只需要关心两种颜色是否有贡献以及有贡献的和 n 是否在模 2 的情况下同余即可。
D 题给我们一棵树,然后要求每次选三个点,把其中第二个点除了第 1,3 个点外所有别的边都删掉然后加给第三个点,最后变成一条链,要求操作次数最少且给出第一步操作。手玩一下发现获得直径之后可以向直径两头去走,是一种比较好的情况,然后进一步发现如果是把直径的一段加到中间的枝桠上可以更好的解决,那么求出直径即可。整体难度肯定不值得 2200 分。
2025年9月23日