XCPC 2026 WEEK 14
否则，答案为 4。时间复杂度 O(n+q√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≥a[i]≥n−i。其次，从前缀 i 到前缀 i+1，最多只能增加一个数，所以 a[i]≤a[i−1]。可以设 a[0]=n。
这样一定合法吗？可以考虑构造：
- a[i]=a[i−1]，则 b[i] 一定要造成贡献，只能填一个 <a[i] 且从未出现在 a 内的数。
- a[i]<a[i−1]，则 b[i] 一定不能造成贡献，只能填一个 >a[i] 或者之前填过的数。
对于第二类，显然可以填 1145141919810。对于第一类好像不一定能填。不过证明一下，是可以填的。因为我们知道如果一共有 k 种 a[i]，那就有 n−k 个第一类，加起来刚好 n 个数。也就是事实上第一类可以填，甚至非常紧。
如果要计数，我们也是同一个道理，对于第一类，后面一共会 ban 掉 (n−i) 种数字（a[j] (j>i) 不能选，并且 a[j]=a[j−1] 会用掉一种数），所以一共有 a[i]−(n−i) 个数可以选；对于第二类，一共有 i 个数可以选。
E
- if 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 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:010takes 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/ω)，其中 M=5N 表示总共的颜色数量。差不多 2e8，3s 可以通过。
问题在于空间被卡了。需要 N2/ω≈298 MiB，题目只给了 256 MiB。
没事，可以拆成两次做。第一次只做bitset[i'][j]其中 i′∈[0,n/2)，第二次再做 i′∈[n/2,n) 的部分。只需要 149 MiB。
D - Ghd
CodeForces - 364D
tag(s): 随机化
我们注意，在数组中随机一个数，答案有高达 50% 的概率是他的一个因子。
这启发我们随机一个数，然后检测其所有因子是否符合条件，差不多随机 20 次，有 10−6 的概率失败。（会 TLE 就随机少一点，我怀疑随机 10 次就行）
但是一个数的因子太多了，直接一个一个数还是 T 飞。
但是可以直接数 gcd(ai,x)，然后把这个东西的贡献加到其因子上。时间复杂度：
O(S(NlogV+d2+√V))
其中 S 是随机次数，NlogV 是对所有 i 求 gcd(ai,x) 的复杂度，d2 是把贡献从大因子加到小因子，√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]=minp{max(f[l][p][k−1],a[r]−a[p])}
而且还可以发现 f 的最佳点是单调的。首先这很明显，其次发现是符合四边形不等式的。所以维护最佳点 opt[i][j−1]≤opt[i][j]≤opt[i+1][j]，就可以保证枚举最佳点是 O(n3) 的。叫什么 Knuth's optimization.
XCPC 2026 W10
Next DP Contest 2026M
tag(s): sos dp
本质上是子集和问题，然后每个子集有特殊的权值（10k）。
可以考虑 SOS DP，设 f[S][i] 表示集合 S 倒数 i 维的答案，然后记 L[S][i] 为对应字符串的长度。如果 S 的 i+1-th bit 是 1，有：
f[S][i+1]=f[S⊕2i][i]×10L[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 个叶子。若某种颜色的可用次数 Ci≥2，则它可以同时出现在一条边的两侧。对于任何叶子，如果它被涂上了 Ci=1 的颜色，切断它唯一的邻边后，另一侧就不可能有该颜色，因此所有叶子都必须用 Ci≥2 的颜色覆盖。于是 ∑Ci≥2Ci≥L 是必要条件。
充分性：当 N≥3 且上述条件成立时，问题总有解。构造步骤如下：
- 选取一个非叶子的顶点 X，使得删除 X 后每一个连通分量包含的叶子个数不超过 ⌊L/2⌋。这是可行的，求法类似点分治求重心。当然 n=2 是找不到的，需要特判。
- 将原树的叶子按删除 X 后所在的连通分量分组。
- 类似哈基米构造法，可以构造出一个相邻两个元素在不同连通分量的序列。
- 处理所有 Ci≥2 的颜色，将序列中一段长度为 Ci 的序列染为颜色 i。如果序列剩余长度不足 2，即为 1，将 X 和这个点都染成颜色 i。
- 所有剩余顶点用任意还有剩余次数的颜色涂满即可。