2026 XCPC 杂题选解

XCPC 2026 WEEK 14

C - Quadratic Jumps

tag(s): math, brute force

CodeForces - 2231F

首先由 Fermat Polygonal Number Theorem，答案不会超过 4。

考虑什么时候答案为 1，直接检测 \(b - a\) 是不是完全平方数即可。

什么时候答案为 2,直接预处理所有 \(a^2 + b^2\) 和 \(a^2 - b^2\) 即可。后者需要记录使得 \(x = a^2 - b^2\) 的最小 \(a\) 和最小 \(b\)。

什么时候答案为 3？直接枚举第一步，剩下的就是判断答案为 2。

否则，答案为 4。时间复杂度 \(O(n + q\sqrt n)\)。感觉应该有很多复杂度同样正确的做法。

D - Bracket Groups

CodeForces - 2144F

tag(s): ACAM, dp

首先判断 \(-1\)。那就是某个字符串为 ()。不可能有合法的括号序没有 () 作为子串。

除了这种情况一定有解吗？答案是肯定的。我们可以构造出这样两个基本没有相同子串的括号序列：

()()()()()()()()()
((((((((()))))))))

所有括号序列，都只会出现在上面两者其一（除了 ()）。

所以答案不会超过 2。问题变成检验答案是否为 1。这个问题不就是“是否存在一个字符串，不包含任意给定字符串”，经典的上 ACAM dp。

XCPC2026 WEEK 13

D - N-MEX (Counting Version)

CodeForces - 2207E2

首先考虑判断是否合法。由 mex 的定义显然 \(n \ge a[i] \ge n - i\)。其次，从前缀 \(i\) 到前缀 \(i + 1\)，最多只能增加一个数，所以 \(a[i] \le a[i - 1]\)。可以设 \(a[0] = n\)。

这样一定合法吗？可以考虑构造：

1. \(a[i] = a[i - 1]\)，则 \(b[i]\) 一定要造成贡献，只能填一个 \(< a[i]\) 且从未出现在 \(a\) 内的数。
2. \(a[i] < a[i - 1]\)，则 \(b[i]\) 一定不能造成贡献，只能填一个 \(> a[i]\) 或者之前填过的数。

对于第二类，显然可以填 \(1\,145\,141\,919\,810\)。对于第一类好像不一定能填。不过证明一下，是可以填的。因为我们知道如果一共有 \(k\) 种 \(a[i]\)，那就有 \(n - k\) 个第一类，加起来刚好 \(n\) 个数。也就是事实上第一类可以填，甚至非常紧。

如果要计数，我们也是同一个道理，对于第一类，后面一共会 ban 掉 \((n - i)\) 种数字（\(a[j]~(j > i)\) 不能选，并且 \(a[j] = a[j - 1]\) 会用掉一种数），所以一共有 \(a[i] - (n - i)\) 个数可以选；对于第二类，一共有 \(i\) 个数可以选。

E

1. if ones >= zeros, best solution is to transform the whole string.
2. it should take <= 3 operations to reach target state (ones >= zeros)

• if max prefix/suffix sum >= 1, then we can do it in 1 operation
• state: 0...[..]...0
  • let s be the max sum of a substring (s >= 1)
  • if s >= 2, takes 2 operations
  • if s == 1, takes 3 operations

special case: 010 takes 2 operations

XCPC2026 WEEK12 kaito solution

C - Cowpatibility G

tag(s): 容斥, bitset

洛谷 - P5123

有两个解法，一个是容斥至少有一种相同=钦定一个相同-钦定两个相同+钦定三个相同-钦定四个相同+钦定五个相同。

这个比较没意思，我们考虑另一个解法，可以解决一头奶牛喜欢任意数量颜色的问题。

使用 bitset 暴力统计。bitset 暴力统计 bitset[i][j] 表示 \(i\) 和 \(j\) 这两头奶牛有相同颜色（\(j\) 有一个颜色和 \(i\) 的一个颜色相同）。对于每一个颜色，枚举这个颜色对应的所有奶牛，在 bitset 上置位，然后把 bitset 或起来即可。

时间复杂度 \(O(MN/\omega)\)，其中 \(M = 5N\) 表示总共的颜色数量。差不多 2e8，3s 可以通过。

