XCPC 2026 WEEK 14

否则答案为 4。时间复杂度 O(nq√n)。感觉应该有很多复杂度同样正确的做法。D - Bracket GroupsCodeForces - 2144Ftag(s): ACAM, dp首先判断 −1。那就是某个字符串为()。不可能有合法的括号序没有()作为子串。除了这种情况一定有解吗答案是肯定的。我们可以构造出这样两个基本没有相同子串的括号序列()()()()()()()()() ((((((((()))))))))所有括号序列都只会出现在上面两者其一除了()。所以答案不会超过 2。问题变成检验答案是否为 1。这个问题不就是“是否存在一个字符串不包含任意给定字符串”经典的上 ACAM dp。XCPC2026 WEEK 13D - N-MEX (Counting Version)CodeForces - 2207E2首先考虑判断是否合法。由 mex 的定义显然 n≥a[i]≥n−i。其次从前缀 i 到前缀 i1最多只能增加一个数所以 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] (ji) 不能选并且 a[j]a[j−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/ω)其中 M5N 表示总共的颜色数量。差不多 2e83s 可以通过。问题在于空间被卡了。需要 N2/ω≈298 MiB题目只给了 256 MiB。没事可以拆成两次做。第一次只做bitset[i][j]其中 i′∈[0,n/2)第二次再做 i′∈[n/2,n) 的部分。只需要 149 MiB。D - GhdCodeForces - 364Dtag(s): 随机化我们注意在数组中随机一个数答案有高达 50% 的概率是他的一个因子。这启发我们随机一个数然后检测其所有因子是否符合条件差不多随机 20 次有 10−6 的概率失败。会 TLE 就随机少一点我怀疑随机 10 次就行但是一个数的因子太多了直接一个一个数还是 T 飞。但是可以直接数 gcd(ai,x)然后把这个东西的贡献加到其因子上。时间复杂度O(S(NlogVd2√V))其中 S 是随机次数NlogV 是对所有 i 求 gcd(ai,x) 的复杂度d2 是把贡献从大因子加到小因子√V 是质因数分解。瓶颈还是 gcd 太慢了。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])}而且还可以发现 f 的最佳点是单调的。首先这很明显其次发现是符合四边形不等式的。所以维护最佳点 opt[i][j−1]≤opt[i][j]≤opt[i1][j]就可以保证枚举最佳点是 O(n3) 的。叫什么 Knuths optimization.XCPC 2026 W10Next DP Contest 2026Mtag(s): sos dp本质上是子集和问题然后每个子集有特殊的权值10k。可以考虑 SOS DP设 f[S][i] 表示集合 S 倒数 i 维的答案然后记 L[S][i] 为对应字符串的长度。如果 S 的 i1-th bit 是 1有f[S][i1]f[S⊕2i][i]×10L[S][i]f[S][i]Next DP Contest 2026Ntag(s): dp, knapsack这个是有一篇论文的。题解见群里。XCPC 2026 WEEK8C - Avoid DivisionAtCoder - abc453_fTAG(s): constructive, greedy必要条件树有 L 个叶子。若某种颜色的可用次数 Ci≥2则它可以同时出现在一条边的两侧。对于任何叶子如果它被涂上了 Ci1 的颜色切断它唯一的邻边后另一侧就不可能有该颜色因此所有叶子都必须用 Ci≥2 的颜色覆盖。于是 ∑Ci≥2Ci≥L 是必要条件。充分性当 N≥3 且上述条件成立时问题总有解。构造步骤如下选取一个非叶子的顶点 X使得删除 X 后每一个连通分量包含的叶子个数不超过 ⌊L/2⌋。这是可行的求法类似点分治求重心。当然 n2 是找不到的需要特判。将原树的叶子按删除 X 后所在的连通分量分组。类似哈基米构造法可以构造出一个相邻两个元素在不同连通分量的序列。处理所有 Ci≥2 的颜色将序列中一段长度为 Ci 的序列染为颜色 i。如果序列剩余长度不足 2即为 1将 X 和这个点都染成颜色 i。所有剩余顶点用任意还有剩余次数的颜色涂满即可。