2026 XCPC 杂题选解

()()()()()()()()() ((((((((()))))))))所有括号序列都只会出现在上面两者其一除了()。所以答案不会超过 2。问题变成检验答案是否为 1。这个问题不就是“是否存在一个字符串不包含任意给定字符串”经典的上 ACAM dp。XCPC2026 WEEK 13D - N-MEX (Counting Version)CodeForces - 2207E2首先考虑判断是否合法。由 mex 的定义显然 n≥a[i]≥n−i≥[]≥−。其次从前缀 i 到前缀 i11最多只能增加一个数所以 a[i]≤a[i−1][]≤[−1]。可以设 a[0]n[0]。这样一定合法吗可以考虑构造a[i]a[i−1][][−1]则 b[i][] 一定要造成贡献只能填一个 a[i][] 且从未出现在 a 内的数。a[i]a[i−1][][−1]则 b[i][] 一定不能造成贡献只能填一个 a[i][] 或者之前填过的数。对于第二类显然可以填 11451419198101145141919810。对于第一类好像不一定能填。不过证明一下是可以填的。因为我们知道如果一共有 k 种 a[i][]那就有 n−k− 个第一类加起来刚好 n 个数。也就是事实上第一类可以填甚至非常紧。如果要计数我们也是同一个道理对于第一类后面一共会 ban 掉 (n−i)(−) 种数字a[j] (ji)[] () 不能选并且 a[j]a[j−1][][−1] 会用掉一种数所以一共有 a[i]−(n−i)[]−(−) 个数可以选对于第二类一共有 i 个数可以选。Eif ones zeros, best solution is to transform the whole string.it should take 3 operations to reach target state (ones zeros)if max prefix/suffix sum 1, then we can do it in 1 operationstate:0...[..]...0let s be the max sum of a substring (s 1)if s 2, takes 2 operationsif s 1, takes 3 operationsspecial case:010takes 2 operationsXCPC2026 WEEK12 kaito solutionC - Cowpatibility Gtag(s): 容斥, bitset洛谷 - P5123有两个解法一个是容斥至少有一种相同钦定一个相同-钦定两个相同钦定三个相同-钦定四个相同钦定五个相同。这个比较没意思我们考虑另一个解法可以解决一头奶牛喜欢任意数量颜色的问题。使用 bitset 暴力统计。bitset 暴力统计bitset[i][j]表示 i 和 j 这两头奶牛有相同颜色j 有一个颜色和 i 的一个颜色相同。对于每一个颜色枚举这个颜色对应的所有奶牛在 bitset 上置位然后把 bitset 或起来即可。时间复杂度 O(MN/ω)(/)其中 M5N5 表示总共的颜色数量。差不多 2e83s 可以通过。问题在于空间被卡了。需要 N2/ω≈298 MiB2/≈298 MiB题目只给了 256 MiB256 MiB。没事可以拆成两次做。第一次只做bitset[i][j]其中 i′∈[0,n/2)′∈[0,/2)第二次再做 i′∈[n/2,n)′∈[/2,) 的部分。只需要 149 MiB149 MiB。D - GhdCodeForces - 364Dtag(s): 随机化我们注意在数组中随机一个数答案有高达 50% 的概率是他的一个因子。这启发我们随机一个数然后检测其所有因子是否符合条件差不多随机 2020 次有 10−610−6 的概率失败。会 TLE 就随机少一点我怀疑随机 1010 次就行但是一个数的因子太多了直接一个一个数还是 T 飞。但是可以直接数 gcd(ai,x)gcd(,)然后把这个东西的贡献加到其因子上。时间复杂度O(S(NlogVd2√V))((log⁡2))其中 S 是随机次数NlogVlog⁡ 是对所有 i 求 gcd(ai,x)gcd(,) 的复杂度d22 是把贡献从大因子加到小因子√V 是质因数分解。瓶颈还是 gcdgcd 太慢了。2026 XCPC TW11 kaitoC - Springboards G洛谷 - P6007非常简单只需要决定 dp 顺序。比如以 x 从小到大为第一关键字y 从小到大为第二关键字之后就是单点修改前缀查询。D - Trucks and CitiesCodeForces - 1101F设 f[l][r][k][][][] 表示把区间 [l,r][,] 分成 k 段后段的最大值的最小值。区间 dp 有转移f[l][r][k]minp{max(f[l][p][k−1],a[r]−a[p])}[][][]min{max([][][−1],[]−[])}而且还可以发现 f 的最佳点是单调的。首先这很明显其次发现是符合四边形不等式的。所以维护最佳点 opt[i][j−1]≤opt[i][j]≤opt[i1][j]opt[][−1]≤opt[][]≤opt[1][]就可以保证枚举最佳点是 O(n3)(3) 的。叫什么 Knuths optimization.XCPC 2026 W10Next DP Contest 2026Mtag(s): sos dp本质上是子集和问题然后每个子集有特殊的权值10k10。可以考虑 SOS DP设 f[S][i][][] 表示集合 S 倒数 i 维的答案然后记 L[S][i][][] 为对应字符串的长度。如果 S 的 i11-th bit 是 1有f[S][i1]f[S⊕2i][i]×10L[S][i]f[S][i][][1][⊕2][]×10[][][][]Next DP Contest 2026Ntag(s): dp, knapsack这个是有一篇论文的。题解见群里。XCPC 2026 WEEK8C - Avoid DivisionAtCoder - abc453_fTAG(s): constructive, greedy必要条件树有 L 个叶子。若某种颜色的可用次数 Ci≥2≥2则它可以同时出现在一条边的两侧。对于任何叶子如果它被涂上了 Ci11 的颜色切断它唯一的邻边后另一侧就不可能有该颜色因此所有叶子都必须用 Ci≥2≥2 的颜色覆盖。于是 ∑Ci≥2Ci≥L∑≥2≥ 是必要条件。充分性当 N≥3≥3 且上述条件成立时问题总有解。构造步骤如下选取一个非叶子的顶点 X使得删除 X 后每一个连通分量包含的叶子个数不超过 ⌊L/2⌋⌊/2⌋。这是可行的求法类似点分治求重心。当然 n22 是找不到的需要特判。将原树的叶子按删除 X 后所在的连通分量分组。类似哈基米构造法可以构造出一个相邻两个元素在不同连通分量的序列。处理所有 Ci≥2≥2 的颜色将序列中一段长度为 Ci 的序列染为颜色 i。如果序列剩余长度不足 2即为 1将 X 和这个点都染成颜色 i。所有剩余顶点用任意还有剩余次数的颜色涂满即可。E - SpicesAtCoder - abc236_fTAG(s): greedy, linear basis要能用 XOR 凑出 1∼2N−11∼2−1 的所有整数等价于选出的集合在异或意义下张成了整个 FN22也就是集合包含一组异或线性基。将所有香料按价格从小到大排序。贪心加入线性基即可。proof. 若当前香料不能被现有集合表示则在任何最优解中一定可以用当前香料替换掉某个价格不低于它的元素不会使总价增加。XCPC 2026 TW6 kaitoC - Interval GameCodeForces - 2217FTAG(s): dp, brute force, game theory不难发现是四个 Nim 游戏 l1−11−1x1−r11−1l2−12−1x2−r22−2。l1−1⊕x1−r11−1⊕1−1 可以凑出来的是 [0,x1)[0,1)所以问题变成找到最小的 y∈[0,x1)∈[0,1) 使得 f[y][] 最小。f 定义如下for (int i 0; i x2; i) for (int j 0; i j x2; j) f[i ^ j] 1;考虑快速求 f。我们知道 iji⊕j(ij)×2⊕()×2考虑不枚举 i 和 j 而是枚举 i⊕j⊕ 和 ij设其分别为 X 和 K。有KX00X2Kx222同时满足这样的 X 和 K 的 (i,j)(,) 对有 2popcount(X)2popcount⁡() 个。所以问题变成求 f[X]2popcount(X)×#{K∣KX0,K(x2−X)/2}[]2popcount⁡()×#{∣0,(2−)/2}考虑怎么计数后面那个东西可以数位 dp。总时间复杂度 O(xlogx)(log⁡)。D - Manhattan CafeAtCoder - abc265_fTAG(s): dp数据范围比较小考虑 dp。设 f[i][s][t][][][] 表示填了 i 维坐标到 p 距离是 s 到 q 距离是 t。直接转移好像是 O(nD3)(3) 的。但是可以发现在线段上选点有三种设 |pi−qi|d|−|具体有f[i][s][t]→f[i1][sk][td−k][][][]→[1][][−]f[i][s][t]→f[i1][sdk][tk][][][]→[1][][]f[i][s][t]→f[i1][sk][tdk][][][]→[1][][]其实是一堆斜率为 ±1±1 的斜线转移可以对斜线做前缀和优化到 O(nD2)(2)。滚动一下防爆空间。XCPC 2026 TW5 - KAITOD - A Simple GCD Problem (Hard Version)CodeForces - 2210C2TAGS: number theory首先区间限制可以简化为相邻两个的限制。记 gcd(ai,ai1)digcd(,1)。则 lcm(di,di−1)∣a′ilcm⁡(,−1)∣′。直接令 a′ilcm(di,di−1)′lcm⁡(,−1) 可以得到一个合法解。但不是最优解显然有 a′i∣ai′∣如果 aia′i′ 则少了一个操作次数。因为限制只和相邻两项相关可以考虑 dp设 f(i,k)(,) 表示前 i 个数已经满足条件并且 a′ilcm(di,di−1)∗k′lcm⁡(,−1)∗ 的最多操作次数。注意一下这里 k 的取值为了多操作一次我们应该让其乘上前面或后面没有的质数。所以随便找出前 30 个质数作为 k 的可能取值dp 即可。E - Learning Binary SearchCodeForces - 2211FTAG(s): combinatorics计算序列的贡献比较困难考虑计算数字的贡献。即∑a∑xf(a,x,1,n)∑x∑af(a,x,1,n)∑∑(,,1,)∑∑(,,1,)对于一个数字 xf(a,x,1,n)(,,1,) 事实上和 a 序列的具体值无关我们只关心 a 序列的值与 x 的大小关系。所以可以把序列分成三段第一段 x中间 x第三段 x。具体的设 [l,r][,] 这一段恰好都是 x。这样的区间的数量是 (l−1x−2l−1)(n−rm−x−1n−r)(−1−2−1)(−−−1−)。x11 和 xm 在看完下文做法并理解后特判一下就好了。这时候 f(a,x,1,n)(,,1,) 会在递归到l mid r的时候返回。具体的把递归的mid画成树状结构定义 ri 为 i 作为mid时递归的深度则 f(a,x,1,n)(,,1,) 的递归深度为 minl≤i≤rrimin≤≤。答案可以写成∑x∑l∑rf(a,x,1,n)∑x∑l∑r(minl≤i≤rri)(l−1x−2l−1)(n−rm−x−1n−r)∑l∑rminri∑x(l−1x−2l−1)(n−rm−x−1n−r)∑l∑r(minri)(nm−(r−l)−3n−(r−l))∑∑∑(,,1,)∑∑∑(min≤≤)(−1−2−1)(−−−1−)∑∑min∑(−1−2−1)(−−−1−)∑∑(min)(−(−)−3−(−))按照 minrimin 分治满足条件的 (l,r)(,) 其实应该是 Li≤l≤i,i≤r≤Ri≤≤,≤≤。可以继续化简∑l∑r(minri)(nm−(r−l)−3n−(r−l))∑Li≤l≤i∑i≤r≤Riri(nm−rl−3m−3)ri∑Li≤l≤i(nml−i−3m−2)−(nml−4−Rim−2)ri[((nm−1m−1)−(nmLi−i−2m−1))−((nmi−Ri−2m−1)−(nmLi−3−Rim−1))]∑∑(min)(−(−)−3−(−))∑≤≤∑≤≤(−−3−3)∑≤≤(−−3−2)−(−4−−2)[((−1−1)−(−−2−1))−((−−2−1)−(−3−−1))]真是丑陋啊。XCPC 2026 TW4 - KAITOC - Count Power of 2AtCoder - arc216_cTAG(s): HASHING, DIVIDE CONQUER首先需要一个能快速判定一个区间是否合法的方法. 会发现值域非常大, 但是数字没几种(最多 n22 种). 可以考虑哈希. 取一个大质数 P, 我们认为一个区间 [l,r][,] 合法当 ∑ril2ai≡2k(modP)∑2≡2(mod) for some k.下一步, 不难感受到答案不会有很多. 比如一个所有数都是 00 的情况, 也只有 O(nlogn)(log⁡) 个答案.假设一个区间 [l,r][,] 中, maxaiMmax, 那么这个区间的和不会超过 2MlogN2log⁡.这启发我们不去枚举区间然后判断是否合法. instead, 先枚举区间的 maxmax, 设其为 am. 利用分治, 求出所有 L≤l≤m,m≤r≤R≤≤,≤≤ 的合法区间数, 递归解决 [L,m−1][,−1] 和 [m1,R][1,] 的情况.在统计跨过 am 的区间的时候, 首先枚举区间和(2am,2am1,…,2amlog2(R−L1)2,21,…,2log2⁡(−1)). 之后再枚举左或右端点中少的那个.最后分析分治的复杂度, 约为 f(n)f(m)f(n−m)min(m,n−m)logn()()(−)min(,−)log⁡, 主定理后是 O(nlog2n)(log2⁡). 最后还需要乘上用来查询某个数值是哪个前缀和的数据结构的复杂度.D - A Trivial String ProblemCodeForces - 2209ETAG(s): border, greedy首先 dp 的转移只能是 border. 这题要最多划分, 所以自然想到选择最短的 border. 接下来考虑证明最小 border 划分是最优的. 如果最优解划分有一个不是最小 border, 则可以把这个分裂, 矛盾.XCPC 2026 TW3B - Subsequences GaloreCodeForces - 1620G首先考虑怎么求 f([s1,…,sk])([1,…,])“至少一个包含”其实不好直接求。注意到求“所有都包含”是好求的也就是交是好求的。所以考虑容斥原理。那对于一个子序列 T看作子集答案应该为f(T)∑S⊆T(−1)|S|1g(S)()∑⊆(−1)||1()其中 g(S)() 是原问题的“所有都包含”版本。右边可以把系数融入到 g(S)()那 f(T)() 就是 g 的 T 子集和了。可以高维前缀和做时间复杂度 O(n2n)(2)。C - ArenaCodeForces - 1606E第一轮所有人都会掉 n−1−1 滴血只有第一轮是好考虑的。只能做一步转移的时候不妨想一下能不能递归解决问题。直接令 f(n,x)(,) 表示答案则 (n,x)(,) 会转移到 (m,x−(n−1))(,−(−1)) 这个状态。所以可以写出式子f(n,x)n∑m0(nm)(n−1)mf(n−m,x−(n−1))(,)∑0()(−1)(−,−(−1))边界这里不赘述。D - Locked OutCodeForces - 2161D题目的限制不好考虑一个全称量词还有两个变量。考虑转化一下限制。记 Li 为 i 这个数字在答案数组里面的最左出现位置Ri 则为最右。那题目的限制可以转化为 LiRi11。这个限制条件有一个很天然的顺序就是 Ri11 只和 Li 有关启发我们从小到大考虑每个数字。把原数组按照数值排序以下标逆序为第二关键字就可以从左到右 dp。fi 表示钦定保留排序后数组里面的第 i 个数最多能保留几个数。转移不赘述。E - Bessla Motors G洛谷 - P10193考虑魔改 dijk记录每个点的前 K 短路相同起点需要去重。这样每个点只会松弛 10 次复杂度约为 O(αkmlogn)(log⁡)α 取决于维护前 K 短路的方法。F - Sum of FractionsCodeForces - 2204F首先考虑一个区间内怎么做操作最优。大概能想到你只会对 bi 最小的那个数操作。因为改成对 minbimin 复刻不在其上的操作答案一定会更大。下一步考虑怎么操作会发现 1 是一个分界。假设最后你操作成 x/y/ 了如果 xy根据糖水不等式回退对 y 的操作改成对 x 操作结果会变成 (x1)/(y1)(1)/(1)更大了。一直回退最后 y′b′。反之 xy 就应该改为 (x−1)/(y−1)(−1)/(−1)。所以如果 kb就应该改成 (1k)/b(1)/反之改成 1k−(b−1)1−(−1)。所以答案可以写成 f([l…r],k)f(minb,k)g(l,r)([…],)(min,)(,)其他部分其实是和 k 无关的常数推式子计算一下就好了。对于 minbmin可以考虑计算 b 的贡献单调栈跑一下Lprevious_less和Rnext_less那所有子区间 [l,r](Lil≤i,i≤rRi)[,](≤,≤) 的 minbmin 都是 bi 了。乘一下系数即可。G - Codeforces Heuristic Contest 001CodeForces - 2195H首先人为构造可以放两个直角三角形占满 2×32×3 的格点。对于这题考虑递归构造。想从 n 递归到 n−1−1 需要构造 3×3n3×3 的矩形和 3×3(n−1)3×3(−1) 的矩形不可能完全填充这是很劣的。但是发现从 n 递归到 n−2−2 是简单的用 2×32×3 去填充 6×3(n−2)6×3(−2) 和 6×3n6×3 显然可以随便就填满。所以显然 n 为偶数是可以填满的。操蛋的是 n33 也是可以填满的只能手模。H - FTLCodeForces - 1743Ehℎ 这一维比较小启发使用背包。由于最优操作要么是交替发射激光要么是同时发射激光并且每次发射激光一定掉血所以这些操作最多只有 hℎ 种。O(h2)(ℎ2) 背包。XCPC TW22206B Subtree Removal Game很有意思的是发现不好分析取决于谁先手一棵树可能有两个答案。有一个做法是二分答案。将 ≤m≤ 的视作 N 类节点m 的视为 P 类节点。对于孩子全是叶子的节点如果 N 节点数量大于 P 节点数量不论先后手答案就是 N反之就是 P。如果相等那就是谁先手谁赢。把 N 节点看成 w11P 节点看成 w−1−1根据 ∑w∑ 的正负性可以分为前面三类对于更一般的情况设当前节点的孩子有一些是 N有一些是 P有一些是 0。先手肯定尽可能去删 P 子树后手尽可能去删 N 子树这两个都等价于操作 0 子树所以答案和上一段落一样。2206I Growth Factor首先预处理ai 肯定可以取后缀 minmin变成一个不降序列。其次不难想到 dp f[i][v][][] 表示填完前 i 个位置并且 biv 的方案数。接下来问题是这个转移复杂度太高不可做。接下来非常神秘。如果 ai 都是 ∞∞那么把答案写在一张表格里会发现 f[i][v][][] 关于 i 是一个多项式或者说多项式增长并且次数在 1,2,4,81,2,4,8 有明显的加一换句话说fv(i)() 是一个关于 i 的不超过 log2vlog2⁡ 次的多项式。下一步的问题是知道是多项式之后又要怎么推导首先要考虑如何记录多项式系数。如果 fv(i)∑jajij()∑推导时需要利用 fv(i)∑u∣vfu(i−1)()∑∣(−1)左边有 fv(i)()右边有 fv(i−1)(−1)减起来麻烦得要死需要展开二项式系数。考虑让 fv(i−1)(−1) 用 fu(i−1)(−1) 表示最后可以得到 fv(i)∑i−1j1∑u∣vfu(j)()∑1−1∑∣()即 fv(i)∑u∣v∑i−1j1fu(j)()∑∣∑1−1()。我们需要一个好求前缀和的多项式表示法考虑牛顿级数。一个 d 次多项式 f(n)() 可以表达为组合数的形式有f(n)d∑i0ci(ni)()∑0()这个多项式的前缀和比较好求有n∑k0f(k)n∑k0d∑i0ci(ki)d∑i0cin∑k0(ki)d∑i0ci(n1i1)