CF2183（Hello 2026）全解

· · 个人记录

CF2183（Hello 2026）

A. Binary Array Game

自评：橙。

题意

给定长度为 n 的 01 串，Alice 和 Bob 轮流操作，Alice 先手，每次选中一段区间 [l,r](l<r) 并将 a_l,\dots,a_r 替换为一个 1-\displaystyle\min_{i=l}^r\{a_i\}，直至不能操作，即只剩一个数为止。如果剩的是 1 则 Bob 获胜，否则 Alice 获胜。求最优情况下谁会获胜。

数据范围：多测，t\le 100,3\le n\le 100。

做法

首先如果是全 1 串 Alice 可以直接操作整个串获胜。

否则注意到如果 Alice 想赢 Bob 必须拿到一个长度为 2 的全 1 串，证明：

而这显然要求原串开头结尾最多只有一个是 0。

综上，判断原串首尾相加是否大于等于 1 即可。单组实际计算的复杂度是 O(1)，考虑读入则为 O(n)。

B. Yet Another MEX Problem

自评：橙。

题意

给定长度为 n 的数组 a 和整数 k。每次操作可以选择一个长度为 k 的子区间满足该区间的 \text{mex} 是所有长度为 k 的子区间里最大的，然后从该区间里任意删除一个数，你需要进行操作直到不能操作（即 a 的长度小于 k）为止。求最终剩下数的 \text{mex} 的最大值。

数据范围：多测，t\le 10^4,\sum n\le 2\times 10^5,0\le a_i\le n。

做法

注意到最优的情况是最后留下 0 至 k-2 的每一个整数。而在这种情况下，一个长度为 k 的区间必然出现额外的元素，删去即可。

所以最终答案是原序列 \text{mex} 与 k-1 的较小值。原序列的 \text{mex} 开桶计算即可，单组复杂度 O(n)。

C. War Strategy

自评：黄。

一眼丁真，鉴定为出题人玩 Genrals 玩的。

有朝一日我 C 能 WA 两发了。

题意

给定 n,m,k，考虑一个在数轴上进行的游戏：初始在点 k 处有 1 个士兵，每天你可以选择一个有士兵的点中任意数量（可以是 0）的士兵并使其向左或向右移动一格且仍需在 [1,n] 内，然后点 k 处会增加一个士兵。

若游戏进行 m 天，求在游戏完成后士兵数量不少于 0 的点数的最大值。

数据范围：多测，t\le 10^4,k\le n\le 10^5,m\le 10^9。

做法

首先中间空格的操作显然是闲的，所以最终有士兵的点必然是包含 k 的一段区间。

于是 k 往左和 k 往右的两部分分别一次性铺完（例如 [3,0,0,0]\to[0+3,1,1,1]）必然是最优的，因为否则多个士兵你要走多次。

也就是最终操作应该是等 - 往一边铺 - 等（如果需要）- 往另一边铺。

因为在能充分利用的前提下，第一次铺的过程中效率是最高的，所以为了缩减第二次等的时长我们应该尽量让左右两边铺的长度相等。由于关于中心对称的两个位置 k 和 n-k+1 是等价的，这里令计算时所用的 k 取上两者的较小值。

你发现上一句话我有一个前提条件是能充分利用。明显如果先铺长度比较短的一边则铺这一边的过程是可以充分利用的，而先铺哪边是没有区别的，所以按先铺长度较短的一边考虑是容易计算的。于是根据上述“尽量让两边铺的长度相等”的思路，这里分出几种情况：

答案与 n 取最小值即可。复杂度单组 O(1)。

D. Tree Coloring

自评：绿~下位蓝。

题意

给定 n 个点的以 1 号点为根的树，初始所有点都是白色，每次操作可以选一个白点构成的独立集，使得其中不存在两个点是同一深度的，然后将这个独立集内的点染黑，直至整棵树变黑。求最小操作次数。D2 另外要求给出构造方案。

数据范围：多测，t\le 10^4,\sum n\le 2\times10^5。

做法

考虑什么时候两层之间选点会冲突。

显然只有当上面一层中只有一个非叶子时，选这个点必然导致下面一层不能选点，从而导致下面一层浪费一次。

