1. 题目回顾一个看起来不可能的构造题CF1554D 是 Codeforces Round 1554 的 D 题题名叫 Diane。题面本身短到可以抄在便签纸上给你一个正整数 n请你构造一个长度为 n、只由小写字母组成的字符串要求字符串的每个子串在它里面出现的次数都是奇数。我第一次看到这个要求时第一反应是这题是不是在玩我。因为随便写一个字符串比如 abab子串 a 出现 2 次就已经违规了ab 也出现 2 次同样违规。哪怕你想取巧输出 n 个 a子串 a 出现 n 次子串 aa 出现 n-1 次n 和 n-1 的奇偶性必然不同总有一个是偶数。换句话说最朴素的两种思路——全 a 串和随便乱写——都是死路。但这类构造题有一个特点题目越像不可能往往越藏着一条特别简洁的出路。Diane 这道题的核心不在什么高级数据结构上而在一个非常朴素的观察——只要字符串里存在某个只出现一次的字符所有包含它的子串就自动满足条件了。想通这一点代码只需要五行。这篇主要适合正在刷 Div2 D 级别构造题、想练奇偶性思维的人。就算你只有最基础的概念知道子串是字符串里连续的一段也能顺着下面的思路把它完整推出来。1.1 题面到底在说什么先把已知条件理清楚。子串出现次数指的是同一个字符串在整个字符串中作为连续片段一共出现多少次。例如 s aaba子串 a 出现 3 次分别落在位置 1、2、4子串 aa 出现 1 次位置 1-2子串 ab 出现 1 次位置 2-3子串 ba 出现 1 次位置 3-4。注意这里统计的是不同的子串内容不是按照位置去数一个子串出现多少次就是统计它在 s 里所有能匹配的位置总数。题目有多组测试用例每个给一个 n要求对每个 n 输出一组合法字符串。输出哪个合法字符串都可以不要求唯一。n 的范围给得很大所以你几乎不可能用枚举候选串 验证的思路去做必须直接给一个公式化的构造。这类题在 CF 里经常出现考验的不是你会不会后缀数组而是你能不能从数学上找到一个处处成立的充分条件。1.2 为什么全 a 串和随便写必然失败如果整个字符串全是 a长度为 n那么子串 a 出现 n 次子串 aa 出现 n-1 次。这两个次数一个是 n一个是 n-1奇偶性必然相反所以至少有一个是偶数直接违规。这个简单反例揭示了一个重要事实一段连续的相同字符越长不同长度的子串出现次数会形成 n、n-1、n-2、… 的递减序列奇偶性跟着交替。想打破这种交替就必须用其他字符把长串的 a 切开。随便写同样不行。但凡某个字符在整个串里出现偶数次长度为 1 的子串就已经违规了而想让所有字符的出现次数都是奇数本身已经是很强的约束。再加上长度为 2、3 的子串也要满足条件随便构造几乎必挂。这道题真正要你回答的问题是在这么多必须满足的限制下到底存在不存在一个统一的构造模板答案是存在而且模板非常简单。1.3 一个关键的破题视角先找天生安全的子串在思考构造之前先问自己一个问题什么样的子串不管怎样出现都是奇数答案脱口而出出现次数为 1 的子串。如果某个字符串在整个大串里只可能出现一次那它当然是奇数。顺着这个思路继续如果有一个字符只在整个串里出现一次那么任何包含这个字符的子串都只能出现一次。因为你想再找一处一模一样的匹配至少得再找一个同样的字符出来——但它只有一个。于是整个问题被一下子简化了把字符串设计成大量危险的 a 串区域被一些只出现一次的字符隔开然后专心处理那些不包含特殊字符的纯 a 子串。这就是 Diane 的全部秘密。剩下的事情无非是用一个奇偶性公式选出最合适的块长。2. 破题思路把奇数翻译成奇偶性现在进入正题。设我们的构造形态是左段 p 个 a 一堵特殊的墙 右段 q 个 a墙里面放一个或两个只出现一次的字符。这样一来所有包含墙字符的子串都天然出现奇数次更准确地说恰好一次我们只需要验证纯 a 子串即可。这个先隔离再处理的思路比直接对着整个字符串想条件要清爽得多。2.1 单段 a 串的子串计数先把基础公式写清楚。假设有一段连续的 R 个 a那么对由 L 个 a 组成的子串 A_L也就是 a 重复 L 次它在这段里出现的次数是R - L 1原因是 A_L 可以以第 1 到第 R-L1 个位置作为开头。比如 aaaa 里a 出现 4 次aa 出现 3 次aaa 出现 2 次aaaa 出现 1 次。这虽然是小学数学但它是今天所有推导的地基——构造题里真正决定成败的往往就是这种小学公式加上一个模 2 的观察。2.2 两段 a 串合并时出现次数怎么算我们的构造是左段 p 个、右段 q 个中间是墙墙里没有 a。那么一个纯 a 子串 A_L 到底出现几次分两种情况如果 L 同时不超过 p 和 q左右两段都有贡献左边贡献 p-L1 次右边贡献 q-L1 次总数是 (p-L1) (q-L1) pq-2L2。如果 L 只能被其中一段完全容纳那就只算那一段的贡献。第一行那个式子有个非常漂亮的性质pq-2L2 对 2 取模等于 pq 对 2 取模。因为 -2L2 永远是偶数完全不影响奇偶性。换句话说只要 pq 是奇数那么所有满足 L ≤ min(p,q) 的纯 a 子串出现次数一律是奇数和 L 的具体大小一点关系都没有。这是本题最核心的结论。你可能要追问那 L 超过 min(p,q) 怎么办比如 L p 但 q p 时右边没贡献只有左边贡献 p-L1而这个数不一定是奇数。但注意在我们的最终构造里 p 和 q 只相差 1所以这种一边不够放的情况只可能发生在 L 恰好等于 p 时那时 p-L1 1正好是奇数。这个细节等第 3 节构造完毕后再严格检查一遍。2.3 为什么必须是两段而不是一段或三段既然关键结论是 pq 要为奇数有人会想那干脆把 a 串切成一段不就行了不行一段时计数公式是 R-L1奇偶性随 L 交替变化全 a 串反例已经说明问题。那三段呢假设三段长度是 p1、p2、p3对不超过三个数最小值的 L出现次数是 (p1-L1)(p2-L1)(p3-L1) S - 3L 3其中 S 是 a 的总数。这个式子对 2 取模会得到 S 3(1-L) ≡ S 1 - L (mod 2)也就是说它还依赖 L 的奇偶并没有被消干净。更一般地k 段 a 串的计数是 S - kL k奇偶性 S k(1-L) (mod 2)只有当 k 是偶数时L 前面的系数才会消失。两段是满足这个条件的最简单选择出题人的答案形态几乎是被数学逼出来的。这段分析平时不会写进题解但我觉得它比结论本身更值得记住当你发现一个式子恰好只跟总数有关、跟具体长度无关时多半是设计者精心挑过段数。做题时遇到类似情况可以主动往段数必须是偶数这个方向想。2.4 墙的长度也有限制现在约束条件逐渐成形墙里的字符必须都只出现一次左右两段 a 的块长之和 pq 必须为奇数同时整串长度必须是 n。这三个条件会精确逼出最终构造。墙为什么有时候要一个字、有时候要两个字因为墙字符同样占用长度而 n 的奇偶性决定了你能往墙里塞多少东西。下一节按 n 的奇偶性分别求解你会发现所有参数都是定死的没有自由发挥空间。3. 构造方案与完整证明3.1 n 为偶数n 2m偶数时直接用一个字符 b 当墙。构造s a 重复 m 次 b a 重复 m-1 次长度m 1 (m-1) 2m n正好。左段 p m右段 q m-1pq 2m-1是奇数完美满足奇偶性条件。验证部分纯 a 子串 A_L当 L ≤ m-1 时出现次数是 (m-L1)(m-1-L1) 2m-2L1是奇数当 L m 时只有左段容纳得下出现 1 次也是奇数。L 再大就不存在了不需要管。包含 b 的子串b 只出现一次所以所有包含它的子串都恰好出现一次。两者并集覆盖了全部子串结论成立。举几个小例子用表格记录实际计数n构造串a 出现次数aa 出现次数aaa 出现次数2ab1不存在不存在4aaba31不存在6aaabaa531表格里 1、3、5 全是奇数其他子串要么出现 1 次要么根本不存在。条件全部满足。3.2 n 为奇数且 n ≥ 3n 2m1奇数才是最需要小心的。很多人第一次会照抄偶数思路写成 a*m b a*m长度是 2m1 刚好对但此时 p q mpq 2m 是偶数子串 a 出现 2m 次直接违规。这个坑我后面还会专门复盘。于是我们把墙做长一点用两个不同的字符 b 和 c 当墙。构造s a 重复 m 次 bc a 重复 m-1 次长度m 2 (m-1) 2m1 n正好。p mq m-1pq 2m-1又是奇数。验证方法和偶数情况完全对称纯 a 子串 A_LL ≤ m-1 时出现 2m-2L1 次是奇数L m 时只有左段出现 1 次奇数。包含 b 或 c 的子串b 出现一次、c 出现一次任何包含其中至少一个字符的子串都只能在唯一位置匹配所以恰好出现一次。全部子串都是奇数构造正确。注意墙为什么必须是两个互不相同的字符。如果你在奇数长度里也只用单个 b 当墙为了凑出 pq 为奇数p 和 q 只能差 1比如 m 和 m-1但这样总长度是 m 1 (m-1) 2m比 n 少 1还得额外再塞一个字符。与其硬塞到某段 a 里破坏奇偶性不如直接让墙占两个位置反正墙字符只出现一次的特性依然成立。而两个墙字符如果相同比如 bbb 就出现两次子串 b 出现偶数次也不行。所以 bc 这种互不相同的组合是最自然的选择你把它换成 xy、mn 也完全没问题。3.3 边界情况n 1n 1 时上面的奇数构造会得到 a0 bc a(-1)右段长度是负数显然不对。所以单独特判直接输出 a。整个字符串只有一个子串 a出现 1 次奇数合法。到这里所有 n 的情况都有了构造方案整理成一张总表n 的奇偶构造方案n 1a偶数 n 2mam b a(m-1)奇数 n 2m1n ≥ 3am bc a(m-1)3.4 用手工验证几个小 n我写题解前习惯先用程序对 n1..20 全部跑一遍这里给两个手工能算的例子让你直观感受构造串长什么样。n 5 时m 2构造是 aabca。纯 a 子串方面a 出现 3 次aa 出现 1 次包含 b 或 c 的比如 ab、bc、ca、aab、abc、bca、aabc、abca、aabca全都是 1 次因为 b、c 各只出现一次。全部奇数。n 7 时构造是 aaabcaa。a 出现 5 次aa 出现 3 次aaa 出现 1 次其余含墙字符的子串最多出现 1 次。又是全部奇数。4. 最短的 AC 代码与复杂度分析思路理清楚之后实现几乎没有技术含量。下面给出 C17 和 Python 两个版本都是 O(n)。4.1 C17 实现#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; string ans; if (n 1) { ans a; } else if (n % 2 0) { int m n / 2; ans string(m, a) b string(m - 1, a); } else { int m n / 2; ans string(m, a) bc string(m - 1, a); } cout ans \n; } return 0; }C 的 string(cnt, ch) 构造器会生成 cnt 个指定字符复杂度 O(cnt)。三个部分拼起来总长度正好是 n所以每个测试用例 O(n)总复杂度 O(∑n)。代码里不需要任何高级数据结构也别去写什么后缀自动机。4.2 Python 实现import sys def solve(): data sys.stdin.read().split() t int(data[0]) out [] idx 1 for _ in range(t): n int(data[idx]) idx 1 if n 1: out.append(a) elif n % 2 0: m n // 2 out.append(a * m b a * (m - 1)) else: m n // 2 out.append(a * m bc a * (m - 1)) sys.stdout.write(\n.join(out)) if __name__ __main__: solve()Python 里 a * m 生成 m 个字符同样是线性操作。一次性读入所有数据、最后统一输出这样可以避免逐行 print 在大数据量下的额外开销属于一个很基础但也实用的 IO 习惯。4.3 复杂度和实现注意点时间复杂度每个测试用例 O(n)总 O(∑n)。这类题的数据规模通常是总和上百万级别线性做法完全够用。空间复杂度除了存答案字符串 O(n) 外没有任何额外空间。多测试用例格式题目给了 T记得每个答案单独换行最后一个字符串也要换行。n1 特判必须放在最前面奇数分支在 n1 时会算到负数的重复次数C 的 string(m-1, a) 在 m-1 为负数时会抛出异常或产生未定义行为Python 里 a * -1 是空串最终会构造出长度为 2 的 bc完全错误。5. 常见错误与对拍自测这一节把最容易出错的地方集中拿出来复盘都是我或者周围朋友真实踩过的坑。构造题不怕想不到最怕的是想了个差不多对的方案就直接交结果挂在边界上。5.1 最常见的错误构造奇数长度用了单个分隔符设 n 2m1很多人会写s a*m b a*m这个长度正确p q m但 pq 2m 是偶数。验证 n5得到 aabaa子串 a 出现 4 次偶数WA。问题出在哪两段等长时a 的总数被均分子串 a 的出现次数是 2m而 2m 永远偶数。所以在奇数长度下两段 a 块绝对不能等长。对比错误和正确方案n错误构造错误原因正确构造5aabaaa 出现 4 次aabca7aaabaaaa 出现 6 次aaabcaa9aaaabaaaaa 出现 8 次aaaabcaaa从表格能直观看到只要两段 a 串一样长子串 a 的次数必为偶数。把墙从单字符变成双字符、并把右段减掉一个 a问题立刻解决。这个错误极其经典我估计提交这道题的人里有一大半都挂在它上面。5.2 边界与实现细节的坑第二个高频坑是 n1。如果没特判奇数分支会构造出 bc 甚至直接崩溃。第三个坑是输出格式多组用例时最后一个字符串后面少换行这类题对输出格式很敏感少换行在某些判题机上会被判 WA。第四个坑是 C 里写 ans m * a 之类的表达式这会把字符的 ASCII 码乘上 m得到的是一个整数而不是字符串必须写 string(m, a)。这些都属于语法层面的低级失误但对拍或者编译一次就能发现。5.3 暴力 checker五分钟写个自测程序构造题最怕的不是想不到而是想到了却不敢确信。我的习惯是写个小暴力验证器把所有小 n 跑一遍心里有底再提交。checker 的思路极其简单生成所有子串用哈希表统计每个子串出现次数检查是否全部为奇数。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()) def construct(n: int) - str: if n 1: return a m n // 2 if n % 2 0: return a * m b a * (m - 1) return a * m bc a * (m - 1) for n in range(1, 30): s construct(n) assert len(s) n and ok(s), (n, s) print(all small n passed)这个程序对 n 到 30 以内的构造做了全量验证。n 再大的话暴力枚举子串是 O(n^3) 级别没必要公式证明已经齐了。但先写 checker 再提交这个习惯我一直推荐尤其是构造题它能帮你快速发现 5.1 那种长度对但性质错的隐蔽问题。5.4 构造题验证的通用习惯除了写 checker另一个有效的办法是做一些扰动实验把 a 块长度微调、把墙字母换成其他字母、把左右块交换再用 checker 验证。这样做能让你对哪些参数是必须的、哪些是自由的有更直观的理解。比如你会很快发现墙字母只要互不相同且不是 a换成 x、y 也没问题但墙字母相同就必挂两段 a 等长就必挂。这种扰动式的思考方式比单纯背一个结论有用得多。6. 从这题能带走的通用套路CF1554D 本身已经讲完了但构造一个满足奇怪子串条件的字符串这类问题在 CF 里隔三差五就会出现一次。最后分享几个我从中提炼的通用方法论都是我后来做题反复用到的。6.1 唯一低频字符当墙是一个高频范式很多字符串构造题的核心矛盾是有些子串天然难控制比如连续相同字符形成的长串。这时候引入一个在整个字符串里只出现一次或频率极低的字符把难搞的区域隔开就能让所有穿墙的子串瞬间变成安全状态。这个范式不止出现在 Diane 里很多涉及子串计数、子串是否出现、子串频次奇偶性的题目都靠这一招破局。学会它至少能让你在面对同类题时有一个正确的起步方向。6.2 看到出现次数为奇数就想到模 2奇偶性问题的标准动作是把计数写成关于长度的表达式然后整体对 2 取模把所有偶数项扔掉。这题里 (p-L1)(q-L1) 中那一大坨 -2L2 直接消失剩下 pq 独立决定一切。做题卡住时试着把计数公式写成关于长度的多项式再模 2经常会有原来如此的瞬间。奇偶性过滤是一个非常廉价的探路工具成本只有一张草稿纸。6.3 字符串构造题的做题顺序我自己总结的三步流程先看长度最小的子串能从必要条件里推出什么。比如单字符出现次数必须奇数次整串长度和字符频次奇偶数量之间还有隐藏约束。挑出最难搞的那类子串设计隔离方案让其他子串自动安全。验证边界n1、全同字符、最短反例再用暴力 checker 兜底。这套顺序帮我解决过好几道 Div2 D 和 Div2 E 的字符串构造题不敢说万能但至少能让你不再对着题面发呆。尤其是第一步很多人一上来就想怎么构造出所有子串都满足条件的串这太难了反过来从必要条件入手反而很快能圈定候选结构。最后说点个人体会。我做这题时一开始也走偏了想着用后缀自动机去数子串出现次数然后反向构造——后来意识到这完全是方向性错误构造题要的是充分条件不是把条件精确算出来。把只出现一次的字符会自动搞定一切包含它的子串这个观察写下来之后五分钟就写出了 AC 代码。之后我遇到类似的所有子串都要满足某种奇怪性质的构造题都会先问自己三个问题哪些子串是天生安全的哪些子串是最难控制的我能不能用低频字符把它们隔开这套想法帮我解决了不少同类题目希望也能帮到你。