打完第 970 场 Div.3 之后我花了三天时间把那两道赛场上没做出来的题补掉顺手把整场的思考过程整理成了这份个人笔记。之所以说“整理”而不是“写题解”是因为我现在越来越确信对一场 Div.3 来说你赛后能从复盘里带走什么比当场多过一道题重要得多。这篇笔记会讲我怎么给复盘分层、怎么把散题归进模板、以及我在这类型中间段位比赛里踩过的一组典型边界坑。如果你正卡在 1300 到 1600 这个分段或者刚接触 Div.3 想建立自己的刷题节奏这份笔记应该能给你一些能直接用的东西。1. 我的复盘笔记到底记什么1.1 开头先记五个数字每场比赛打完我会第一时间在本子里写一行带时间戳的摘要内容固定是五件事AC 了几道、WA 了几次、总用时、补题前最后评分区间、赛后重做列表。这五个数字看起来简单但它能在一分钟之内告诉我这场状态到底烂在哪。比如 970 这一场我当场 AC 了 A、B、C、E 四道D 和 F1 各 WA 两次没调完。WA 的提交里D 两次都错在数组长度写错F1 第一次是没开long long第二次是二分边界写错。把这些数字放在一起看问题就暴露得很清楚D 属于思路没大错的实现失误F1 属于边界条件不熟练。前者说明我码力不稳定后者说明我对“最大最小”这类题型的条件反射还不够快。有了这个判断我补题时就不会无脑刷掉整场而是专门把 D 和 F1 当重点。1.2 按题型归档而不是按题目归档很多人的复盘笔记长这样A 题怎么写B 题怎么写C 题怎么写……写得很完整但下次遇到类似题还是想不起来。我自己的做法是反着来先把题目粗分为“枚举 / 贪心 / 前缀和 / 二分 / BFS / DP”几个抽屉再把题塞进去。一道题可以同时进几个抽屉无所谓关键是让“题型特征”和“解题动作”建立关联。这一场我归出来的抽屉是这样题型抽屉题目分布我的主判断依据模拟 / 构造A、B操作过程可描述输出受限制小前缀和 计数C、D区间性问题能转成前缀差贪心 / 排序E取最优顺序时往往需要排序二分答案F1求“最大最小”或“最小最大”BFS / 状态搜索F2格子或图上的最少步数这样的归档方式等于强迫我给每道题写了两行“特征签名”。比如以后看到“最多能分成多少段使每段和不超过 K”我不是去回忆某道具体题的代码而是立刻想到“预处理前缀和 二分或者双指针”这个组合。这个动作本身就是复盘的真正意义。2. 把这一场拆成四类核心题逐个说透2.1 模拟与构造题找到周期就到终点了模拟题是 Div.3 的送分主力但也很容易送走我。这类题的特征是给你一个过程、一堆规则让你输出若干次操作后的状态。A、B 两场我都是十分钟内过的复盘时我给自己总结了一条铁律先找循环再写循环千万别直接人肉模拟。举个典型的复盘记录假设有 n 个位置排成一圈每个位置有一个方向标记每轮问你从某个位置出发能否在 k 步之类到达目标。直接 while(k--) 或者队列模拟在 n 很大、k 很大的时候必挂但这题实际上每一轮状态完全一样走完一圈后就是周期重复。我当时的做法是先手动跑三四轮把周期长度算出来再用 k 对周期取模剩下的步数才实际走。这个思路平平无奇但却是这一整场模拟题里最关键的观察。真正在赛场上出错的人往往是没意识到“复现”这件事本身就是突破口。构造题则不太一样。它不给过程让你直接输出一个可能解。这类题我复盘时只记一个问题有没有“不变量”。比如让一个数组经过若干相邻交换后变得有序最小操作次数不是由数组本身决定而是由它的逆序对数决定。抓住不变量构造方案就会从一个“碰运气”的过程变成一个有根据的推导。Div.3 的构造基本不会太难多数只要构造一组“满足条件的排列”或“满足某种奇偶性的方案”先猜、再证、再写三步走。2.2 前缀和与区间计数题看到区间就想差分与映射C、D 两道题我都是栽在同一条路上直接暴力双循环统计子区间结果要么超时要么因为前缀和数组下标写错而 WA。赛后我把这类题专门拎出来重新练了一遍这里把核心套路分享出来。先说最经典的例子给定一个只包含 0 和 1 的数组问有多少个子区间里 0 和 1 的个数相等。如果直接枚举左右端点是 O(n^2)n 到十万就当场去世。正确姿势是把 0 看成 -1把 1 看成 1然后求前缀和数组 pre。于是问题变成了“有多少对 (i, j)使 pre[i] pre[j]”因为只有在两个前缀和相等的位置之间区间的数字总和才为 0也就是 0 和 1 个数相等。实现时我差点又踩一个坑pre[0] 0也要算进统计里否则漏掉从数组开头就满足条件的区间。正确代码大概是#include bits/stdc.h using namespace std; int main() { int n; cin n; vectorint a(n 1); for (int i 1; i n; i) { int x; cin x; // 把读进来的值映射成 1 / -1 a[i] (x 1 ? 1 : -1); } unordered_mapint, long long cnt; cnt[0] 1; // 前缀和为 0 出现一次 long long ans 0, pre 0; for (int i 1; i n; i) { pre a[i]; ans cnt[pre]; // 如果这个前缀和之前出现过就能配对 cnt[pre]; } cout ans \n; return 0; }注意答案要开long long因为合法区间数可能远大于 int 范围。这是我 F1 之外第二次被 int 坑的地方与其说算法不会不如说“随手开 int”的毛病根深蒂固。前缀和的另一类变种是“区间和能被 m 整除”套路完全一样只是把 pre 的值对 m 取模后存到 map 里。这类题刷上三五道之后基本就是肌肉记忆了。2.3 二分答案题先写判断再写二分Div.3 里一旦出现“最大化最小值”“最小化最大值”“求最大的可行长度/容量”基本可以闭眼往二分答案上靠。这一场 F1 就是典型的二分答案题我复盘时把完整的思考顺序写下来方便下次卡住时直接对照。假设我们有若干个桶每个桶容量有限要把一串物品按顺序装入桶中问在“最多分成 k 个桶”的前提下桶的最小容量是多少。这类问题的关键词是“最小容量”它同时具备两个条件越大越容易满足越小越难满足。单调性存在于是可以对桶容量做二分。二分的每一轮里用一个判定函数去验证给定容量 mid能不能把所有物品放进不超过 k 个桶。这个判定函数其实就是一个线性扫描用当前桶剩余容量记录一下装不下就开新桶。复杂度是 O(n) 一次判定总复杂度 O(n log V)完全能跑。我这一场卡住的点不在思路而在二分边界int l 0, r 1e9 1; while (l r) { int mid (l r) / 2; if (check(mid)) r mid; else l mid 1; } cout l \n;这个写法里判定成功说明 mid 够大我们应该收缩右边界失败说明 mid 不够左边界往右。整体是“找最小可行值”的标准框架。我以前最喜欢把判断成功和失败写反然后死循环。复盘时我总结了一个口诀找最小可行值满足则右边界等于 mid找最大可行值满足则左边界等于 mid。这个记法比背代码可靠得多。还有一个容易被忽视的细节二分答案里的答案可以是负数吗很多时候我们直觉上把左边界设为 0但如果物品里可能有负数容量不可能是负的还好说遇到某些带 pad 的间距类问题最低可能合法值就真的是负数。所以先认真读题看边界是从 0 开始还是从极小值开始。970 的 F1 我用l 0没问题但我有个朋友在另一道等价题上因为没把 l 设成“所有需求的最小值”而 WA 了一整场。2.4 BFS 与状态搜索把“图”画出来再动手这一场后半段的图论题没让我好过。F2 我选取了一个迷宫最短路的最朴素套路给定一张地图从起点到终点只能走空地求最短步数。这类题的模板大同小异BFS 按层扩展用 dis 数组记录第一次到达某格子的步数第一次到达终点时输出即可。但我复盘时真正想记的不是模板本身而是“什么时候该用 BFS什么时候该用 Dijkstra”。Div.3 的图论题绝大多数边权为 1BFS 就可以秒杀。只有在边权不一致、或者某些状态转移有额外代价时Dijkstra 才需要上场。我的快速判断方法是问自己“每一步的代价是不是完全相同”如果完全相同的BFS如果移动代价随位置或方向变化就 Dijkstra。970 这场里有个状态还带“传送阵”那就要把状态数组扩展成带层数或带传送信息的二维布尔数组BFS 照样能处理。BFS 代码模板也顺手贴在笔记里queuepairint, int que; vectorvectorint dis(n, vectorint(m, -1)); dis[sx][sy] 0; que.push({sx, sy}); while (!que.empty()) { auto [x, y] que.front(); que.pop(); for (int i 0; i 4; i) { int nx x dx[i], ny y dy[i]; if (nx 0 || nx n || ny 0 || ny m) continue; if (dis[nx][ny] ! -1 || grid[nx][ny] #) continue; dis[nx][ny] dis[x][y] 1; que.push({nx, ny}); } }比起代码写法我更想强调状态数组的长度。很多图论 WA 根本不是算法问题而是dis的开法错了比如地图是 n 行 m 列结果开成了 m 行 n 列下标一转就数组越界。我这场 D 的两次 WA 全部死在类 似 的 “数组维度写反”上这一点后面专门讲。3. 这一场我踩进去的四个边界坑3.1 int 溢出别以为只有 1e18 才叫大赛场上有一种憋屈叫“思路对了答案类型没开对”。前缀和、区间计数、排列组合动辄就能达到 O(n^2) 的规模n 到 2e5 时答案上限就是 4e10int 根本放不下。我这一场至少有两个地方应该直接long long ans 0从开头就开对结果硬是等到 WA 之后才改。复盘时我把所有可能爆 int 的位置列了个清单前缀和 pre、合法配对数量、乘法中间结果、二分答案返回值的判断函数内部累计和。看见任何“求和”或“计数”关键词默认long long你在第一层写类型时就该有这个意识。3.2 二分死循环问题出在“趋于零的前进规则”二分死循环最常见的原因是左右边界收敛时如果中间值mid永远不变化while 就卡死了。比如我写“找最大可行值”时如果代码是这样的if (check(mid)) l mid; // 这里忘了确保 mid 在变化 else r mid;那么当l 3, r 4, mid 3时check(3) 为真l 被设成 3一下次还是 3死循环。正确写法要么用mid (l r 1) / 2让中点偏右要么在check(mid)成立时写l mid 1而不是l mid然后再考虑最终答案要不要减一。复盘时我给自己定的规矩是任何二分答案的中点在边界相邻时必须能保证区间长度至少缩小 1。这个检查比背哪个模板管用十倍。3.3 下标是 0 还是 1和的终点和起点都会骗你前缀和问题里最容易错的一行是pre[0] 0有没有被算进去。比如统计“区间总和等于 0 的区间个数”如果你只从 pre[1] 开始往 map 里放就会漏掉以 1 为左端点的区间。再比如说某些题要求“从 l 到 r 的和等于 pre[r] - pre[l-1]”那么数组长度必须开成 n1for 循环从 1 开始存储这样 pre[i] 就对应前 i 个数。省掉 pre[0] 的那个人往往会在边界样例上翻车。我整理了一个自查清单第一次出现的下标是不是 0map 初始化时存没存 pre[0]循环是从 0 开始还是从 1 开始输出答案时用 l 还是 l-1每次写完都要逐个对电光石火之间能救下不少 WA。3.4 输入输出性能刷量很大的时候std::endl 是敌人这一场我在补 F2 时中途用了一段很朴素的 cin/cout没有加快读输出还带endl。结果本地样例跑得挺欢交上去超时。原因无他大量输出时endl会强制刷新缓冲区每行一次 flush性能损耗巨大。复盘后的长期修复方案很简单把所有模板统一写成ios::sync_with_stdio(false); cin.tie(nullptr);同时输出时用\n而不是endl。这个方法能解决 95% 的 IO 性能问题。剩下 5%比如 n 到 1e6 且输入量超大再用快读或scanf。对 Div.3 来说只要把这两行加上基本告别 IO 超时。4. 直接抄走一份能复用的 Div.3 复盘模板我现在每场打完之后都会直接复制下面这个模板然后往里面填内容。它足够轻量让复盘这件事不会变成负担## [比赛编号] Div.3 复盘 - 当场完成A, B, C, E - 补题完成D, F1, F2 - WA 次数Dx2, F1x1 - 总提交数11 ### 按题型的抽屉归档 - 前缀和 计数C, D - 二分答案F1 - BFSF2 - 贪心E ### 每道题一句话教训 - A模拟题先算周期再暴力 - B构造题先找不变量 - C前缀和统计map 要预置 pre[0] - D数组维度别写反看看 n 和 m - E排序之后贪心别忘开 long long - F1二分答案判断函数返回 bool边界用 l r - F2BFS 状态数组多层注意传送门 ### 下次目标 - 所有计数答案一律开 long long - 二分模板统一背熟“找最小/最大”两套写法 - F2 类迷宫题限定 30 分钟内调通把这个模板存成本地 markdown 文件每场比赛一个文件。你会发现连续记录 5 场以后自己的高频问题项会非常清晰地浮出来这就是所谓“u200b数据驱动的刷题”。5. 补题时顺手做的小事写一个小型对拍器打完比赛补题不是把 AC 代码交上去就完了。我会做一件事写一个暴力解和一个优化解然后跑小数据随机对拍。这听起来有点蠢但它是捕捉“假通过”的最好办法。比如这场 F1 我用二分答案写的代码本地样例全过但如果我拿它去对拍一个 O(n^2) 的暴力在 n20 随机数据下跑 200 组立刻就能抓到边界错误。对拍脚本思路也不复杂核心只有三步生成随机输入、跑两个程序、逐行比较输出。比如用 bash 快速实现for i in $(seq 1 200); do python gen.py in.txt ./std in.txt out_std.txt ./test in.txt out_test.txt if ! diff -q out_std.txt out_test.txt /dev/null; then echo WA on test $i break fi done对拍能覆盖到那些你想不到的手工样例帮我省下了很多次无意义的 rejudge。这个方法特别适合前缀和、二分这类容易边界出错的题。对拍本质上是在告诉我们的脑子别太相信所谓木一的“通透感”写下来的代码才算数。复盘到最后我觉得最值得记住的不是某道题的解法而是那三个数字WA 次数 × 错误类型 ÷ 题目难度。我已经连续三轮 Div.3 都把“计数答案开 int”写进失误清单了这一场终于靠模板强制改掉了。下一次遇到类似题我应该可以更早地跳去 F2而不是在 F1 和边界条件搏斗到收场。