所以统计每层非叶子个数，如果上一层只有一个非叶子则这层可以视为需要 cnt+1（cnt 为本层内点数）次；否则需要 cnt 次。各层取最大值即可。

构造看上去比较容易但还是有点细节的。经过若干次翻车之后我找到一种还可以的方法，就是按 BFS 序一层层放，放一个点的时候优先往它父亲那一层中下一个非叶子所在的操作里放，如果那个操作有点了就往后面放（即不含上一层中非叶子的操作）。这样能确保每个非叶子下必然有一个其他非叶子的儿子，从而确保操作次数是对的。

注：如果 checker 显示方案有没染色的点，请检查你的策略是否可能导致某两个本互不干扰的层，由于某个点下一层除其自己的儿子外都被用了而导致多一次操作。

E. LCM is Legendary Counting Master

自评：中位蓝~上位蓝。

题意

给定长度为 n、值域 [0,m] 的数组 a，你需要为每个原来为 0 的位置赋一个 [1,m] 的值，使得 a 严格单增，且满足

\sum_{i=1}^n\dfrac{1}{\text{lcm}(a_i,a_{(i\bmod n)+1})}\ge 1

求合法的方案数。

数据范围：多测，t\le 1000,2\le n\le m\le 3000,\sum m\le 3000。

做法

由 \gcd(x,y)\text{lcm}(x,y)=xy 有 \dfrac{1}{\text{lcm}(a_i,a_i+1)}=\dfrac{\gcd(a_i,a_{i+1})}{a_ia_{i+1}}。

当 a_i<a_{i+1} 时，有 \gcd(a_i,a_{i+1}])\le a_{i+1}-a{i}，即 \dfrac{1}{\text{lcm}(a_i,a_i+1)}=\dfrac{\gcd(a_i,a_{i+1})}{a_ia_{i+1}}\le\dfrac{a_i+a_{i+1}}{a_ia_{i+1}}。

故原式 \le\sum_{i=1}^n\dfrac{a_i+a_{(i\bmod n)+1}}{a_ia_{(i\bmod n)+1}}=\frac{1}{2}(\frac{1}{a_1}-\frac{1}{a_n})。

但是这个东西好像不是很好看。根据从小初各种题攒下来的经验我们是希望它最后有一个 \frac{1}{a_n} 来把前面减掉的部分加上的。

于是我们考虑将 \frac{a_n-a_1}{a_1a_n} 换成 \frac{a_1}{a_1a_n} 是等价的。即原式 \le\frac{1}{a_1}，当且仅当 \forall i\in[1,n)\gcd(a_i,a_{i+1})=a_{i+1}-a_i 时取等号。

然后只有 a_1=1 时这个玩意能取到 1。故这两个条件要同时成立。而满足第一个条件的数对只有 O(m\ln m) 个，故直接 DP 就是 O(nm\ln m) 的。

F. Jumping Man

自评：上位蓝~下位紫。

题意

给定一棵 n 个点、以 1 为根的树，每个点上有一个字母。考虑其中的一棵子树：从子树中任取一个点为起点，从该点出发，在该点的子树中任取一个点并跳到这个点，直到到达某个叶子，这样经过的若干个点上的字母会形成一个字符串。对于每个点为根的子树，对于该子树中每个可能通过上述操作获得的字符串，求出可以得到该串的路径数量的平方，然后对这些字符串的答案求和，对 998244353 取模。

数据范围：多测，t,\sum n\le 5000。

做法

这个题提醒了我：这种形式比较复杂的式子（例如本题要求平方和）应该试着化开或者表达其意义。

本题选择了后者。平方和即选两条路线能产生相同字符串的方案数。我们设 f_{i,j} 表示两个路线分别到达了 i,j 并满足上述条件的方案数。

显然只有当 p,q 分别在 i,j 的子树中时 f_{p,q} 才能转移至 f_{i,j}。根据 DFS 序的子树连续性，如果将各点按 DFS 序编号形成二维数组，则转移的范围必然在一个矩形里。前缀和预处理后 DP 一下即可。

G. Snake Instructions

自评：下位黑~中位黑。

题意

