1. 从一道题看动态规划的“平衡”本质第一次看到 CF_17C Balance 这个题号很多人会愣一下——Codeforces 上 17C 确实是一道关于字符串平衡的经典题但网上流传的题面版本不少真正把“平衡”二字吃透的人并不多。我当年做这道题的时候卡了整整两天不是因为不会写状态转移而是因为没想明白“平衡”到底在平衡什么。后来带新人刷题发现大家踩的坑几乎一模一样把注意力全放在“怎么凑出目标串”上却忽略了题目真正在考察的是用最少的操作把原串改造成满足特定计数约束的形态。这个思路一旦转过来整道题就通了。这篇文章适合三类人正在刷 Codeforces 动态规划专题、被字符串计数类问题折磨过的选手想理解“平衡”类问题通用解法的算法学习者以及带课老师或集训队教练需要一份能直接讲给学生听的拆解材料。我会从题目本质、状态设计、转移推导、代码实现到调试技巧完整走一遍中间穿插我踩过的坑和后来总结的速查表。你不需要有很强的竞赛背景只要能写基础的循环和数组就能跟上。先给结论CF_17C Balance 的核心不是“构造”而是“计数”——统计有多少种方式能把原串通过替换操作变成满足“任意两个字符出现次数之差不超过 1”的串。这个“差不超过 1”就是平衡的定义。听起来简单但状态怎么设、边界怎么处理、重复怎么去每一步都有讲究。下面我按实际做题的顺序一层层拆开。2. 题目本质与核心需求拆解2.1 平衡条件的数学表达题目给的是一个只含 A、B、C 三种字符的字符串长度最多 150。你可以把任意位置的字符替换成另外两种之一每次替换算一步。问有多少种替换方案使得最终串中任意两种字符的出现次数之差不超过 1。用数学语言说设最终串中 A、B、C 的个数分别为 a、b、c则要求 |a-b| ≤ 1|b-c| ≤ 1|a-c| ≤ 1。这三个条件合起来其实等价于a、b、c 三个数中最大值减最小值 ≤ 1。也就是说三个计数要么全部相等要么是两个相等、第三个差 1。这个转化很关键。很多新手会分别去检查三个不等式写一堆 if其实只要抓住“极差 ≤ 1”这一个条件就够了。我在代码里通常直接算 max(a,b,c) - min(a,b,c) ≤ 1一行搞定既不容易漏判也方便后面做状态剪枝。那长度 n 固定时abc n。满足极差 ≤ 1 的三元组 (a,b,c) 有多少个如果 n 能被 3 整除只有 (n/3, n/3, n/3) 一种如果 n 除以 3 余 1则是 (n/31, n/3, n/3) 的排列共 3 种余 2 则是 (n/31, n/31, n/3) 的排列也是 3 种。这个结论直接决定了最终要统计的目标状态只有 1 个或 3 个而不是漫无边际地枚举。2.2 为什么不能直接贪心有人会想既然目标计数固定那我从原串出发看每个位置需不需要改改的话有几种选择乘起来不就行了这个思路错在字符之间会互相影响。举个例子原串是 AABn3目标只能是 (1,1,1)。第一个 A 可以改成 B 或 C第二个 A 也可以改成 B 或 C但如果你把两个 A 都改成 B那 B 就有 2 个C 有 0 个不满足平衡。所以每个位置的选择不是独立的必须全局统筹。这就是为什么必须用动态规划我们需要在扫描字符串的过程中同时跟踪已经确定的 A、B、C 各有多少个才能保证最终落在合法状态上。贪心在这里会失效因为局部最优比如尽量少改和全局可行计数平衡之间没有单调关系。2.3 操作的本质替换而非删除插入题目只允许替换不允许删除或插入。这意味着最终串的长度和原串完全一样只是某些位置的字符变了。这个约束简化了问题我们不需要考虑长度变化带来的组合爆炸只需要决定每个位置“保留原字符”还是“改成另一个字符”。但要注意替换是有方向的。原字符是 A你可以改成 B 或 C但不能“改成 A”那叫保留。所以在 DP 转移时每个位置有三种选择保留、改成另外两种之一。如果保留对应字符计数加 1如果改则目标字符计数加 1原字符计数不变。这个细节在写转移方程时很容易搞混我后面会专门讲。3. 状态设计与转移方程推导3.1 三维 DP 的自然想法最直观的状态是 dp[i][a][b][c]处理完前 i 个字符最终串中 A、B、C 的个数分别为 a、b、c 的方案数。但这样状态数是 150 × 150 × 150 × 150直接爆炸。不过注意到 abc i因为前 i 个位置已经确定了 i 个字符所以 c 可以由 i - a - b 推出来状态降到 dp[i][a][b]复杂度 150 × 150 × 150 ≈ 3.4M完全可接受。这个“用和约束消掉一维”的技巧在计数类 DP 里非常常见。我刚开始做题时总是不敢消维怕漏状态其实只要关系是恒等式消掉的那一维就是冗余的。这里 abci 是铁律因为每个位置必须且只能贡献一个字符。3.2 转移的三种分支设原串第 i 个字符1-indexed为 s[i]。从 dp[i-1][a][b] 转移到 dp[i][a][b]分三种情况保留 s[i]如果 s[i] 是 A则 a a1, b b如果是 B则 a a, b b1如果是 C则 a a, b b因为 c 自动加 1而 c i - a - b所以 a、b 不变。改成另外两种字符之一比如 s[i] 是 A改成 B则 a a, b b1改成 C则 a a, b b。注意这里有个容易错的地方当 s[i] 是 C 且选择保留时a 和 b 都不变但 c 增加了 1。因为我们的状态只记录 a 和 bc 是隐含的所以这个转移看起来“什么都没做”但实际上 i 增加了c 自然就多了。如果你用三维数组显式记录 c就不会有这个困惑但空间会大很多。我建议新手先用三维写一遍理解清楚后再压缩到二维。3.3 边界与初始化dp[0][0][0] 1其余为 0。最终答案是所有满足平衡条件的 dp[n][a][b] 之和其中 c n - a - b且 max(a,b,c) - min(a,b,c) ≤ 1。这里有个坑最终状态可能不止一个。比如 n4 时合法三元组是 (2,1,1) 的排列共 3 个。你需要把这三个状态的值都加起来。我见过有人只取 (n/3, n/3, n/3) 那个结果 n 不是 3 的倍数时答案偏小。另外取模问题。题目通常要求对 51123987 取模这是 CF 17C 的经典模数这个数不是常见的 1e97写代码时别顺手写错。我当年就因为模数写错样例过了但提交 WA查了半天。4. 代码实现与关键细节4.1 二维 DP 的完整写法#include bits/stdc.h using namespace std; const int MOD 51123987; int dp[155][155][155]; // dp[i][a][b] char s[155]; int main() { int n; scanf(%d %s, n, s 1); dp[0][0][0] 1; for (int i 1; i n; i) { for (int a 0; a i; a) { for (int b 0; a b i; b) { int c i - 1 - a - b; // 前 i-1 个字符中 C 的个数 if (c 0) continue; int cur dp[i-1][a][b]; if (!cur) continue; // 保留 s[i] if (s[i] A) { dp[i][a1][b] (dp[i][a1][b] cur) % MOD; } else if (s[i] B) { dp[i][a][b1] (dp[i][a][b1] cur) % MOD; } else { dp[i][a][b] (dp[i][a][b] cur) % MOD; } // 改成其他字符 if (s[i] ! A) { dp[i][a1][b] (dp[i][a1][b] cur) % MOD; } if (s[i] ! B) { dp[i][a][b1] (dp[i][a][b1] cur) % MOD; } if (s[i] ! C) { dp[i][a][b] (dp[i][a][b] cur) % MOD; } } } } int ans 0; for (int a 0; a n; a) { for (int b 0; a b n; b) { int c n - a - b; if (max({a, b, c}) - min({a, b, c}) 1) { ans (ans dp[n][a][b]) % MOD; } } } printf(%d\n, ans); return 0; }这段代码里c i - 1 - a - b是前 i-1 个字符中 C 的个数用来判断当前状态是否合法c 不能为负。但实际写的时候因为循环条件a b i已经保证了 ab ≤ i而 c i-1-a-b 可能为负所以需要if (c 0) continue;。这个判断不能省否则会访问非法状态。4.2 空间优化与滚动数组上面的代码用了三维数组空间约 155×155×155×4 字节 ≈ 14.9 MB在一般竞赛环境256MB下没问题。但如果想更省可以用滚动数组把第一维压掉因为 dp[i] 只依赖 dp[i-1]。压掉后空间降到 155×155×4 ≈ 96 KB几乎可以忽略。滚动数组的写法要注意每一层 i 开始前要把 dp[a][b] 清零或者用两个数组交替。我习惯用dp[2][155][155]用i 1索引当前层和上一层。这样写起来稍微绕一点但省内存效果明显。不过对于 n150 这个规模其实没必要三维更直观不容易出错。4.3 模数陷阱与溢出防范模数 51123987 大约是 5.1e7两个这样的数相加约 1.02e8在 int 范围内2.1e9所以用 int 存 dp 值没问题。但如果你用dp[i][a1][b] cur然后最后取模多次累加可能溢出。稳妥做法是每次加法后立即取模就像上面代码那样。另外max({a, b, c})用了初始化列表需要 C11 及以上。如果比赛环境老可以手写max(a, max(b, c))。这个细节虽小但编译错误会浪费很多时间。5. 常见问题与调试技巧实录5.1 答案偏小漏算最终状态这是最常见的错误。很多人只检查 abc 的情况忽略了 n 不是 3 的倍数时还有两个合法状态。比如 n4合法的是 (2,1,1)、(1,2,1)、(1,1,2)如果你只取 (1,1,1) 那个但 1113≠4根本不存在答案就是 0。正确做法是遍历所有 a、b算出 c检查极差。我当年写了个测试n1原串 A。合法状态是 (1,0,0)、(0,1,0)、(0,0,1)极差都是 1。原串 A 保留就是 (1,0,0)改成 B 是 (0,1,0)改成 C 是 (0,0,1)共 3 种。如果你的代码输出不是 3那最终状态统计肯定有问题。5.2 答案偏大重复计数重复计数通常来自转移时把“保留”和“改成相同字符”搞混了。比如 s[i] 是 A你写“改成 A”又算了一种那就多算了。记住保留就是保留改就是改成另外两种不能改成自己。上面的代码用if (s[i] ! A)来避免改成自己这个判断很关键。还有一种重复是状态定义不清导致的。比如你用 dp[i][a][b][c] 但没保证 abci那同一个最终串可能被多条路径到达。用和约束消维后这个问题自然消失。5.3 调试技巧小规模暴力对拍写完后别急着提交。写一个暴力枚举程序对于 n ≤ 8 的小串枚举每个位置改成什么3 种选择生成所有最终串检查平衡条件计数。然后和你的 DP 输出对比。我当年就是用这个方法发现模数写错的——暴力不取模DP 取模小数据下两者应该相等不等就说明 DP 逻辑有问题。对拍时注意暴力也要考虑“保留”和“改成其他”的区别但本质上每个位置有 3 种选择保留原字符、改成另外两种之一所以总方案数是 3^n。n8 时 3^86561完全跑得动。5.4 常见问题速查表问题现象可能原因排查方法答案偏小最终状态漏算打印所有合法 (a,b,c) 组合检查是否都累加答案偏大转移重复计数检查“保留”和“改成自己”是否重复样例过但 WA模数写错确认模数是 51123987 而非 1e97运行超时状态未剪枝检查循环边界ab≤i 是否写对数组越界c 为负未判断加if (c 0) continue;编译错误max 初始化列表改用max(a, max(b, c))6. 从 Balance 到同类问题的通用思路6.1 计数类 DP 的通用框架CF_17C 这类题本质是“给定操作统计达到目标状态的方案数”。通用框架是定义状态表示“处理到哪、当前计数如何”转移表示“这一步做什么选择”最终统计“满足目标条件的状态”。这个框架可以套用到很多题上比如“把字符串改成回文串的方案数”“把数组改成非递减的方案数”等。关键区别在于目标条件的复杂度。Balance 的目标是三个计数极差 ≤ 1比较简单有些题目标条件是“任意前缀和 ≥ 0”那就需要额外记录前缀和。但状态设计的思路是一样的把影响目标判断的所有量都放进状态里能消维就消维。6.2 平衡类问题的变体如果把字符集从 3 个扩大到 k 个平衡条件变成“任意两个计数差 ≤ 1”那合法状态就是所有计数要么都是 floor(n/k)要么部分是 floor(n/k)1。状态数会变成 k 维但同样可以用和约束消掉一维。n150、k4 时状态数约 150^33.4M还是可做的。但如果 k 很大就需要更高级的技巧比如生成函数或组合数学。另一个变体是允许删除和插入操作。那长度会变状态里还要记录当前长度复杂度上升。不过核心思想不变跟踪各字符计数保证最终平衡。6.3 实操心得先想清楚再写代码我带了这么多届学生发现一个规律卡题的人往往不是不会写代码而是没想清楚状态和转移就动手。CF_17C 的代码不到 50 行但想清楚状态设计可能需要半小时。我的建议是先在纸上画出 dp 表的前几行手动推几个转移确认无误后再写代码。这样比对着屏幕干想效率高得多。另外模数、边界、循环顺序这些细节最好在写代码前就列个清单写完逐项检查。我自己的清单是模数对不对边界初始化对不对循环范围对不对最终统计全不全这四个问题问完基本不会出大错。7. 我个人在实际操作中的体会这道题我前前后后做了三遍。第一遍用三维 DP样例过了但提交 WA查了一晚上发现是最终状态漏了一个。第二遍改用二维又因为模数写成 1e97 挂了。第三遍才把所有坑填完AC 的那一刻其实没什么兴奋更多的是“终于把该想的都想清楚了”的踏实。后来我总结这类计数 DP 最怕的就是“想当然”。你觉得最终状态只有一种其实有三种你觉得模数是常见的其实是个冷门数你觉得 c 不会为负其实循环边界没卡死。每一个“你觉得”背后都可能是一个 WA。所以我现在写这类题都会强迫自己把每个假设写下来然后逐一验证。如果你也在刷这道题或者被类似的平衡计数问题卡住我的建议是别急着看题解先自己把 n1 到 n6 的所有情况手算一遍列出所有合法最终串和方案数然后再去对 DP。这个过程很慢但走完一遍你对状态设计的理解会深很多。题解只能告诉你“怎么做”手算才能让你明白“为什么这么做”。最后分享一个小技巧如果你不确定最终状态有哪些可以写个程序枚举所有 a、b、c 满足 abcn 且极差 ≤ 1打印出来。n150 时这个枚举瞬间完成比手算靠谱。这个技巧在比赛时也能用相当于给自己写了个“目标状态生成器”省得漏算。