问题在于空间被卡了。需要 \(N^2/\omega \approx 298~\text{MiB}\)，题目只给了 \(256~\text{MiB}\)。

没事，可以拆成两次做。第一次只做 bitset[i'][j] 其中 \(i'\in[0, n/2)\)，第二次再做 \(i'\in[n/2, n)\) 的部分。只需要 \(149~\text{MiB}\)。

D - Ghd

CodeForces - 364D

tag(s): 随机化

我们注意，在数组中随机一个数，答案有高达 50% 的概率是他的一个因子。

这启发我们随机一个数，然后检测其所有因子是否符合条件，差不多随机 \(20\) 次，有 \(10^{-6}\) 的概率失败。（会 TLE 就随机少一点，我怀疑随机 \(10\) 次就行）

但是一个数的因子太多了，直接一个一个数还是 T 飞。

但是可以直接数 \(\gcd(a_i, x)\)，然后把这个东西的贡献加到其因子上。时间复杂度：

\[O\left(S(N\log V + d^2 + \sqrt V)\right) \]

其中 \(S\) 是随机次数，\(N\log V\) 是对所有 \(i\) 求 \(\gcd(a_i, x)\) 的复杂度，\(d^2\) 是把贡献从大因子加到小因子，\(\sqrt V\) 是质因数分解。瓶颈还是 \(\gcd\) 太慢了。

2026 XCPC TW11 kaito

C - Springboards G

洛谷 - P6007

非常简单，只需要决定 dp 顺序。比如以 x 从小到大为第一关键字，y 从小到大为第二关键字，之后就是单点修改，前缀查询。

D - Trucks and Cities

CodeForces - 1101F

设 \(f[l][r][k]\) 表示把区间 \([l, r]\) 分成 \(k\) 段后，段的最大值的最小值。区间 dp 有转移

\[f[l][r][k] = \min_p\{\max(f[l][p][k-1], a[r]-a[p])\} \]

而且还可以发现 \(f\) 的最佳点是单调的。首先这很明显，其次发现是符合四边形不等式的。所以维护最佳点 \(\text{opt}[i][j-1]\le \text{opt}[i][j]\le\text{opt}[i+1][j]\)，就可以保证枚举最佳点是 \(O(n^3)\) 的。叫什么 Knuth's optimization.

XCPC 2026 W10

Next DP Contest 2026M

tag(s): sos dp

本质上是子集和问题，然后每个子集有特殊的权值（\(10^k\)）。

可以考虑 SOS DP，设 \(f[S][i]\) 表示集合 \(S\) 倒数 \(i\) 维的答案，然后记 \(L[S][i]\) 为对应字符串的长度。如果 \(S\) 的 \(i+1\)-th bit 是 1，有：

\[f[S][i + 1] = f[S \oplus 2^{i}][i] \times 10^{L[S][i]} + f[S][i] \]

Next DP Contest 2026N

tag(s): dp, knapsack

这个是有一篇论文的。题解见群里。

XCPC 2026 WEEK8

C - Avoid Division

AtCoder - abc453_f

TAG(s): constructive, greedy

• 必要条件：树有 \(L\) 个叶子。若某种颜色的可用次数 \(C_i \ge 2\)，则它可以同时出现在一条边的两侧。对于任何叶子，如果它被涂上了 \(C_i = 1\) 的颜色，切断它唯一的邻边后，另一侧就不可能有该颜色，因此所有叶子都必须用 \(C_i \ge 2\) 的颜色覆盖。于是 \(\sum_{C_i \ge 2} C_i \ge L\) 是必要条件。

• 充分性：当 \(N \ge 3\) 且上述条件成立时，问题总有解。构造步骤如下：

1. 选取一个非叶子的顶点 \(X\)，使得删除 \(X\) 后每一个连通分量包含的叶子个数不超过 \(\lfloor L/2 \rfloor\)。这是可行的，求法类似点分治求重心。当然 \(n = 2\) 是找不到的，需要特判。
2. 将原树的叶子按删除 \(X\) 后所在的连通分量分组。
3. 类似哈基米构造法，可以构造出一个相邻两个元素在不同连通分量的序列。
4. 处理所有 \(C_i \ge 2\) 的颜色，将序列中一段长度为 \(C_i\) 的序列染为颜色 \(i\)。如果序列剩余长度不足 2，即为 1，将 \(X\) 和这个点都染成颜色 \(i\)。
5. 所有剩余顶点用任意还有剩余次数的颜色涂满即可。

E - Spices

AtCoder - abc236_f

TAG(s): greedy, linear basis

要能用 XOR 凑出 \(1 \sim 2^N-1\) 的所有整数，等价于选出的集合在异或意义下张成了整个 \(\mathbb{F}_2^N\)，也就是集合包含一组异或线性基。将所有香料按价格从小到大排序。贪心加入线性基即可。

proof. 若当前香料不能被现有集合表示，则在任何最优解中，一定可以用当前香料替换掉某个价格不低于它的元素，不会使总价增加。

XCPC 2026 TW6 kaito

C - Interval Game

CodeForces - 2217F

TAG(s): dp, brute force, game theory

不难发现是四个 Nim 游戏 \(l_1 - 1\)，\(x_1-r_1\)，\(l_2-1\)，\(x_2-r_2\)。

\(l_1-1 \oplus x_1-r_1\) 可以凑出来的是 \([0, x_1)\)，所以问题变成找到最小的 \(y\in [0, x_1)\) 使得 \(f[y]\) 最小。\(f\) 定义如下：

for (int i = 0; i < x2; ++i)for (int j = 0; i + j < x2; ++j)f[i ^ j] += 1;

考虑快速求 \(f\)。我们知道 \(i+j = i\oplus j + (i \& j)\times 2\)，考虑不枚举 \(i\) 和 \(j\) 而是枚举 \(i\oplus j\) 和 \(i\& j\)，设其分别为 \(X\) 和 \(K\)。有：

• \(K \& X = 0\)
• \(X + 2K < x_2\)
• 同时，满足这样的 \(X\) 和 \(K\) 的 \((i, j)\) 对有 \(2^{\operatorname{popcount}(X)}\) 个。

所以问题变成求 \(f[X] = 2^{\operatorname{popcount}(X)} \times \#\{ K \mid K \&X = 0, K < (x_2-X)/2\}\)

考虑怎么计数后面那个东西，可以数位 dp。

总时间复杂度 \(O(x\log x)\)。

D - Manhattan Cafe

AtCoder - abc265_f

TAG(s): dp

数据范围比较小，考虑 dp。设 \(f[i][s][t]\) 表示填了 \(i\) 维坐标，到 \(p\) 距离是 \(s\) 到 \(q\) 距离是 \(t\)。

直接转移好像是 \(O(nD^3)\) 的。但是可以发现在线段上选点有三种，设 \(|p_i-q_i| = d\)，具体有：

1. \(f[i][s][t] \to f[i+1][s+k][t+d-k]\)
2. \(f[i][s][t] \to f[i+1][s+d+k][t+k]\)
3. \(f[i][s][t]\to f[i+1][s+k][t+d+k]\)

其实是一堆斜率为 \(\pm1\) 的斜线转移，可以对斜线做前缀和，优化到 \(O(nD^2)\)。滚动一下防爆空间。

XCPC 2026 TW5 - KAITO

D - A Simple GCD Problem (Hard Version)

CodeForces - 2210C2

TAGS: number theory

首先区间限制可以简化为相邻两个的限制。记 \(\gcd(a_i, a_{i+1}) = d_i\)。则 \(\operatorname{lcm}(d_i, d_{i-1})\mid a'_i\)。

直接令 \(a'_i = \operatorname{lcm}(d_i, d_{i-1})\) 可以得到一个合法解。但不是最优解：显然有 \(a'_i \mid a_i\)，如果 \(a_i = a'_i\) 则少了一个操作次数。

因为限制只和相邻两项相关，可以考虑 dp，设 \(f(i, k)\) 表示前 \(i\) 个数已经满足条件，并且 \(a'_i = \operatorname {lcm}(d_i, d_{i-1}) * k\) 的最多操作次数。

注意一下这里 \(k\) 的取值，为了多操作一次，我们应该让其乘上前面或后面没有的质数。所以随便找出前 30 个质数作为 \(k\) 的可能取值，dp 即可。

E - Learning Binary Search

CodeForces - 2211F

TAG(s): combinatorics

计算序列的贡献比较困难，考虑计算数字的贡献。

即

\[\sum_a \sum_x f(a, x, 1, n) = \sum_x \sum_a f(a, x, 1, n) \]

对于一个数字 \(x\)，\(f(a, x, 1, n)\) 事实上和 \(a\) 序列的具体值无关，我们只关心 \(a\) 序列的值与 \(x\) 的大小关系。所以可以把序列分成三段，第一段 \(<x\)，中间 \(=x\)，第三段 \(>x\)。具体的，设 \([l, r]\) 这一段恰好都是 \(x\)。这样的区间的数量是 \(\binom{l - 1 + x - 2}{l - 1} \binom{n - r + m - x - 1}{n - r}\)。\(x=1\) 和 \(x=m\) 在看完下文做法并理解后，特判一下就好了。

这时候 \(f(a, x, 1, n)\) 会在递归到 l <= mid <= r 的时候返回。具体的，把递归的 mid 画成树状结构，定义 \(r_i\) 为 \(i\) 作为 mid 时，递归的深度，则 \(f(a, x, 1, n)\) 的递归深度为 \(\min_{l\le i\le r} r_i\)。答案可以写成

\[\begin{aligned} \sum_x\sum_{l}\sum_r f(a, x, 1, n) &= \sum_x\sum_l\sum_r\left(\min_{l\le i\le r}r_i\right) \binom{l - 1 + x - 2}{l - 1} \binom{n - r + m - x - 1}{n - r}\\ &=\sum_l\sum_r\min r_i\sum_x\binom{l - 1 + x - 2}{l - 1} \binom{n - r + m - x - 1}{n - r}\\ &=\sum_l\sum_r(\min r_i)\binom{n + m - (r - l) - 3}{n - (r - l)} \end{aligned} \]

按照 \(\min r_i\) 分治，满足条件的 \((l, r)\) 其实应该是 \(L_i\le l \le i, i\le r\le R_i\)。可以继续化简：

\[\begin{aligned} \sum_l\sum_r(\min r_i)\binom{n + m - (r - l) - 3}{n - (r - l)} &= \sum_{L_i\le l\le i} \sum_{i\le r\le R_i} r_i \binom{n + m - r + l - 3}{m - 3}\\ &= r_i\sum_{L_i\le l\le i} \binom{n+m+l-i-3}{m-2}-\binom{n+m+l-4-R_i}{m-2}\\ &= r_i\left[\left(\binom{n+m-1}{m-1}-\binom{n+m+L_i-i-2}{m-1}\right)-\left(\binom{n+m+i-R_i-2}{m-1}-\binom{n+m+L_i-3-R_i}{m-1}\right)\right] \end{aligned} \]

真是丑陋啊。

XCPC 2026 TW4 - KAITO

C - Count Power of 2

AtCoder - arc216_c

TAG(s): HASHING, DIVIDE & CONQUER

首先需要一个能快速判定一个区间是否合法的方法. 会发现值域非常大, 但是数字没几种(最多 \(n^2\) 种). 可以考虑哈希. 取一个大质数 \(P\), 我们认为一个区间 \([l, r]\) 合法当 \(\sum_{i=l}^r 2^{a_i} \equiv 2^k\pmod P\) for some \(k\).

下一步, 不难感受到答案不会有很多. 比如一个所有数都是 \(0\) 的情况, 也只有 \(O(n\log n)\) 个答案.

假设一个区间 \([l,r]\) 中, \(\max a_i = M\), 那么这个区间的和不会超过 \(2^{M+\log N}\).

这启发我们不去枚举区间然后判断是否合法. instead, 先枚举区间的 \(\max\), 设其为 \(a_m\). 利用分治, 求出所有 \(L\le l \le m, m\le r\le R\) 的合法区间数, 递归解决 \([L, m-1]\) 和 \([m+1, R]\) 的情况.

在统计跨过 \(a_m\) 的区间的时候, 首先枚举区间和(\(2^{a_m}, 2^{a_m+1}, \ldots, 2^{a_m + \log_2(R-L+1)}\)). 之后再枚举左或右端点中少的那个.

最后分析分治的复杂度, 约为 \(f(n) = f(m) + f(n - m) + \min(m, n - m)\log n\), 主定理后是 \(O(n\log^2 n)\). 最后还需要乘上用来查询某个数值是哪个前缀和的数据结构的复杂度.

D - A Trivial String Problem

CodeForces - 2209E

TAG(s): border, greedy

首先 dp 的转移只能是 border. 这题要最多划分, 所以自然想到选择最短的 border. 接下来考虑证明最小 border 划分是最优的. 如果最优解划分有一个不是最小 border, 则可以把这个分裂, 矛盾.

XCPC 2026 TW3

B - Subsequences Galore

CodeForces - 1620G

首先考虑怎么求 \(f([s_1, \ldots, s_k])\)，“至少一个包含”其实不好直接求。注意到求“所有都包含”是好求的，也就是交是好求的。所以考虑容斥原理。

那对于一个子序列 \(T\)（看作子集），答案应该为：

\[f(T) = \sum_{S\subseteq T} (-1)^{|S|+1} g(S) \]

其中 \(g(S)\) 是原问题的“所有都包含”版本。右边可以把系数融入到 \(g(S)\)，那 \(f(T)\) 就是 \(g\) 的 \(T\) 子集和了。可以高维前缀和做，时间复杂度 \(O(n2^n)\)。

C - Arena

CodeForces - 1606E

第一轮所有人都会掉 \(n-1\) 滴血，只有第一轮是好考虑的。只能做一步转移的时候，不妨想一下能不能递归解决问题。直接令 \(f(n, x)\) 表示答案，则 \((n, x)\) 会转移到 \((m, x - (n - 1))\) 这个状态。所以可以写出式子：

\[f(n, x) = \sum_{m=0}^n \binom n m (n-1)^m f(n - m, x - (n - 1)) \]

边界这里不赘述。

D - Locked Out

CodeForces - 2161D

题目的限制不好考虑，一个全称量词还有两个变量。

考虑转化一下限制。记 \(L_i\) 为 \(i\) 这个数字在答案数组里面的最左出现位置，\(R_i\) 则为最右。那题目的限制可以转化为 \(L_i > R_{i+1}\)。

这个限制条件有一个很天然的顺序，就是 \(R_{i+1}\) 只和 \(L_i\) 有关，启发我们从小到大考虑每个数字。把原数组按照数值排序，以下标逆序为第二关键字，就可以从左到右 dp。\(f_i\) 表示钦定保留排序后数组里面的第 \(i\) 个数，最多能保留几个数。转移不赘述。

E - Bessla Motors G

洛谷 - P10193

考虑魔改 dijk，记录每个点的前 K 短路（相同起点需要去重）。这样每个点只会松弛 10 次，复杂度约为 \(O(\alpha km\log n)\)，\(\alpha\) 取决于维护前 K 短路的方法。

F - Sum of Fractions

CodeForces - 2204F

首先考虑一个区间内，怎么做操作最优。

大概能想到，你只会对 \(b_i\) 最小的那个数操作。因为改成对 \(\min b_i\) 复刻不在其上的操作，答案一定会更大。

下一步考虑怎么操作，会发现 1 是一个分界。假设最后你操作成 \(x/y\) 了，如果 \(x < y\)，根据糖水不等式，回退对 \(y\) 的操作，改成对 \(x\) 操作，结果会变成 \((x+1)/(y+1)\)，更大了。一直回退最后 \(y' = b\)。反之 \(x>y\) 就应该改为 \((x-1)/(y-1)\)。

所以如果 \(k < b\)，就应该改成 \((1+k)/b\)，反之改成 \(1+k-(b-1)\)。

所以答案可以写成 \(f([l\ldots r], k) = f(\min b, k) + g(l, r)\)，其他部分其实是和 \(k\) 无关的常数，推式子计算一下就好了。对于 \(\min b\)，可以考虑计算 \(b\) 的贡献，单调栈跑一下 L=previous_less 和 R=next_less，那所有子区间 \([l, r](L_i<l\le i, i\le r < R_i)\) 的 \(\min b\) 都是 \(b_i\) 了。乘一下系数即可。

G - Codeforces Heuristic Contest 001

CodeForces - 2195H

首先人为构造可以放两个直角三角形，占满 \(2\times 3\) 的格点。对于这题，考虑递归构造。

想从 \(n\) 递归到 \(n-1\) 需要构造 \(3\times 3n\) 的矩形和 \(3\times 3(n-1)\) 的矩形，不可能完全填充这是很劣的。

但是发现从 \(n\) 递归到 \(n-2\) 是简单的，用 \(2\times3\) 去填充 \(6\times 3(n-2)\) 和 \(6\times 3n\) 显然可以随便就填满。

所以显然 \(n\) 为偶数是可以填满的。操蛋的是 \(n=3\) 也是可以填满的，只能手模。

H - FTL

CodeForces - 1743E

\(h\) 这一维比较小，启发使用背包。由于最优操作要么是交替发射激光，要么是同时发射激光，并且每次发射激光一定掉血，所以这些操作最多只有 \(h\) 种。\(O(h^2)\) 背包。

XCPC TW2

2206B Subtree Removal Game

很有意思的是，发现不好分析，取决于谁先手，一棵树可能有两个答案。

有一个做法是：二分答案。

将 \(\le m\) 的视作 N 类节点，\(>m\) 的视为 P 类节点。

对于孩子全是叶子的节点，如果 N 节点数量大于 P 节点数量，不论先后手，答案就是 N，反之就是 P。如果相等，那就是谁先手谁赢。把 N 节点看成 \(w = 1\)，P 节点看成 \(w=-1\)，根据 \(\sum w\) 的正负性可以分为前面三类

对于更一般的情况，设当前节点的孩子有一些是 N，有一些是 P，有一些是 0。先手肯定尽可能去删 P 子树，后手尽可能去删 N 子树（这两个都等价于操作 0 子树），所以答案和上一段落一样。

2206I Growth Factor

首先预处理，\(a_i\) 肯定可以取后缀 \(\min\)，变成一个不降序列。

其次不难想到 dp \(f[i][v]\) 表示填完前 \(i\) 个位置，并且 \(b_i = v\) 的方案数。

接下来问题是这个转移复杂度太高，不可做。

接下来非常神秘。如果 \(a_i\) 都是 \(+\infty\)，那么把答案写在一张表格里，会发现 \(f[i][v]\) 关于 \(i\) 是一个多项式（或者说多项式增长），并且次数在 \(1, 2, 4, 8\) 有明显的加一，换句话说，\(f_v(i)\) 是一个关于 \(i\) 的不超过 \(\log_2 v\) 次的多项式。

下一步的问题是，知道是多项式之后又要怎么推导？首先要考虑如何记录多项式系数。如果 \(f_v(i) = \sum_j a_j i^j\)，推导时需要利用 \(f_v(i) = \sum_{u\mid v} f_u(i-1)\)，左边有 \(f_v(i)\)，右边有 \(f_v(i - 1)\)，减起来麻烦得要死，需要展开二项式系数。考虑让 \(f_v(i-1)\) 用 \(f_u(i - 1)\) 表示，最后可以得到 \(f_v(i) = \sum_{j = 1}^{i-1} \sum_{u\mid v} f_u(j)\)，即 \(f_v(i) = \sum_{u\mid v} \sum_{j=1}^{i-1} f_u(j)\)。

我们需要一个好求前缀和的多项式表示法，考虑牛顿级数。

一个 \(d\) 次多项式 \(f(n)\) 可以表达为组合数的形式，有：

\[f(n) = \sum_{i=0}^d c_i\binom{n}{i} \]

这个多项式的前缀和比较好求，有：

\[\begin{aligned} \sum_{k=0}^n f(k) &= \sum_{k=0}^n\sum_{i=0}^d c_i\binom{k}{i}\\ &= \sum_{i=0}^dc_i\sum_{k=0}^n\binom{k}{i}\\ &= \sum_{i=0}^dc_i\binom{n+1}{i+1} \end{aligned} \]

可以发现多项式系数的数值没变，只需要平移一下（或者记个偏移量）。

把 \(f_v(i)\) 写成 \(f_v(i) = \sum_{d=0}^{\lfloor\log_2 v\rfloor} c_v(d)\binom{i}{d}\)，就知道 \(f_v(i) = \sum_{u\mid v} \sum_{d=0}^{\lfloor\log_2 u\rfloor} c_u(d)\binom{i}{d+1}\)，可以得到 \(c_v(d)\) 的递推式。对于 \(a_i\) 的限制，就需要把 \(\sum_{u\mid v}\) 的 \(u\) 范围修改一下。因为这是最外层的枚举所以其实很简单。时间复杂度约为 \(O(n\log^2 a_i)\)。