刷题打卡这件事难的不是某一天突然开窍而是每天都能坐下来把一道没见过的题啃完。到今天为止我打卡本上已经攒到第2892个记号这一题就是 P5181 GENIJALAC。说实话第一次看到这个题名我有点发怵COCI 的题经常把名字起得很抽象GENIJALAC 听起来像天才之类的东西题面的故事外壳也厚。但把它剥干净之后我发现它其实是一道特别典型的前缀和计数题非常适合用来复习 C 的常用容器和边界处理。这篇文章我就把从读题到 AC 的完整过程整理出来包括三种 C 写法的耗时对比以及三次提交才过的三个坑希望给同样在刷信奥的朋友省点时间。先说结论这题最后用到的核心算法只有一句话——把字符转成 1 和 -1用前缀和加历史计数统计所有前缀和相同的配对数量。接下来我按自己当时的思考顺序把整道题从头到尾拆开讲。1. 题意还原GENIJALAC 到底在问什么1.1 剥掉故事外壳后的等价模型COCI 的题特别喜欢把一个简单的算法问题包在故事里GENIJALAC 也不例外。原题的具体背景这里不重复了我读完题之后做的第一件事就是把所有修饰词全部去掉得到这样一个核心问题给定一个长度为 n 的序列序列中每个位置是一个二元标记只有两种取值。问一共有多少个连续区间使得区间内两种标记的数量相等n 的最大值在 1e6 这个量级输入就是一行长度为 n 的字符串字符只有两种比如 A 和 B。输出一个整数表示满足条件的区间数量。不同 OJ 上这道题的题面翻译可能有差异但如果你看到一个字符序列加上数合法连续段这样的要求那核心就是上面这个模型。做完题之后我把这个浓缩版题面记进了打卡本下次复习一分钟就能想起来。为了后面推导有抓手先拿一个极端简单的例子手算一遍。假设序列是 ABBA长度 4。我们手动数所有连续区间长度为 1 的区间A、B、B、A每种标记的数量不可能相等全部不合法长度为 2 的区间ABA1,B1合法、BB不合法、BAB1,A1合法长度为 3 的区间ABBA1,B2不合法、BBAB2,A1不合法长度为 4 的区间ABBAA2,B2合法。所以答案是 3。这个例子很小枚举能数出来但它已经告诉我们一个非常重要的信号合法区间一定都是偶数长度并且只有某些偶数长度成立。真正的问题是当 n 拉到 1e6 之后区间总数是 n(n1)/2约 5e11绝对不可能一个个枚举。1.2 数据范围就是出题人给你的提示信奥题有个很实用的判读技巧先看数据范围再决定算法方向。看到 n 是 1e6 这个级别我脑子里会立刻排除 O(n^2)、O(n^2 log n) 这一类方案然后锁定在 O(n) 或 O(n log n)。这一题没有修改操作只有静态查询那么大概率是一遍扫描能解决的题。很多同学看到区间就想着枚举左右端点或者套线段树其实都偏了。当合法条件是一个区间和等于某个值时第一反应应该是前缀和。为了把两种标记数量相等这个条件变成数字关系我做的第一步是编码把 A 记成 1B 记成 -1。这样一来一个区间 [l, r] 内 A 和 B 数量相等就等价于这个区间所有数的和等于 0。到这里问题就完整变成了另一道更经典的题统计和为 0 的连续子数组个数。这里多说一句很多同学不敢做这种抽象总觉得题目原本不是这么说的。其实竞赛题有多少故事外壳根本不重要重要的是对象是什么、条件是什么、要算什么。这三个问题想清楚代码往往非常简单。2. 从 O(n^2) 到 O(n)前缀和与哈希表的配合2.1 前缀和为什么天然适合连续段求和我们先定义前缀和数组 prepre[i] 表示序列前 i 个位置的和。因为 A1, B-1所以 pre[i] 实际就是前 i 个里 A 的数量减去 B 的数量。任意区间 [l, r] 的和可以写成 pre[r] - pre[l-1]当 l1 时左边是 pre[0]0。题目要求区间和为 0也就是pre[r] - pre[l-1] 0移项之后就是pre[r] pre[l-1]这句话说出来特别简单但信息量很大我们并不关心 l 具体是几只关心在遇到 r 之前有没有出现过同样的前缀和出现过多少次。有多少个这样的 l-1就有多少个以 r 结尾的合法区间。拿 ABBA 来验证。ABBA 对应的编码是 [1, -1, -1, 1]前缀和数组为pre[0] 0 pre[1] 1 pre[2] 0 pre[3] -1 pre[4] 0我们看到 pre[4]0而 pre[0]、pre[2] 也等于 0。以 4 结尾的合法区间有两个分别对应 l-10 和 l-12也就是区间 [1,4] 和 [3,4]这正好是 ABBA 全串和 BA 这一段。同理pre[2]0 和 pre[0]0 相等形成区间 [1,2]即 AB 这一段。三个区间全部对上。2.2 哈希表记录的是历史出现次数理解上面的关键等式之后维护方式就顺理成章了。我们需要一个哈希表 cntkey 是某个前缀和的值value 是这个前缀和已经出现过的次数。从头到尾扫描每一步做两件事当前前缀和是 pre先把 cnt[pre] 累加到答案里再把 cnt[pre] 加一表示这个前缀和又多出现了一次。第二件事为什么放在后面因为当前这个前缀和是刚刚产生的还没形成以当前位置结尾的合法区间所以不能先自增再统计。这个顺序如果写反了答案会凭空多出很多。操作的本质可以这样理解当我在位置 r 看到前缀和 pre[r] 时所有历史中出现的、和 pre[r] 相同的 pre[i-1]都会让区间 [i, r] 合法。所以把历史次数加进答案就是一次性统计了所有右端点在 r 的合法区间。2.3 为什么必须预置 cnt[0] 1刚开始写的时候最容易漏掉的就是初始化遍历前要把 cnt[0] 设置成 1也就是把 pre[0]0 这个虚拟位置先放进哈希表。想想看合法的区间有可能是从第 1 个位置开始的也就是 [1, r]。在这种区间里pre[r] - pre[0] 0所以 pre[r] 必须等于 pre[0] 0。如果我们没有提前把 0 放进哈希表那么在扫描到 r 的时候cnt[0] 是 0这个以 r 结尾、从左端点 1 开始的区间就永远数不进去。更直白地说前缀和数组里多了一个虚拟的第 0 项必须给它一个位置。我们在循环里只更新了 pre[1] 到 pre[n]但统计整个序列合法区间时一定不要忘记那个第 0 项。这个坑我第一次提交就直接吃了 WA。当时样例如果是一个以第 1 个字符开头的合法段输出就会比正确答案少 1如果有多个以 1 为左端点的合法区间差得更多。后面我会再讲一次因为它属于那种代码逻辑看着毫无问题但就是会错的典型。2.4 为什么不是排序也不是双指针有些同学看到相同的值配对会想到排序、双指针或者滑动窗口这里要特别说明一下为什么都不太行。排序会破坏区间原有的顺序信息。双指针通常适用于单调性比较明显的场景比如窗口内条件满足后扩展右端点和收缩左端点都有确定方向。但这里前缀和并没有单调性因为序列里同时有 1 和 -1前缀和会上下波动窗口并不满足右端点变远一定更难/更易满足的性质。哈希计数最大的优势是既不破坏顺序也不需要单调性只记录曾经出现过什么、出现过多少次。这种一边扫一边往历史里查的思路本质上是一种时间换空间的经典做法在竞赛里非常常用。3. 三种 C 写法的实测对比3.1 map 写法逻辑最直观但代价不小先说思维负担最小的写法。用 std::map 保存前缀和的次数因为 map 本身支持负数 key不需要处理偏移#include bits/stdc.h using namespace std; int main() { ios::sync_with_stdio(false); cin.tie(nullptr); int n; cin n; maplong long, long long cnt; cnt[0] 1; long long pre 0, ans 0; for (int i 1; i n; i) { char c; cin c; pre (c A ? 1 : -1); ans cnt[pre]; cnt[pre]; } cout ans \n; return 0; }代码是正确的核心逻辑就 5 行。但 map 底层是红黑树每次查找和插入都是 O(log n)而且频繁插入会涉及节点分配常数很大。我拿一组 n1e6 的随机数据在本机简单测过map 版本大概要跑 1.8 到 2.2 秒。如果题目时限在 2 秒以上可能勉强能过但在信奥赛场上1 秒时限的题很常见这个写法有风险。3.2 unordered_map 写法期望很快但稳定性一般第二种是用 unordered_map期望复杂度 O(1)unordered_maplong long, long long cnt; cnt[0] 1; long long pre 0, ans 0; for (int i 1; i n; i) { char c; cin c; pre (c A ? 1 : -1); auto it cnt.find(pre); ans (it cnt.end() ? 0 : it-second); cnt[pre]; }这里我特意用了 find 而不是直接 cnt[pre]因为直接 [] 会在 key 不存在时插入一个默认值会改变哈希表结构。虽然在这个场景下影响不大但养成只查询不插入的习惯总是好的。实测下来unordered_map 在同样数据下大概是 0.35 到 0.5 秒比 map 快很多。但它的缺点是常数不稳定特别是大量插入会触发 rehashrehash 时要重新分配所有节点时间波动比较大。而且标准库哈希在面对刻意构造的输入时冲突可能被放大器化最坏情况下退化得比 map 还慢。3.3 数组偏移写法竞赛场景下最稳的选择因为每个位置贡献的都是 1 或者 -1所以前缀和 pre 的值一定落在 [-n, n] 这个连续区间内。用整数作为数组下标时负数不能直接访问所以加一个偏移量 OFFSET把 [-n, n] 整体平移到 [0, 2n]#include bits/stdc.h using namespace std; int main() { ios::sync_with_stdio(false); cin.tie(nullptr); int n; cin n; const int OFFSET n 5; vectorlong long cnt(2 * n 10, 0); cnt[OFFSET] 1; long long pre 0, ans 0; for (int i 1; i n; i) { char c; cin c; pre (c A ? 1 : -1); ans cnt[pre OFFSET]; cnt[pre OFFSET]; } cout ans \n; return 0; }为什么 OFFSET 取 n5 而不是 n因为 pre 的最小值是 -n加上 n 刚好是 0再留一点余量避免边界错误。数组大小开2 * n 10足以覆盖 pre ∈ [-n, n] 映射后的所有下标。实测下来这个写法在同样数据上只要 0.03 到 0.05 秒比 unordered_map 快了一个数量级。原因很简单数组随机访问就是一次内存读写没有哈希计算、没有桶链表、没有扩容。能用连续整数当下标就绝不用哈希表这是我在竞赛里吃过亏之后总结出的经验。3.4 三种写法怎么选写法单次操作复杂度n1e6 实测耗时本机参考适用场景mapO(log n)约 1.8~2.2s数据量小、key 稀疏、懒得处理偏移unordered_map期望 O(1)约 0.35~0.5skey 稀疏、取值不连续、不想开大数组数组 偏移O(1) 真常数约 0.03~0.05s前缀和取值范围连续竞赛首选4. 完整代码与边界用例把正确性钉死在提交前4.1 最终提交版本综合前面的对比我最终用的是数组偏移版。完整代码并不长但三个关键点都藏在里面#include bits/stdc.h using namespace std; int main() { ios::sync_with_stdio(false); cin.tie(nullptr); int n; cin n; const int OFFSET n 5; vectorlong long cnt(2 * n 10, 0); cnt[OFFSET] 1; // 关键点1虚拟 pre[0] 必须预先存在 long long pre 0, ans 0; // 关键点2ans 必须用 long long for (int i 1; i n; i) { char c; cin c; pre (c A ? 1 : -1); ans cnt[pre OFFSET]; // 关键点3负数下标统一加 OFFSET cnt[pre OFFSET]; } cout ans \n; return 0; }三个关键点对应三类问题逻辑初始化、溢出、边界映射。任何一个出错程序都能跑但答案就是不对。这也是我后来说的看起来对实际上错的典型。4.2 边界用例设计边界用例不是随机生成的而是要针对可能出现的 bug 构造。我给自己定的检查流程是小样例手算、全 A 全 B 边界、随机数据对拍。先看几个必须过的边界n1输入 A只有一个 A没有任何区间满足两种标记数量相等答案应该是 0。n2输入 AB唯一的长度 2 区间 AB 满足条件答案 1。n2输入 AA没有合法区间答案 0。n6输入 ABABAB这个数据主要测是否重复计数手动可以算出结果也可以交给暴力程序验证。再考虑极端性能数据n1e6全 A答案必然是 0同时也能测试极端退化下的运行时间。n1e6交替 ABAB...合法区间数量会非常大用于验证 long long 是否溢出。这里重点说交替数据。在 ABABAB 这样的序列里任意偶数长度的连续区间A 和 B 的数量恰好相等所以答案等于所有偶数长度区间数量之和数量级大概是 n^2/8 到 n^2/4。n1e6 时答案接近甚至超过 1e11已经远超 int 的 21 亿上限。如果 ans 用 int会直接溢出成负数或者回绕成一个完全没意义的数。4.3 暴力对拍小数据兜底写对拍是信奥选手的基本功。我不直接依赖题目样例而是写一个暴力程序枚举所有区间对长度很小的随机数据做对比。暴力版核心大概这样long long brute(const string s) { int n s.size(); long long res 0; for (int l 0; l n; l) { int bal 0; for (int r l; r n; r) { bal (s[r] A ? 1 : -1); if (bal 0) res; } } return res; }然后用一个循环生成 n 从 1 到 10 的所有 A/B 字符串逐一对比暴力结果和前缀和算法结果。这一步跑通之后算法的正确性基本就有保障了剩下的才是性能问题。对拍的时候要注意暴力不能用 int 存答案哪怕数据小也要用 long long。因为这不是要不要溢出的问题而是要保持两边类型一致、口径一致避免因为暴力本身写错而产生的误判。5. 从一题到一类三个变式帮你把套路固化下来5.1 变式一区间和为 K 的计数GENIJALAC 统计的是和为 0 的子数组数量。把 0 改成任意整数 K思路完全一样只需要把统计目标从 cnt[pre] 改成 cnt[pre - K]。原理还是那个公式pre[r] - pre[l-1] K移项得 pre[l-1] pre[r] - K。所以在位置 r 时去历史里查 pre[r] - K 出现了多少次即可。这个变式太常考了几乎每过一段时间就会在一道模拟题里见到。建议把代码里的cnt[pre]统一改成cnt[pre - k]然后用同样的暴力对拍工具去验证。5.2 变式二不是计数而是求最长合法区间如果题目问的不是多少个区间而是最长的连续区间是多少哈希表的 value 就不再是出现次数而是最早出现的位置。做法是扫描过程中如果当前前缀和 pre 之前在位置 i 出现过那么 [i1, r] 就是一个合法区间长度是 r - i。我们只保留每个前缀和第一次出现的位置后续遇到相同值时都用第一次的位置去更新答案。这个变式的难点在于想清楚为什么记录最早位置而不是最近位置因为最长区间要求左端点尽量靠左。很多同学会把记次数的代码改一半结果查出来的长度永远是 1 或者 0问题就出在 value 的含义变了整个维护逻辑必须跟着变。5.3 变式三二维矩阵里的子矩阵计数扩展度高一点题目可能会变成给定一个 n 行 m 列的 0/1 矩阵问有多少个子矩阵满足行内两种标记数量相等。这时候一维前缀和就不够了常用做法是枚举上下边界把矩阵中间部分压缩成一维数组再用本题的套路。具体来说固定上边界 top 和下边界 bottom 之后每一列可以算出一个当前列的 A-B 差值把多列的值加在一起就得到一个一维数组。在这个一维数组上统计和为 0 的子段个数就是所有上下边界为 top 和 bottom 的合法子矩阵数量。复杂度会上升到 O(n^2 * m) 或 O(m^2 * n)需要根据数据范围选枚举方向。这个变式告诉我们这道题的核心思想是一层壳可以在许多地方复用。6. 三次提交才 ACGENIJALAC 的踩坑复盘6.1 第一次 WA漏了 cnt[0] 1第一次提交我用的 unordered_map 版初始化只写了声明忘了把 cnt[0] 设成 1。结果就是所有从第 1 个位置开始的合法区间全部漏掉样例如果恰好有一个以第 1 个字符开头的合法段输出就莫名其妙少 1。这个坑特别隐蔽因为如果你随便测一个小例子比如序列是 B A B A可能会想着反正答案里有别的区间差一个看不出来。但正式评测不会放过这种错误。从此我养成了一个习惯初始化部分单独写一行注释任何涉及前缀和的题第一反应就是 cnt[pre[0]] 1。6.2 第二次 WAint 溢出答案变成负数改完初始化后本地对拍全过提交还是 WA。我把输出打出来一看有时是负数有时是一个很小的离谱数字。查了一会儿才发现问题出在类型上。我一开始认为前缀和范围在 [-n, n]n 最大 1e6int 完全够用所以 pre 用的 intcnt 用的 intans 也用的 int。但合法区间的数量并不是 n 级别而是 n^2 级别。在 ABABAB 这种交替数据下答案大到 int 根本装不下溢出之后就变成了完全不可信的数。修复很简单ans 必须用 long longcnt 的值也统一用 long long。这个反例也说明做题不要只看某个中间变量会不会爆更要看最终答案的数量级。凡是计数题第一件事先估算答案上限通常都有 n^2 或更大级别。6.3 第三次卡常unordered_map 被哈希扩容拖累第三次答案终于对了但我在本地测 n1e6 交替数据时发现unordered_map 版的耗时忽高忽低某些输入能冲到 0.7 秒以上。虽然理论上可能过但这种不稳定的常数让人心里没底。后来我把cnt[pre]和find的调用流程拆开测过发现大量插入会频繁触发 rehash每次 rehash 都要把已有节点重新插入新的桶数组时间开销被放大。虽然整体均摊 O(1)但常数有时会达到几倍甚至十几倍。最终的解决方案就是换成数组加 OFFSET。前缀和的取值范围是连续整数数组下标天然就是最完美的哈希函数。从那以后凡是遇到前缀和取值范围有限且连续的题我直接上数组不再纠结哈希表。6.4 通用排查套路如果以后你做类似的题也 WA 了按这个顺序排查效率最高先看初始化虚拟 pre[0] 是否放入容器再看统计顺序是先累加还是先自增再看类型答案和计数是否 long long最后看映射负数下标是否真正平移到非负区间。这四步覆盖了大部分计数类前缀和题目的错误源。很多时候你不需要看算法思路因为思路早就对了错在工程细节上。7. 打卡刷题视角这道题留给我的几点感悟7.1 不要被 COCI 的厚故事壳吓住COCI 的题名和背景经常很夸张GENIJALAC 这种一听就很天才的题内核反而不复杂。这种厚故事壳、薄算法核的现象在早期 COCI 轮次里尤其常见很多题都是把经典算法包得看不出原型。应对办法是把题面里的对象、条件、询问一一翻译成数学符号。比如这题把两种标记翻译成 1/-1把数量相等翻译成和为 0把连续区间翻译成前缀和相减。翻译完之后一切就清晰了。这个能力需要刻意训练每道题打卡时可以多花 5 分钟把抽象模型写在笔记里。7.2 打卡的正确姿势不是刷数量我这个打卡系列已经到第 2892 个记号了但说实话前 500 题的时候我也走过弯路总想着今天做了几道新题结果很多题只是照着别人的思路抄了一遍第二天就忘。后来我把打卡拆成三个动作第一遍独立写哪怕写得慢、写得丑也要先有自己的思路第二遍看题解补盲区把别人的写法和自己的对比找差距第三遍重写并沉淀把核心套路压缩成一句话放进打卡本。P5181 这道题最后留给我的沉淀就是一句话区间和等于 0 的计数等价于前缀和相同的历史次数累计用偏移数组代替哈希表。下次再看到类似题目我只需要这一句话就能快速进入状态。7.3 最后分享一个内存和输入的小技巧数组开成2 * n 10时也许有人会担心 n 很大导致 vector 开不出来。实际上 n1e6 时2n10个 long long 也就 16 MB 左右完全没压力。就算 n 到 5e6也就 80 MB只要题目内存限制在 128 MB 或 256 MB依然够用。输入方面如果字符序列很长记得关掉同步ios::sync_with_stdio(false); cin.tie(nullptr);这两行能让 cin 快很多。如果还不放心可以自己写一个快速读入函数但对于只有一行字符串的题目来说关闭同步已经完全足够了。刷题打卡这件事最重要的不是某道题能拿多少分而是每道题都能留下一个可以复用的思维工具。GENIJALAC 能让我把前缀和 历史计数 偏移数组这个组合牢牢记住那它就没有白做。