省流
跳过 C2 直接开 D，实现太烂调试过多没时间再写 C2，表现分 \(1938\) 勉强稳住紫线。
10.19
内含剧透，请vp后再来。
不是题解！！！！！！！
赛时
A 题给定一个 \(01\) 串，要求保护一些 \(1\)，使所有 \(1\) 要么被保护，要么在 \(i - k + 1\) 到 \(i\) 之间有被保护的 \(1\)。转换一下，就是记录有多少个 \(1\) 前面 \(k\) 个中没有 \(1\)。由于数据范围较小，直接模拟即可。我做这道题目时陷入误区，一眼看题后，认为应该贪心的去保护，虽然结果推出来是正确的但相比直接完整理解题目花的时间更多一些。\(4min\) 通过。
B 题给定一个序列，要求偶数位置大于相邻的位置。有两种修改操作，把一个值变为自己以及前缀的最大值，把一个值减一。问给定的序列至少要执行多少次减一操作才能满足条件。容易想到第一个操作次数不计，且只可能增大一个数。那么我们对所有操作 \(2\) 执行操作一后再对不满足的奇数位减一即可。延展一下，如果这题的操作是加一，那么就应该是先加一后再往后替换。\(8min\) 通过。
C1 是给了一个数组，以及有一个操作，对某个数加一。问最少执行多少次操作让数组中某两个数 gcd 不为 \(1\)。容易想到如果有两个偶数那么一定是满足条件的，所以答案最多为 \(2\)。接下来考虑答案为 \(1\) 或者 \(0\) 的情况。一开始想的是通过计算 lcm 判断原始数组中有没有 gcd 不为 \(0\) 的情况，但会溢出。然后想到可以直接枚举质因子，那么只要出现相同的就是 gcd 不为 \(0\)，答案为 \(0\)。那么答案为 \(1\) 的情况也呼之欲出，直接把每一个数加一的因子也枚举了，因为最大答案为 \(2\) 所以不用枚举更多，那么两个枚举的数组互相去找就可以了。我第一发只考虑了后面的数加一，没有把所有数的加一的因子都存起来，第二发才在 \(31min\) 通过。
C2 是把统计操作次数换成了每个操作都有花费，求最后花费最少。鉴于我 C1 花了比预期长的时间，而且 D 过的人数不比 C2 少特别多，于是在当时过题人数大约差距三倍时大胆的先开了 D。
D 题给了一棵树，一只猫在点 \(1\) 而需要设计一个路线让猫一定能到达点 \(n\)。路线中有两种操作，第一是让猫随机移动一格，第二是摧毁一个点，要求路线不能超过 \(3n\)，摧毁点时不能摧毁猫，以及第二个操作不能连续摧毁。这个题目到手时很像一道题目，CF2133E。借助这个题的想法，这道题的解法应该也是把起点到终点变成一个链，那么考虑该怎么删别的点就行。显然删一个点的操作是 \(3\) 次，且需要一定不能删掉猫，那么我们只要确定猫和要删掉的点不在同一行就行，然后每次都让猫先移动两下，再删掉这一行的下一个点就行。然后由于不能把猫堵死在错误的子树上，所以从高度高的节点删。删完所有不在目标道路上的点后，用同样的方法从起点一个一个删到终点就可以把猫逼到终点了。思维出的非常快，然而我实现的时候记录猫的行数的细节出了特别多问题导致时间主要花在调试，\(96min\) 一发通过。
此时回去看 C2，想到类似 C1 的想法设计一个上限，然后记录所有的值在上限里的变化值的质因子，以及每个质因子的最小花费就应该是可以的，但没时间了，这场比赛就结束了。
赛后
接着看 C2，按照原来的想法，可以知道最大花费就是最便宜的两个，因为总可以构成两个偶数。接下来的操作低于最便宜的两个有以下两种情况：只有一个变化了一次，最便宜的变化了多次。除了最便宜的都不可能变化多次，因为如果某个非最便宜的变化两次，那么一定比最便宜的两个都变化一次贵。这两种情况中第一个和 C1 操作一样，第二个则是只存后面的初始的所有质因子，然后对最便宜的求出要加几个，然后加最少的就可以了。
2025年10月20日