第一次做 CF1554D Diane 的时候我盯着题目看了很久给一个正整数 n要输出一个长度为 n 的小写字母字符串 s使得 s 的每一个非空子串在 s 中出现的次数都是奇数。换句话说任意一个“连续片段”无论它是一段还是两段在整串里都不能出现偶数次。第一次接触这个条件的时候很容易懵因为子串种类是 O(n^2) 级别的怎么可能全部保证奇数但拆开分析之后会发现解法其实非常干净甚至最后构造出来的字符串结构简单到不可思议。这篇就顺着我当时思考的过程把完整构造、证明、代码实现以及踩过的坑都写出来。适合正在训练构造题、想理顺奇偶性证明的人也适合需要一份能直接照着写、再慢慢回去琢磨的参考。1. 先把题意翻译成人话1.1 一个例子讲清楚“出现奇数次”子串就是原字符串里连续的一段。比如 s abcab那么 ab 出现两次第一次从位置 0 到位置 1第二次从位置 3 到位置 4所以 ab 的出现次数是 2是偶数不符合要求。再比如 a 在 abcab 里也出现两次同样不合格。而 bc 只出现一次是奇数符合要求。题目要求的是所有能作为子串出现的不同字符串它们在整串里的出现次数都必须是一个奇数。这里有一个立刻能推出的必要条件每个字符本身也是一个长度为 1 的子串所以每个字符在字符串中的出现次数必须是奇数。这个条件虽然简单但能挡住很多不靠谱的第一反应。比如有人想“那我把 n 个字符全部用不同的字母拼起来”每个字符出现 1 次每个子串也最多出现 1 次确实全奇数。但小写字母只有 26 个n 稍微大一点这条路就断了必须让某个字符重复出现而重复之后要让所有长度的子串计数仍然保持奇数这就不是碰运气能解决的了。1.2 为什么不能一直用“全不同字符”的思路先做几个小例子找感觉。n 1 时输出 a 就行子串只有 a出现 1 次。n 2 时 ab 可以每个子串都只出现 1 次。n 3 时 abc 也可以。问题是 n 4 的时候全不同字符还能用 abcd但 n 26 以后就不行了。即使 n 还没到 26我们也希望找到一个能统一处理任意 n 的模式而不是靠枚举长度去凑。再试几个失败的构造。比如 n 3 时输出 aaa子串 a 出现 3 次是奇数aa 出现 2 次是偶数立刻失败。n 4 时输出 aabb子串 a 出现 2 次失败。于是想到把字符分散开但又要控制每种子串的计数。手工凑几个例子之后会发现光盯着长度 1 的子串不够长度 2、长度 3 的计数可能在某一步变成偶数。所以我们需要一种能列出公式的结构让所有长度的计数都能放在一张表里分析。1.3 构造题的通用武器让计数变成通项公式处理这种题最忌讳从头到尾枚举子串。正确做法是先设计一个特殊的字符串形状使得子串出现次数可以被一条式子表达然后只需要检查这条式子的奇偶性。常见的思路是在字符串里插入一个只出现一次的“特殊字符”比如 b。这样所有包含 b 的子串就全部被“锁死”了因为 b 只有一个位置模板一旦确定匹配位置基本唯一。剩下的不含 b 的子串就只能是纯 a 的连续段。这个想法把一个大问题拆成了两半一半是天然的奇数另一半是可以用等差数列计算的计数。下面这一节就是整个构造的核心。2. 核心思路用唯一分隔符把麻烦隔断2.1 唯一特殊字符 b含 b 的子串天然只出现 1 次假设我们的字符串形状是 a^L b a^M也就是左边 L 个 a中间一个 b右边 M 个 a。这个串里只有一个 b。现在随便取一个包含 b 的子串比如 ab、ba、aab、aba它无论长什么样在整串里匹配的时候模板里那个 b 都只能对着整串里唯一的那一个 b。模板的左端长度、右端长度一旦确定整个匹配区间就唯一确定了。所以结论非常强所有包含 b 的不同子串出现次数不是 0 就是 1题目只要奇数所以这部分全部安全。这个思想可以类比成整条路上只有一家招牌是蓝色的店任何一张要拍到这家店的街景照片取景框一旦固定拍到的位置就只有一个因为店本身是唯一的。有了这个“锚点”之后问题一下子缩小了一大半不需要再统计任何包含 b 的子串只剩纯 a 子串需要考虑。2.2 不含 b 的子串退化成纯 a 子串统计在 a^L b a^M 这个结构里不含 b 的连续段只能是一段连续的 a。由于 b 在中间隔开任何连续段都不能同时跨越左侧和右侧的 a所以长度为 i 的纯 a 子串只可能完全落在左段或者完全落在右段。左段长度是 L右段长度是 M。长度为 i 的子串在长度为 L 的连续段里一共有 L - i 1 个起点在长度为 M 的连续段里一共有 M - i 1 个起点。于是长度为 i 的纯 a 子串总出现次数就是cnt(i) max(0, L - i 1) max(0, M - i 1)如果某一段长度不足 i那么那一项为 0说明该段不产生长度 i 的纯 a 子串。这个公式是整个构造的核心接下来所有讨论都围绕它的奇偶性展开。2.3 关键推导两段 a 的长度必须相差 1把 cnt(i) 按 i 的范围拆成两个区间。第一段区间i ≤ min(L, M)此时左右两段都足够长公式变成cnt(i) L M - 2i 2要让这个数对所有 i 都为奇数关键看 L M 2 的奇偶性。因为 -2i 只改变偶数不减奇偶性所以 cnt(i) 和 L M 2 同奇偶。也就是说需要 L M 是奇数。第二段区间min(L, M) i ≤ max(L, M)此时只有较长的那段还有长度 i 的子串公式变成cnt(i) max(L, M) - i 1这个数随着 i 增加会从某个正数一路递减到 1。如果这段区间包含两个或更多的 i那么连续的两个 i 得到的 cnt(i) 必然一奇一偶肯定有偶数出现。因此这段区间最多只能有一个 i。这意味着 |L - M| ≤ 1。把两个条件放一起L M 必须是奇数且 |L - M| ≤ 1。两个整数相差不超过 1只有两种可能相等或者相差 1。如果 L M那么 L M 是偶数第一段区间直接失败。所以只剩下 |L - M| 1。而两个相差 1 的整数之和必然是奇数两个条件刚好同时满足。结论就一句话在这个结构里两段 a 的长度必须相差 1。但这里立刻出现一个危机a^L b a^M 的总长度是 L M 1 n。既然 L 和 M 相差 1那么 L M 一定是奇数所以 n 必须等于一个奇数加 1也就是 n 只能是偶数。这解释了为什么只靠一个 b 构造不出奇数 n 的答案奇数情况必须再多加一个字符来打乱奇偶结构。3. 最终构造与完整证明3.1 偶数 n两段 a 加一个 b当 n 是偶数时设 n 2m构造s a^m b a^(m-1)也就是左边 m 个 a中间一个 b右边 m - 1 个 a。两段长度分别是 m 和 m - 1正好相差 1。验证一下。包含 b 的子串全部只出现 1 次不用管。纯 a 子串分两种情况如果 i ≤ m - 1左右两段都产生贡献cnt(i) (m - i 1) (m - 1 - i 1) 2m - 2i 1因为 2m 是偶数减 2i 还是偶数最后再加 1 得到奇数。如果 i m那么只有左段还有贡献cnt(m) 1也是奇数。i 再大就不存在了。所以所有子串出现次数都是奇数。举个例子n 6m 3构造是 aaabaa。子串 a 出现 5 次aa 出现 3 次aaa 出现 1 次所有含 b 的子串都是 1 次。完全符合要求。3.2 奇数 n两段 a、一个 b、一个尾部 c当 n 是奇数时设 n 2k 1其中 k ≥ 1构造s a^k b a^(k-1) c也就是左边 k 个 a中间一个 b右边 k - 1 个 a最后再放一个 c。注意 n 1 要单独处理直接输出任意长度为 1 的字符串比如 a因为这里 k 0 时 a^(k-1) 的指数是 -1。证明分三类。第一类包含 b 的子串。整个串只有一个 b所以任何包含 b 的子串最多出现 1 次满足奇数要求。第二类包含 c 的子串。c 被放在字符串末尾而且全串也只有一个 c。一个包含 c 的子串在匹配时它的最后一个字符必须落在 c 的位置因此模板的右端被固定模板里如果有 bb 的位置也被唯一 b 固定模板里的其他 a 字符按左右扩展长度也唯一。所以包含 c 的子串同样最多出现 1 次。注意如果一个模板同时包含 b 和 c由于两个特殊字符都是唯一的匹配位置依然唯一同样只出现 1 次。第三类不含 b 也不含 c 的子串。那只能是纯 a 子串分布在左段长度 k 和右段长度 k - 1 里。当 i ≤ k - 1 时cnt(i) (k - i 1) (k - 1 - i 1) 2k - 2i 1 n - 2i。n 是奇数所以这是奇数。当 i k 时只有左段贡献 1 次也是奇数。全部满足。n 3 的时候k 1构造是 abc每个子串都出现 1 次没问题。n 5 的时候k 2构造是 aabac之前手推过也完全没有问题。3.3 为什么第三个字符要放在末尾有人可能会问奇数 n 的时候能不能把 c 放在中间比如 a^k b a^p c a^q 这种原则上只要保证所有特殊字符唯一证明框架还是一样的但放中间会让“包含 c 的子串”多出左右两侧的扩展讨论证明变长。放到末尾之后包含 c 的子串必须以 c 结尾匹配位置直接唯一写起来最省事。还有一个容易忽略的点偶数 n 的构造千万不要画蛇添足也加一个 c。在 a^L b a^M c 这种带尾部 c 的结构里两段 a 的总长度是 n - 2。偶数 n 时 n - 2 还是偶数可是相差 1 的两段 a 长度之和一定是奇数这两件事直接矛盾。所以偶数情况只能使用不带 c 的两段结构奇数情况必须使用带 c 的三段结构。两者是配套的不能混用。3.4 拿 n7 完整跑一遍奇数 n 7k 3构造是 aaabaac。分类看一下纯 a 子串中a 出现 3 2 5 次aa 出现 2 1 3 次aaa 出现 1 次全是奇数。含 b 的子串 b、ab、ba、aab、aba、aaab、aaba 等等全都只出现 1 次。含 c 的子串 c、ac、aac、bac、abac、aabac、aabac注意 aabac 本身也是整体一个子串其他含 c 子串也一样都只出现 1 次。没有遗漏整个字符串确实满足要求。4. 代码实现、边界与提交细节4.1 C 参考实现直接给一份能过题的 C 代码#include bits/stdc.h using namespace std; int main() { ios::sync_with_stdio(false); cin.tie(nullptr); int T; cin T; while (T--) { int n; cin n; if (n 1) { cout a\n; continue; } if (n % 2 0) { int m n / 2; cout string(m, a) b string(m - 1, a) \n; } else { int k n / 2; // 整除即 (n - 1) / 2 cout string(k, a) b string(k - 1, a) c \n; } } return 0; }几个实现细节。string(0, a) 是合法的空串所以 n 2 时偶数分支输出 ab完全正确。奇数分支里k 最小是 1k - 1 0输出空串所以 n 3 输出 abc。唯一需要特判的边界是 n 1因为 k 0 时 k - 1 -1string(-1, a) 属于未定义行为绝不能出现。4.2 Python 参考实现Python 版更紧凑t int(input()) for _ in range(t): n int(input()) if n 1: print(a) elif n % 2 0: m n // 2 print(a * m b a * (m - 1)) else: k n // 2 print(a * k b a * (k - 1) c)Python 里字符串乘 -1 会得到空串而不是报错所以 n 1 时不特判也会输出 bc长度还是 2结果完全错误。这个特判必须写。4.3 边界自测表与复杂度下面这张表列出 n 1 到 n 8 的构造输出可以用来和本地暴力验证对照。n输出结构说明1a特判2ab偶数分支右段为空3abc奇数分支右段为空4aaba偶数分支5aabac奇数分支6aaabaa偶数分支7aaabaac奇数分支8aaaabaaa偶数分支复杂度方面每组数据构造长度为 n 的字符串时间是 O(n)总时间取决于所有测试的 n 之和。输出用标准流没什么可担心的注意 C 里不要频繁 flush 就行。5. 踩坑记录与构造题通用经验5.1 坑一只检查长度 1 的子串就觉得自己对了我第一次想出的候选是 aabaa觉得 a 出现 4 次明显失败换成长度 1 都是数的勉强过关之后又差点漏掉长度更大的子串。这类构造题最迷惑人的地方就是长度 1 的子串只是全部约束的冰山一角长度 2、长度 3、一直到最长连续 a 段都可能突然冒出偶数。正确姿势是先把 cnt(i) 的通项写出来再一次性判断所有 i或者直接跑一个暴力验证脚本把所有长度扫一遍。5.2 坑二把“含 b 子串的种数”当成“某个子串的出现次数”在 a^L b a^M 里包含 b 的子串一共有 (L 1)(M 1) 个。这个数字本身可能很大有时候甚至是偶数。但它是“含 b 子串的种类数”不是“某一个特定子串的出现次数”。题目要检查的是同一个子串出现了几次而不是一共有多少种含 b 的子串。因为 b 是唯一的任何一个含 b 的特定子串模板最多出现一次所以无论 (L 1)(M 1) 是多少都不影响结论。这里一开始容易绕进去想复杂。5.3 坑三n1 时指数变成负数奇数分支 a^k b a^(k-1) c当 n 1 时 k 0a^(k-1) 是 a 的 -1 次方这在 C 里是未定义行为在 Python 里会得到空串然后输出错误答案。这道题不给 n 1 特判前几个样例可能没问题但一到隐藏数据就会挂。所以写构造题的时候凡是出现 n/2 和 n/2 - 1 的地方都要习惯性地检查 n 1、n 2 这种最小边界。5.4 这类构造题的通法小结把这道题的经验推广一下以后遇到“每个子串出现次数都是奇/偶数”之类的要求可以按这个顺序思考第一步找天然安全的位置。一个只出现一次的特殊字符能让所有包含它的子串计数变成 1。这是整个构造的锚点。第二步把剩余的子结构写成计数公式。比如纯 a 子串的个数是等差数列 max(0, L - i 1) 之和。第三步让公式的奇偶性在所有 i 上都成立。这一步通常会产生对长度参数的约束比如两段 a 长度必须相差 1。第四步单独处理边界。n 1、空串、负数长度都要在代码里提前规避。第五步用暴力验证脚本兜底。构造题的正确性不能只靠肉眼写一个枚举所有子串并统计出现次数的脚本随机测 n 1 到 50一秒就能发现问题。5.5 一份一分钟就能写完的暴力验证脚本下面是配套的 Python 验证代码把构造和检查放在一起from collections import Counter def ok(s: str) - bool: cnt Counter(s[i:j] for i in range(len(s)) for j in range(i 1, len(s) 1)) return all(v % 2 1 for v in cnt.values()) for n in range(1, 21): if n 1: s a elif n % 2 0: m n // 2 s a * m b a * (m - 1) else: k n // 2 s a * k b a * (k - 1) c assert ok(s), n print(all ok)这个脚本用 Counter 枚举所有起点和终点统计每个不同子串的出现次数然后检查是否全部为奇数。跑一遍会发现 n 1 到 n 20 的构造全部通过相当于给结论加了一道保险。最后说点个人感受。当时卡住我的不是想不出 a^k b a^(k-1) c 这个形式而是不敢确认含 b 的子串到底会不会重复出现。后来想明白“特殊字符唯一 包含它的子串唯一”之后整个证明就顺畅了。之后再做类似的构造题我都会先找能不能用一个唯一元素把大批子串锁成 1 次再集中处理剩下的计数。这个习惯帮我解决过很多构造题。如果你也在刷这一类题我建议拿到题先别急着写代码多推几步 cnt(i) 的公式再把边界情况和暴力验证脚本准备好。CF1554D 这道题确实值得来回多玩几遍。