1. 项目概述与问题拆解最近在刷蓝桥杯的历年真题碰到了这道P12143“好串的数目”题目本身描述不算复杂但想拿满分尤其是面对n最大到10^5的数据规模暴力枚举肯定是行不通的。这道题本质上是一个字符串计数问题但它的“好串”定义有点意思不是简单的回文或者单调而是要求能拆分成两个“连续非递减子串”。很多同学第一眼看到这个定义可能会有点懵不知道从何下手。我花了些时间研究把几种主流的解法都实现和对比了一遍从最直观的O(n²)暴力法到利用双指针的O(n)线性扫描再到需要一点动态规划思维的O(n)解法。这篇文章我就来详细拆解一下这道题的解题思路特别是如何从暴力法优化到高效算法并给出完整的C实现代码和详细的注释。无论你是正在备赛蓝桥杯、信奥赛的选手还是单纯对算法优化感兴趣的朋友相信都能从中获得启发。2. 核心概念解析与暴力思路2.1 什么是“好串”题目对“好串”的定义是这道题的核心也是我们设计算法的出发点。我们再来仔细咀嚼一下这个定义单字符子串一定是好串这个很好理解长度为1的子串它自己就是自己天然满足条件。这为我们提供了一个基础的计数起点。长度大于1时可以拆分为两个连续非递减子串这是关键。它不是说整个子串本身是连续非递减的而是说存在一种拆分方式使得这个子串能被切成前后两段每一段自己内部是“连续非递减”的。那么什么是“连续非递减子串”呢题目也给出了明确定义对于子串中的每一个位置ii0当前字符s[i]必须等于前一个字符s[i-1]或者等于s[i-1] 1即ASCII码值加1对于数字字符就是数值加1。例如12233 1-21 2-2相等 2-31 3-3相等。满足。456 4-51 5-61。满足。135 1-32不满足差值超过1。988 9-8-1不满足递减了。所以“连续非递减”意味着相邻字符的差值只能是0或1并且不能减少。2.2 最直接的暴力法O(n²)拿到问题最朴素的想法就是枚举所有可能的子串然后对每个子串检查它是否是好串。枚举所有子串对于一个长度为n的字符串子串总数是n*(n1)/2大约是O(n²)级别。检查一个子串如何检查一个子串s[l...r]是否是好串如果长度len r-l1 1直接返回true。如果长度大于1我们需要找到那个“拆分点”。假设我们在位置kl k r处拆分得到前一段s[l...k]和后一段s[k1...r]。我们需要检查是否存在这样一个k使得前后两段各自都是“连续非递减”的。检查一段子串是否为“连续非递减”是O(len)的。那么对于一个长度为L的子串我们需要枚举L-1个可能的拆分点对每个拆分点检查两段最坏情况下的复杂度是O(L²)。再结合外层枚举所有子串总复杂度会达到惊人的O(n⁴)这显然不可行。我们需要一个更聪明的暴力法。注意到“连续非递减”这个性质具有传递性。我们可以先预处理出一些信息。一个O(n²)的可行暴力思路 我们可以用动态规划的思想预处理一个二维表valid[i][j]表示子串s[i...j]是否是“连续非递减”的。但这样预处理本身就需要O(n²)的时间并且需要O(n²)的空间对于n10^5空间直接爆掉需要约10^10的存储单元。因此更实际的暴力法是对于每个起始位置i我们尝试向右扩展结束位置j并在此过程中维护信息。但即便如此最坏情况仍然是O(n²)。对于n10^3或许能过但对于10^5必然超时。注意在竞赛中即使知道暴力法过不了所有数据先写出一个正确的暴力版本进行测试和对拍与高效算法对比结果也是非常重要的步骤。它可以验证我们对题意的理解是否正确并为优化提供思路。3. 高效算法设计双指针与贡献值计算要处理n10^5的数据我们的算法复杂度必须控制在O(n log n)甚至O(n)。这就需要我们深入挖掘“好串”的性质避免枚举所有子串。3.1 关键性质挖掘我们重新审视“好串”的定义一个子串是好串当且仅当它能被拆分成两个连续非递减子串。让我们考虑一个固定的起始位置i。我们从i开始向右看能构成好串的结束位置j有什么规律假设我们从i开始维护两个指针p1和p2或者想象我们在扩展这个子串。首先我们希望找到从i开始的最长连续非递减前缀记其结束位置为end1。也就是说s[i...end1]是连续非递减的并且end1是满足这个条件的最大下标。接着从end11开始我们继续寻找第二个连续非递减段记其结束位置为end2。同样s[end11...end2]是连续非递减的且end2最大。那么对于起始位置i所有以i开头的好串其结束位置j必须满足i j end2。但这还不够因为好串要求整个子串能拆分成两段所以j不能超过第二段的结束位置end2。更重要的是j可以取哪些值呢当j位于第一段内即i j end1时由于单字符子串是好串所以这些j都对应一个好串直接把s[i...j]本身视为第一段第二段长度为0不题目要求长度大于1时要拆分成两段。所以当j i且j end1时我们可以将拆分点设在j处但这样第二段就为空了题目没有明确说第二段能否为空。回顾定义“拆分为两个连续非递减子串”。通常理解两个子串都应该非空否则“拆分”的意义就不大了。我们结合样例检查一下。让我们用样例s12258i0字符1来验证。从i0开始的最长连续非递减前缀是122对应end12下标从0开始。第二段从下标3开始5最长连续非递减段是58对应end24。 现在看以i0开头的好串j0:1长度1是好串。j1:12可以拆成1和2都是连续非递减是好串。j2:122可以拆成12和2或者1和22是好串。j3:1225可以拆成122和5是好串。样例中也有j4:12258可以拆成122和58是好串吗检查第一段122是连续非递减第二段585-83不是连续非递减所以12258不是好串。实际上整个串12258本身也不是连续非递减的2-53。这里发现一个关键点整个子串s[i...j]要成为好串不仅需要存在一个拆分点k使得前后两段各自连续非递减更重要的是这个拆分点k必须恰好是前后两段“连续非递减性质”的断点。也就是说在位置k处前后字符的关系破坏了我们定义的“连续非递减”规则即s[k]到s[k1]的差值既不是0也不是1或者甚至是递减的。只有这样拆分才有意义。因此更准确的算法思路是寻找所有的“断点”。所谓断点就是位置pos满足s[pos]到s[pos1]不满足连续非递减关系即差值大于1或为负。对于一个好串它最多只能包含一个这样的“断点”并且这个断点就是它的拆分点。因为如果包含两个断点那么无论如何拆分都会有一段内部包含断点从而不是连续非递减的。3.2 线性扫描算法双指针/滑动窗口基于上述分析我们可以设计一个O(n)的算法预处理断点遍历一次字符串记录所有不满足s[i] s[i-1]且s[i] s[i-1]1的位置。也就是说记录所有i其中1 i n且(s[i] - s[i-1]) ! 0 (s[i] - s[i-1]) ! 1。实际上就是s[i] - s[i-1] 1 || s[i] - s[i-1] 0。我们把这些位置i即断点开始的位置存到一个数组break_points中。注意断点是相邻字符对(i-1, i)我们通常记录i作为断点位置。计算贡献现在整个字符串被这些断点分割成了若干个“连续非递减段”。设这些段为seg[0], seg[1], ..., seg[m-1]每个段seg[k]的长度为len_k。单独一个段seg[k]内部任意子串如果完全包含在该段内并且不跨段那么它本身就是一个连续非递减串。但是题目要求的好串是可以拆分成两个连续非递减子串这意味着好串必须恰好跨越两个段或者在一个段内但以某个点为界拆分成两个都连续非递减的部分在一个连续非递减段内任意位置拆分前后两段自然也都是连续非递减的。所以一个完整的连续非递减段内部的所有长度大于1的子串也都是好串因为它可以在任意位置拆分。例如1223拆成12和23122和3等都满足。因此好串的来源有两类A类完全位于同一个连续非递减段内部长度1。这样的子串有多少对于一个长度为L的段长度大于1的子串数量为L*(L-1)/2。B类跨越两个相邻的连续非递减段即包含且仅包含一个断点。设前一段seg[k]长度为L1后一段seg[k1]长度为L2。那么所有以seg[k]中某个位置开头以seg[k1]中某个位置结尾并且包含中间那个断点的子串都是好串。这样的子串数量是L1 * L2。因为起点可以在前一段的L1个位置中任选终点可以在后一段的L2个位置中任选。汇总结果总的好串数目 所有段的A类贡献之和 所有相邻段对的B类贡献之和 长度为1的子串总数n个。算法步骤细化初始化total n。 // 先加上所有长度为1的子串遍历字符串找出所有的连续非递减段并记录每个段的长度。用start表示当前段的起始下标。从i1开始遍历如果s[i] - s[i-1] 0 || s[i] - s[i-1] 1则继续。否则遇到断点。此时一个段结束区间为[start, i-1]长度为len i - start。A类贡献total len * (len - 1) / 2。记录前一段长度prev_len len用于后续计算B类贡献。更新start i开始新的段。循环结束后处理最后一个段。假设最后一个段区间为[start, n-1]长度为len。A类贡献total len * (len - 1) / 2。最后一个段没有后续的段与之形成B类贡献。计算B类贡献我们需要在遍历过程中记录每一段的长度。更简单的方法是在步骤2中每结束一段如果这不是第一段我们就可以计算它和前一段形成的B类贡献total prev_len * len其中prev_len是前一段的长度len是当前段的长度。我们需要用一个变量prev_len来记录前一段的长度初始为0表示还没有前一段。让我们用样例s12258验证一下 字符串1 2 2 5 8差值 1, 0, 3, 3 断点出现在下标2和3之间2-53以及下标3和4之间5-83不仔细看s[2]2,s[3]5, 差值为3是断点。s[3]5,s[4]8, 差值也是3是断点。所以断点位置是i3和i4。 那么连续非递减段被分割为 段0:[0,2]-122, 长度L03。 段1:[3,3]-5, 长度L11。 段2:[4,4]-8, 长度L21。计算贡献长度1子串 total 5。A类贡献段内长度1子串段0: L03, 贡献 3*2/2 3。 (对应12,22,122? 等等122长度是3它也是好串吗是它可以拆成12和2。段内所有长度1的子串确实都是好串。段0长度3长度1的子串有[0,1](12),[1,2](22),[0,2](122)。共3个。正确。段1: L11, 贡献0。段2: L21, 贡献0。 total 3 8。B类贡献跨越相邻段段0和段1: L0 * L1 3 * 1 3。这些子串是起点在段0(3个选择)终点在段1(1个选择)即[0,3](1225),[1,3](225),[2,3](25)。其中252-5不是连续非递减但它是好串吗检查25可以拆成2和5两段各自连续非递减所以是好串。225拆成22和5是好串。1225拆成122和5是好串。都对。段1和段2: L1 * L2 1 * 1 1。对应子串[3,4](58)。58可以拆成5和8是好串。 total 3 1 12。结果total12与样例输出一致。再验证样例s97856: 字符串9 7 8 5 6差值 -2, 1, -3, 1 断点i1(9-7), i3(8-5) 段0:[0,0](9), L01 段1:[1,2](78), L12 段2:[3,4](56), L22 计算total 5。A类贡献段0: 0段1: 2*1/21 (子串78)段2: 2*1/21 (子串56) total 2 7。B类贡献段0段1: 1*22 ([0,1](97),[0,2](978))段1段2: 2*24 ([1,3](785),[1,4](7856),[2,3](85),[2,4](856)) total 6 13。结果正确。3.3 算法复杂度分析时间复杂度我们只需要一次线性扫描字符串找出所有段并计算长度过程中进行简单的算术运算。时间复杂度为O(n)。空间复杂度我们只需要常数个额外变量如start,prev_len,total,current_len等空间复杂度为O(1)。这个算法高效且优雅地解决了问题。4. C代码实现与逐行解析理解了算法代码实现就相对直接了。这里给出两种风格的实现一种是清晰易读的版本另一种是稍微紧凑的版本。我们以清晰版本为主进行讲解。#include iostream #include string using namespace std; int main() { string s; cin s; int n s.length(); long long total n; // 使用long long防止溢出n最大1e5结果可能接近n^2量级5e9int会溢出 int start 0; // 当前连续非递减段的起始下标 int prev_len 0; // 前一个连续非递减段的长度用于计算跨越两段的子串数 long long segment_count 0; // 当前段的长度临时计算用 // 遍历字符串识别连续非递减段 for (int i 0; i n; i) { if (i start) { // 每个段的第一个字符直接开始计数 segment_count 1; } else { int diff s[i] - s[i - 1]; if (diff 0 || diff 1) { // 仍然满足连续非递减条件当前段延长 segment_count; } else { // 遇到断点当前段结束 // 1. 计算当前段内部的A类贡献长度大于1的子串数 C(segment_count, 2) if (segment_count 1) { total segment_count * (segment_count - 1) / 2; } // 2. 计算当前段与前一段之间的B类贡献 if (prev_len 0) { // 如果存在前一段 total (long long)prev_len * segment_count; } // 3. 更新前一段长度并开始新的段 prev_len segment_count; start i; segment_count 1; // 新段从当前字符开始长度为1 } } } // 循环结束后处理最后一个段 // 1. 最后一个段内部的A类贡献 if (segment_count 1) { total segment_count * (segment_count - 1) / 2; } // 2. 最后一个段与前一段的B类贡献 if (prev_len 0) { total (long long)prev_len * segment_count; } cout total endl; return 0; }代码关键点解析数据类型total使用long long。因为n最大为1e5好串数量最大可能是所有子串的数量约5e9这超过了int的表示范围约21亿。使用long long是竞赛中处理大数结果的常见做法。变量含义start记录当前考察的连续非递减段的起始下标主要用于逻辑划分在最终计算中未直接使用。prev_len记录刚刚结束的那个连续非递减段的长度。初始为0表示还没有“前一段”。segment_count记录当前正在扩展的连续非递减段的长度。核心循环逻辑遍历每个字符i。如果i是当前段的起始位置i start则初始化segment_count1。否则计算当前字符与前一个字符的差值diff。如果diff为0或1说明连续非递减性质保持当前段长度segment_count加1。如果diff不满足条件即diff ! 0 diff ! 1或者说diff 1 || diff 0说明遇到了“断点”。此时当前段[start, i-1]结束其长度为segment_count。计算A类贡献如果该段长度大于1则其内部长度大于1的子串数为C(segment_count, 2) segment_count * (segment_count - 1) / 2加到total。计算B类贡献如果存在前一段prev_len 0则跨越前一段和当前段的子串数为prev_len * segment_count加到total。注意这里乘法可能溢出需要强制转换为long long。更新状态将当前段的长度segment_count赋给prev_len作为下一段的前一段。然后重置start i并设置segment_count 1开始新的一段。循环后处理循环结束时最后一段还没有被处理。我们需要对最后一段重复上述的A类和B类贡献计算。输出结果输出total。紧凑实现版本 有些选手喜欢更简洁的写法下面是一种逻辑等价但更紧凑的实现#include iostream #include string using namespace std; int main() { string s; cin s; int n s.size(); long long ans n; // 单字符子串 long long current_len 1; // 当前连续非递减段的长度至少为1 long long prev_len 0; // 上一个连续非递减段的长度 for (int i 1; i n; i) { int diff s[i] - s[i - 1]; if (diff 0 || diff 1) { current_len; } else { // 段结束 if (current_len 1) ans current_len * (current_len - 1) / 2; if (prev_len 0) ans prev_len * current_len; prev_len current_len; current_len 1; // 新段从i开始长度为1 } } // 处理最后一段 if (current_len 1) ans current_len * (current_len - 1) / 2; if (prev_len 0) ans prev_len * current_len; cout ans endl; return 0; }这个版本从i1开始遍历直接维护current_len逻辑更集中。5. 测试、调试与常见问题5.1 测试用例设计自己编写代码后需要用多种用例测试确保边界情况都覆盖到。最小输入n1。例如s0。答案应为1它自己。全连续非递减例如s12345。没有断点只有一个段长度L5。长度1子串5个。A类贡献C(5,2)10个12,23,34,45,123,234,345,1234,2345,12345。B类贡献0。总计15。用程序跑一下验证。全断点每两个字符都不满足条件例如s97531。每个段长度都是1有5个段。长度1子串5个。A类贡献0因为每个段长度都为1。B类贡献段0段1:1*11 (97), 段1段2:1 (75), 段2段3:1 (53), 段3段4:1 (31)。共4个。总计9。混合情况题目给出的两个样例。最大规模测试生成一个n100000的随机字符串用我们的O(n)算法应该能瞬间出结果。可以用暴力O(n²)算法对小规模n如n100验证结果一致性确保逻辑正确。5.2 常见错误与排查整数溢出这是最容易犯的错误。total、segment_count * (segment_count - 1) / 2、prev_len * segment_count这些计算的结果都可能超过int范围。务必使用long long。差值的计算s[i] - s[i-1]得到的是字符ASCII码的差值。因为题目保证是数字字符0到9所以直接相减得到的就是数字的差值。如果是其他字符则需要先转换。断点判断条件必须是diff 0 || diff 1才满足连续非递减。不能写成diff 0 diff 1因为diff可能是负数递减情况。也不能漏掉diff 0相等字符的情况。最后一个段的处理循环结束后一定要记得处理最后一段的贡献否则会漏算。prev_len的初始化初始应为0表示还没有“前一段”。这样在计算第一段的B类贡献时if (prev_len 0)条件为假不会进行错误的加法。段长度为1时的A类贡献长度为1的段其内部没有长度大于1的子串所以A类贡献为0。代码中通过if (segment_count 1)来判断。5.3 调试技巧打印中间变量在循环中打印i,diff,current_len,prev_len,ans的值对于小样例手动模拟看是否与预期一致。对拍写一个简单的暴力枚举程序双重循环枚举所有子串并检查是否是好串用于n较小如20的情况。用随机生成的字符串同时运行高效算法和暴力算法对比结果是否一致。这是验证算法正确性的黄金标准。边界测试专门测试n1, n2以及全递增、全递减、全部相等的情况。6. 算法思维延伸与总结这道“好串的数目”题目从暴力枚举到线性解法的优化过程体现了算法竞赛中常见的思维模式理解与转化首先必须彻底理解题目定义。将“好串”转化为“包含至多一个断点”的性质是解题的关键一步。这种将复杂条件转化为更易处理的计数性质的能力非常重要。分类计数转化后我们不是直接数“好串”而是数“段内子串”和“跨段子串”。分类讨论化整为零是计数问题的常用技巧。线性扫描与状态维护我们不需要保存所有段的信息只需要在扫描过程中维护当前段长度和前一段长度即可。这种“滚动”的思想节省了空间也简化了逻辑。贡献法计算每个“段”或“段对”对最终答案的贡献然后求和。这是许多子串计数问题的核心例如计算所有子串的和、乘积、某种属性等。回到这道题本身它的考点在于对“连续非递减”和“拆分”这两个条件的综合理解以及如何利用双指针/滑动窗口的思想在线性时间内统计满足条件的子串。它不像有些动态规划题那样有显式的状态转移方程但同样需要清晰的逻辑分析和问题分解能力。在竞赛中遇到类似“统计满足特定条件的子串数量”的题目可以先尝试寻找子串的公共特征或边界条件比如本题的“断点”尝试将子串的计数转化为对每个字符或每个位置“贡献”的计数或者转化为对若干“段”的组合计数。多练习这类题目对提升解题能力大有裨益。最后代码实现时务必注意数据范围和边界条件long long和循环结束后的处理往往是失分的陷阱。希望这篇详细的拆解能帮助你完全掌握这道题并在遇到类似问题时能够举一反三。