给定数轴上 n 条蛇的位置，均在 [1,4n] 内，每条蛇有一个未知的速度 s_i\in\{0,1,2\}。你可以进行不超过 3 次操作，每次给定一个由 L 和 R 组成的、长度不超过 4n 的字符串。所有蛇会按此串进行移动，如果当前字符为 L 则第 i 条蛇左移 s_i 格，反之右移 s_i 格，如果两蛇相撞（即使不在整点处），则速度较大的蛇死去。每次操作完后你可以获得所有剩余蛇的所在位置。操作之间是独立的。求所有蛇的速度，或报告无解。

数据范围：多测，t\le 1000,\sum n\le 10^5。

做法

这个题的一个点在于不要鼠目寸光，想着一次操作确定 xxx。题中询问串长度为 4n 的限制在把你往这个沟里带。

注意到 L+LR 两次操作减一下可以获得所有往左一步不会死的蛇的速度。此时剩下下面几种未能确定的情况：

然后对于 12 式和 0_2 的情况就直接确定了，于是只剩下 01 和 02 式的。

刚才往左走了一次所以现在考虑往右走一次。然后发现这么干的话 0x0 式的是无解的，因为中间没法确定是 1 还是 2，仔细想想好像也没啥办法，所以这种情况直接定下来无解。然后剩下的情况就容易确定了。

复杂度 O(n)。

H. Minimise Cost

自评：中位黑。

题意

定义一个序列的代价为其元素和乘其长度。

给定长度为 n 的序列 a，要求将其划分成恰好 k 个非空子序列，求各子序列代价之和的最小值。

数据范围：多测，t\le 10^4,k\le n\le 2\times 10^5,\sum n\le 2\times 10^5,|a_i|\le 10^9。

做法

官解巨长其实主要是在证明，而且中间其实有点绕弯。

子序列是不好做的，故考虑观察性质。

我们发现排序后实际上原序列会被分成若干个长度单调不增的子段，这个容易感性理解。

于是我们有暴力 DP：设 dp_{i,j} 表示前 i 个数分了 j 段的最小代价。转移直接枚举上一个分段的位置：

dp_{i,j}=\min_{k=1}^{i-1}\{dp_{k,j-1}+(s_i-s_k)(i-k)\}

其中 s 是前缀和数组。

看到这个形式不难想到的定理是：

定理 形如 dp_{i,j}=\displaystyle\min_{k=1}^{i-1}\{dp_{k,j-1}+w(i,k)\} 的转移方程中，若价值函数 w(i,k) 具有凸性，则答案 dp_{i,j} 也具有凸性。

证明没记错的话蓝书和 OI-Wiki 上都有。当然我不会证。

故我们需要 w(a,c)+w(b,d)\le w(a,d)+w(b,c)。

将 w(x,y)=(s_x-s_y)(x-y) 代入上式后展开并移项得 (b-a)(s_d-s_c)+(d-c)(s_b-s_a)\ge 0。不难注意到当 a_i>0 时不等式成立。

考虑 a_i<0 的情况。显然我们希望负数的段数越少越好、正数的段数越多越好，故分为两种情况：

这个思考很牛的一点在于，由于第一种情况中正数丢到负数段中可能反而产生更小的贡献，所以如果只是简单地把负数的转移点跳过去，四边形不等式仍不成立；但由于一个正数 x 被分入正数段中时其贡献至少为 x，故我们把丢到负数段中时贡献小于 x 的数跳过，诶，四边形不等式就成立了。

上述过程可以 wqs 二分套二分队列完成，在 P6246 中亦有记载。由于我也只会对着各种资料打打板子，所以这里不展开讲了。

于是这玩意就做完了，复杂度 O(n\log n\log C)。

I. Pairs Flipping

自评：？位黑。

题意

给定长度为 n 的 01 串 s。你需要进行 \lfloor\frac{n}{2}\rfloor 次操作，第 i 次操作可以选除了最后 i 个外的任意位置 x，并将 s_x 与 s_{x+i} 取反；也可以什么都不干（记作 x=0）。要求构造每次操作的 x，使得最终 s 剩下不超过 15/7（I1/I2 题）个 1。

数据范围：多测，t\le 10^5,\sum n\le 2\times 10^6。

做法

实在懒得写了，见官方题解。毕竟我写的话只能把 I2 展开讲，要不然和官方题解也没啥区别[笑哭]。