九月那场 GESP 六级考完走出考场时很多人都在说 T1 简单但分数出来以后发现并不是所有人都拿到了这几分。问题往往不是代码不会写而是把题目读成了自己想象中的样子或者在最后一段、字符范围这些地方翻了车。T1 的“划分字符串”这类题六级的考点从来不是高级算法而是你能不能把一个字符串划分条件和最优化目标理清楚然后把边界全部接住。这篇文章我把这类题的完整解题路径拆一遍从读题、模型判断、贪心写法、动态规划写法一直到考场上的坑点都会给到可复现的代码和验证方法。适合正在备考 GESP 六级、想把第一批基础分拿稳的同学参考。1. 先别急着写代码把“划分条件”从题面里完整剥出来“划分字符串”在六级真题里有很多变体常见的有按不同字符个数限制来分段、按相邻字符关系来分段、按回文段来分段、按权值和来分段。无论哪一种第一步都是把题面里的三个隐藏信息找全划分对象是什么、每个段要满足什么条件、最终要最大还是最小。1.1 这类题最容易漏掉的信息点以我这些年看过的备考代码为例最容易漏的是“连续子串”这个限定。字符串划分和子序列划分完全是两回事连续子串意味着切割点只能在字符之间的位置不能跳着选字符。第二个容易漏的是段是否允许为空大多数题默认划分出的每一段都是非空连续子串但少数题目会用“可以把字符串划分成若干子串”这种含糊说法此时空段要单独判掉。第三个容易漏的是目标方向是求“最多能分成几段”还是“最少能分成几段”方向不同贪心策略和 DP 状态都可能完全不同。还有一类信息容易被忽略字符集范围。题面如果只说了“字符串”没有说明只含小写字母那你写cnt[26]就有风险。六级题目经常卡这个我在第 4 章会专门讲。1.2 一个常见的六级 T1 问法还原基于往年六级序列题的风格“划分字符串”作为 T1 时最常出现的模型是这样描述的给定一个只含小写字母的字符串s要求把它划分成若干连续子串使得每个子串中不同字符的种数都不超过一个给定整数k。求最少能划分成几段。这个模型有个好处它不涉及复杂数据结构但很考验对贪心正确性的判断。我们先用样例走一遍思路。假设s abacbec,k 2。我们沿字符串从左往右看想让每个段内不同字符不超过 2 种。最直观的做法是当前这一段能收字符就尽量收一旦新字符会把段内不同字符数撑到 3就必须在这里切一刀。按这个规则切分的结果是第一段aba段内字符集合是{a, b}共 2 种合法碰到下一个字符c如果继续收这一段会变成{a, b, c}共 3 种超限所以在c前切一刀第二段从c开始收cb的字符集合是{c, b}合法碰到e撑成 3 种再切第三段ec合法。答案就是 3。你可能会想是不是存在更聪明的切法让总段数更少我们试一下 2 段是否可行前一段不管怎么短后一段剩下的位置有限。比如切ab | acbec第二段有{a,b,c,e}共 4 种超限切aba | cbec第二段也有{b,c,e}共 3 种还是超限。所以 3 段确实是最少。这个“尽量往后收收不下再切”的直觉就是解这道题的贪心策略。2. 贪心还是双指针先判断模型再决定写法看到“最少段数”别急着套 DP。六级 T1 这类题大多数情况下贪心就是最优解但你需要能解释清楚为什么而不是凭感觉选一个看起来对的策略。2.1 判定一条贪心路径是否成立的通俗方法一个非常朴素的判断方法是看“能不能交换”。假设当前段已经装了k种不同字符下一个新字符c一进来就会变成k1种。此时你必须在c前面的某个位置切一刀。问题是怎么选切割点。如果你把切割点往前移让当前段提前结束那么后缀就会变长。可是当前段里提前放出去的那些字符对后缀没有任何帮助它们既不能降低后缀的字符种类数也不能让后缀的段变少。反过来把切割点尽可能往后挪当前段吃到最多的合法字符后缀最短后续需要处理的字符最少。因此“在第一个会超限的字符前切”这种策略不会比任何其他策略差。这就是典型的“能多装就多装装不下再另起一段”的交换论证思路。这个策略对“最少段数”成立对“最大段数”则不成立。如果题目反过来问“最多能分成多少段”答案几乎就是字符串长度因为单字符段一定合法这时候贪心逻辑就完全变了。所以读题阶段确认目标方向非常重要。2.2 双指针实现数组计数比哈希表更适合考场有了策略实现就很简单了。用cnt[ch]记录当前段里每个字符的出现次数用distinct记录当前段有几种不同字符。遍历一遍字符串遇到字符ch如果cnt[ch] 0说明段里要引入一个新种类distinct加 1如果distinct k说明当前段已经装不下了在ch之前切一刀然后重置计数最后无论是否切段都要把cnt[ch]加 1。完整代码可以写成#include bits/stdc.h using namespace std; int main() { ios::sync_with_stdio(false); cin.tie(nullptr); string s; int k; cin s k; vectorint cnt(256, 0); int distinct 0; int ans 1; for (char rawCh : s) { unsigned char ch static_castunsigned char(rawCh); if (cnt[ch] 0) { if (distinct k) { // 当前段已经满了出现新字符必需切段 ans; fill(cnt.begin(), cnt.end(), 0); distinct 0; } distinct; } cnt[ch]; } cout ans \n; return 0; }这里要注意ans的初始值是 1因为即使只有一个字符的字符串也是一个段。当k小于实际唯一字符数时每次“切段”才让ans加 1。遍历结束后不需要再加一次否则会多算最后一段。这段代码的时间复杂度是O(n)空间复杂度是O(1)因为计数数组大小固定。六级数据量如果给到10^5甚至10^6这个写法都能稳过。2.3 空段和 k 的边界怎么处理k 0时任何非空段都会包含至少一种字符因此无法完成划分这种题面基本不会出现因为题目要求一定有解。但如果你在自测时遇到可以直接判k 0输出-1或按题面约定处理。k大于等于字符串不同字符数时整串直接当一段答案是 1。这两个边界写进自测清单考场就不用慌。3. 用动态规划视角再看一遍为什么最优会收敛成贪心很多复习资料会把这类题归到“字符串 DP”里因为一旦加一点变化比如每个段的权值不同或者不是求段数而是求某种分数最大化贪心就不一定成立了。所以我把 DP 写法也完整讲一遍这样你遇到变式时能接得住。3.1 DP 状态的经典定义设dp[i]表示s的前i个字符最少能划分成多少段。这里i从 1 开始编号。转移时枚举最后一段的起点j只要s[j..i]这段内不同字符种数不超过k就可以从dp[j-1]转移过来dp[i] min(dp[i], dp[j-1] 1)朴素实现需要把每个i都往前枚举j同时还要快速统计s[j..i]的字符种数复杂度最高能到O(n^2)。如果六级 T1 的n只在10^3以下这个写法也能混到分但如果n是10^5就会超时。3.2 维护滑动窗口左端点DP 立刻变 O(n)这里有一个很有意思的观察对于“最少段数”dp[i]随着i增大是非递减的。你想一下一个更长的前缀至少不可能比短前缀划分出更少的段因为短前缀已经要那么多段了加字符只会变多变难。于是若left是满足s[left..i]不超过k种字符的最小起点那么可选转移里j-1最小对应的前缀也最短dp[j-1]也最小。换句话说dp[i] dp[left-1] 1所以只需要用一个滑动窗口维护left。只要窗口内的不同字符数大于k就把窗口左端点右移同时更新计数。这个left在整个扫描过程中只会向右移动所以总复杂度是O(n)。实现如下int minPartitionsDP(const string s, int k) { int n s.size(); vectorint dp(n 1, 0); vectorint cnt(256, 0); int left 1; int distinct 0; for (int i 1; i n; i) { unsigned char ch static_castunsigned char(s[i - 1]); if (cnt[ch] 0) distinct; cnt[ch]; while (distinct k) { unsigned char leftCh static_castunsigned char(s[left - 1]); cnt[leftCh]--; if (cnt[leftCh] 0) distinct--; left; } dp[i] dp[left - 1] 1; } return dp[n]; }这个 DP 版本和贪心版本本质上算的是同一个东西但它的扩展性好很多。比如把目标改成“划分后每个段有一个权值求权值和最大”你在dp[i] dp[left-1] 1这里就不能直接用最小值而需要配合单调队列、线段树一类工具继续优化。理解了这层关系你就知道考场上为什么可以先写贪心拿满分而不是被“这题是不是 DP”卡住。3.3 几个常见的变式提醒“划分字符串”家族在六级里还可能换成这些问法每个段内的字符必须互不相同且同一个字符不能出现在两个不同段中。这种是“标签划分”模型要用字符最后一次出现位置来切而不是简单的滑动窗口。每个段必须是非递减字典序字符串求最多能分多少段。这种变成比较相邻字符段与段之间按字典序比较处理起来又不一样。每个段必须是某个模式串的排列求最小划分段数。这种需要统计字符频次本质是哈希 贪心。一旦你意识到“划分字符串”只是一个题目家族而不是一道具体的题复习时就不会把时间花在背代码上而是花在判断模型上。4. 考场上最容易翻车的四个地方边界、字符集、substr 和多组数据我见过太多代码思路完全正确、最后因为小地方丢分的案例。下面这四个地方是 T1 高频翻车点考前务必自己动手踩一遍。4.1 最后一段的结算逻辑很多人的第一反应是“当前段满了就ans遍历结束后再ans补上最后一段”。这个写法在字符串恰好完整地被切成整数段时会多算一个空段。比如s ab,k 1段内不同字符不超过 1 种时最少分 2 段。如果只在“超限”时加段遍历过程遇到b时a段要切ans变成 2遍历结束再补一次就变成 3。正确写法是ans初始为 1只有发生切割才自增最后不用补段。你也可以反过来写代码最后无条件ans但初始值改为 0关键是两种写法要自洽不要混着来。4.2 字符集范围cnt[26]能不能用先看题面题面说“只含小写字母”cnt[26]配合ch - a没问题。但如果字符串可能包含大写字母、数字甚至空格就必须把计数数组开到 256。更稳妥的做法是直接用cnt[128]或cnt[256]并且把字符转成unsigned char再当下标。C 的char是不是有符号由编译器决定如果平台上char是有符号的直接用char做下标遇到 ASCII 码大于 127 的字符会得到负数下标程序可能直接越界崩溃。写成unsigned char ch s[i];这种形式能避开绝大多数隐患。遇到中文等多字节字符那就别用数组了直接上std::map或unordered_map统计种类数。4.3 循环里频繁 substr 是性能杀手有些同学写划分题时喜欢用s.substr(left, len)把当前段拿出来再统计这段的字符。这个做法在数据小时问题不大一旦n到10^5每次substr都创建新字符串底层还有拷贝最坏情况会变成O(n^2)。正确做法是只维护下标和计数数组需要统计字符时直接通过下标访问原字符串不要复制字符串本身。记住划分题里你要操作的是“边界”和“计数”不是字符串实体。4.4 多组测试数据的计数数组清零六级机考常常是多组输入最后一组数据读完后才结束。每组数据之间如果不清空计数数组上一组残留的频次会污染下一组。要么每组开头用fill(cnt.begin(), cnt.end(), 0)要么把计数数组定义在循环内部。注意memset(cnt, 0, sizeof(cnt))也可以但务必确认cnt是数组而不是指针否则sizeof会得到指针大小那是经典 bug。刷题平台对输出格式也很严格每组答案一行样例里没有额外空行就不要在输出里加。5. 把“划分字符串”练成送分题的三个习惯最后一个部分我想分享一些训练方法。这些方法不是针对某一道题的而是让你在考场上一看到字符串划分就能快速进入稳定状态。5.1 先写一个暴力版再用它验证贪心策略你不需要每次比赛都写暴力但平时练习必须写。比如你可以先写一个最普通的O(n^2)DPvectorint brute(n 1, 1e9); brute[0] 0; for (int i 1; i n; i) { for (int j 1; j i; j) { // 统计 s[j-1..i-1] 的不同字符数 unordered_setchar st; for (int p j - 1; p i; p) st.insert(s[p]); if ((int)st.size() k) { brute[i] min(brute[i], brute[j - 1] 1); } } }然后把贪心代码和暴力代码放到同一个程序里用随机生成的小写字母串和随机k对拍。如果跑上几千组数据结果完全相同你对贪心的信心会强很多。这个对拍习惯比背任何模板都实用。写对拍时注意用随机种子固定便于复现失败用例。5.2 考场时间分配T1 别抢跑先列极端样例T1 在整张试卷里分数占比不小但它再简单也要花时间验证边界。我的习惯是拿到题先不动键盘在草稿纸上写五个样例长度为 1 的字符串、全部字符相同的字符串、全部字符都不同的字符串、k1的字符串、字符集里同时包含大写小写数字的字符串。把这五个样例在纸上跑通思路再开始写代码。这样做的成本只有两三分钟收益是基本消灭低级错误。5.3 在 VSCode 里配置好断点单步调试字符串边界很多同学备考六级用的是 VSCode 加 g 环境。这类题的调试重点不是看整个数组而是看left指针和distinct值的变化。比如k2字符串abacbec你单步到第 3 个字符a时应该确认distinct没有增长因为a已经在段里出现过到第 4 个字符c时distinct变成 3触发切段。这种通过断点盯变量的方式能让你直观体会到滑动窗口的边界移动规律。我的个人经验是字符串划分题最怕的不是不会算法而是“觉得自己会了但一跑边界就炸”。如果你能在考前把上面这些坑全部自测一遍再把贪心模型的正确性用自己的话讲给别人听六级 T1 这几分基本就算装进口袋了。真正考试时哪怕代码写得慢一点也比写错重来快得多。