最近在按“每日亿题”的计划推题单昨天正好轮到2017年ACM ICPC亚洲区域赛沈阳站。这场一共13道题我花了一个晚上加一个上午补完最终AC了10道剩下3道没啃下来。这篇继续作为系列的第2篇不按题号平铺直叙而是按我复盘的顺序分成几个类别来写重点讲有复用价值的题以及我在调试时踩过的坑。如果你最近也在补区域赛真题或者想找一套难度梯度比较正常的题目练手这场其实比很多近年新题更适合拿来刷。1. 整体复盘与难度分层1.1 十道题做完后的第一感受这场比赛属于典型的“中等偏难但不过分阴间”的区域赛配置。13道题里没有特别离谱的论文题但中间档的题量很大想把铜牌往上打至少得稳定做出5道左右银牌往上基本要把图论、DP、数据结构这三块吃透。我做出来的10道里有3道属于签到和模拟3道是常见的套路题还有4道需要现场推结论或做一点优化。整体时间主要耗在T6和T8上前者是DP优化后者是数据结构常数。难度分层我按自己的体感排了一下仅供参考难度档位题号按我自己的编号突破口预估用时签到/模拟T1、T2直接模拟或简单贪心40分钟基础算法T3、T4图论小结论 / 二分答案60分钟中档套路T5、T7、T9树上差分、数学分块、构造90分钟压轴难度T6、T8、T10区间DP优化、莫队、最大权闭合子图110分钟未完成T11、T12、T13计算几何、卷积优化、复杂树分治现场心态崩了1.2 这场比赛的“题感”分析做区域赛题单有个好处就是能明显感觉到出题人喜欢把知识点藏在场景后面。比如T5表面上是“树上若干条路径统计每条边被经过的次数”实际考的就是树上差分加LCA换一个包装就很多人不会了。再比如T8是“区间内出现次数最多的数”经典到不能再经典但卡常版本需要莫队排序优化。所以复盘的时候别只盯着“这题我AC了”要追问“这题的考点是什么换个包装我还认不认得出来”。这也是我做这场最大的收获。废话不多说下面按我推荐的做题顺序把每类题拆开讲。2. 热身题怎么把签到题写到不出错2.1 T1“省电模式”贪心结论要敢猜T1的题面大意是一台设备有若干种运行状态每种状态有一个功率现在给你一段时间的调度序列要求把其中一段连续时间切换到“省电模式”省电模式下所有状态的功率都会降到原来的某个固定比例问能省下的最大功率是多少。这题其实就是一个最大子段和的变体。把每个时间点“省下的功率”算出来即(1 - ratio) * power[i]然后在一维数组上找最大连续子段和。因为切换的是一段连续区间区间外的功率不变区间内的省电量等于省下功率的累加和所以问题马上转成经典的最大子段和。long long cur 0, ans 0; for (int i 1; i n; i) { long long val power[i] - power[i] * ratio; cur max(cur val, val); ans max(ans, cur); } printf(%lld\n, ans);注意数据范围直接power[i] * ratio如果两个都是整数会丢精度建议ratio用小数读入或者先把比例转成整数再算。我最开始就是在这里WA了一发只记住了“连续区间”的模型忘了处理浮点。2.2 T2“回文排列”与T3“最小环”的边界细节T2是关于字符串重排列后能否形成回文串。给一个字符串你可以重新排列任意次问能否做到任意两个相同字符之间的距离都相等。实际上如果一个字符出现了偶数次就能对称摆放如果出现奇数次的字符超过一个就不可能。所以代码只有几行难点反而是读题时容易把“重排列后是回文”和“任意两个相同字符距离相等”搞混。T3是求无向带权图的最小环。这个知识点在《算法竞赛入门经典》里讲过用Floyd顺便算最小环先枚举一个顶点k作为环上编号最大的点再枚举比k小的点i和j更新最小环ans min(ans, dis[i][j] w[i][k] w[k][j])之后再用k松弛最短路。这个顺序不能乱否则会把同一条边重复计入。关于T3有个小坑如果图不连通最小环不存在输出要按题目要求写不要图省事全输出0。我当时直接ans初始化为inf最后判断ans inf再输出无解这样最稳妥。3. 图论与连通性树上问题和二分答案的本质3.1 T5树上路径覆盖差分的核心是“点转边”T5的题面大致是一棵n个点的树有m条路径每条路径会把路径上的所有边覆盖一次问最后哪些边被覆盖的次数最多输出最大覆盖次数。这类题的标准解法是树上差分。维护一个diff数组每条路径u - v操作时diff[u]diff[v]diff[lca] - 2然后一次DFS把子树差分值累加回父亲就能得到每条边被覆盖的次数。如果是点权覆盖则diff[lca]--diff[fa[lca]]--这个细微的区别很容易记混。我再展开说一下为什么是-2路径覆盖边时每条边对应深度较大的那个点。从u到根和从v到根的累加会重复计算LCA以上的部分所以在LCA处减两次抵消。现场写的时候如果没想明白建议画一棵链状的树手动跑一遍差分比死记模板靠谱得多。void dfs(int u, int fa) { for (int v : G[u]) { if (v fa) continue; dfs(v, u); diff[u] diff[v]; ans max(ans, diff[u]); } }LCA部分我习惯用倍增lg数组预处理log2up[u][i]表示u往上跳2^i步的祖先。注意一个细节up数组第二维的大小要开到ceil(log2(n)) 1而不是直接写死20否则遇到n1e5的链会越界。好多同学在本地小数据测试没问题一交就RE多半是这里。3.2 T4“修桥”二分答案不是二分“修几座桥”T4题面说的是若干岛屿之间有桥连接可以修一定数量的新桥问让整个图连通需要的最小“最大距离”是多少。一开始容易理解成“修几座桥最少”但仔细读才发现是让你决定新桥的连接方式使得任意两个岛屿都能通过某种路径互相到达并且希望路径中单条边跨度的最大值尽量小。这题思路非常套路二分答案mid把所有原始跨度小于等于mid的桥加入并查集然后在当前连通块之间选择距离不超过mid的新桥。判断能否让整个图连通。因为新桥数量没有硬性限制所以只要在二分过程中不断合并最后看并查集是否只有一个根即可。复杂度是O((n m) log W)W是边权的最大值。这里我想说一个赛场经验二分答案的精髓不是套模板而是“检查函数”要写对。很多人二分边界设置成l 0, r max_edge结果检查函数里没有把“原本就存在的边”加全导致答案偏大。更好的做法是把所有边按权排序检查时只取前若干个这样就天然满足单调性。3.3 图论题调试的三个土办法第一写并查集时记得先执行init()否则多个样例之间会串数据。第二做DFS前先确认递归深度n较大时建议改成BFS或显式栈否则在OJ上直接栈溢出。第三涉及到树的问题如果题目没有说明根通常默认1号点为根这在求LCA时很重要。我在做T5时还遇到一个很隐蔽的问题因为差分会改变点权而树上的点权在统计时可能超过int范围所以差分数组要开long long。别看这个小区域赛数据一大WA两三次都很正常。4. DP与数论推导比模板更重要4.1 T6“序列切割”区间DP与四边形不等式T6的题面是给一个长度为n的数组把它切成若干段每段有一个代价代价等于该段中最大值与最小值的差问总代价最小值是多少。这道题一来就像区间DP但直接枚举四层循环肯定T。我一开始写的是O(n^3)的朴素转移n只有5000跑不动。后来观察到代价函数满足四边形不等式也就是转移点具有单调性可以用决策单调性优化把复杂度降到O(n^2)。具体做法是dp[i]表示前i个数切完的最小代价转移时枚举上一段的起点jdp[i] min(dp[j-1] cost(j, i))其中cost(j, i)可以通过预处理区间最值快速得到。由于cost满足四边形不等式j的最优位置随i单调不减所以可以记录opt[i]转移时从opt[i-1]枚举到i。for (int i 1; i n; i) { dp[i] INF; for (int j opt[i-1]; j i; j) { long long c maxv[j][i] - minv[j][i]; if (dp[j-1] c dp[i]) { dp[i] dp[j-1] c; opt[i] j; } } }这里特别提醒maxv[j][i]如果只能用O(1)查询的RMQ或st表那总复杂度是O(n^2)。我在赛场上图省事用了O(1)但是预处理二维数组n5000时二维数组大概100MB差点MLE。后来改成一维滚动预处理才过。遇到这种题先算内存再动手写。4.2 T7“模意义下的等比数列”分块处理循环节T7题面是给一个等比数列求和模数不一定是质数而且n很大。正常思路是用快速幂加逆元但模数不是质数时逆元不一定存在所以需要换方法。这题我做的时候差点绕进死胡同后来发现可以直接分块。设等比数列首项为a公比为q项数为n模数为m。因为模数固定q^i mod m一定会进入循环节我们可以找到循环节长度len然后把前min(n, len)项跑一遍之后每len项的和都一样再乘上循环次数即可。如果n太小或者循环节还没出现就到末尾了直接暴力O(n)也能过。这个思路用到的是“找循环节预处理前缀和”复杂度O(len)len通常是O(m)量级题目里m不大就可以跑。赛后我查了下有些人用矩阵快速幂也能做但显然分块更简单。4.3 数论题的通用检查清单取模时注意负数写成(x % mod mod) % mod。快速幂的指数是long long别写int。等比数列求和如果要约分先检查gcd是否为1。不要默认模数是质数很多区域赛题故意设非质数模数。5. 数据结构与构造题考场上的“最后一公里”5.1 T8“区间众数”莫队排序的奇偶优化T8就是经典的区间众数问题给一个序列和若干询问每次问区间内出现次数最多的数字出现了几次。用普通线段树不好维护因为区间合并众数并不满足简单结合律。最经典的离线做法是莫队但数据范围一上来普通莫队就会卡成TLE。我赛场上写的是带奇偶优化的莫队排序时如果左端点所在的块编号是奇数右端点从小到大排如果是偶数右端点从大到小排。这样右指针来回移动的距离能减少不少。实测下来加了这个优化之后跑的飞快比不加优化大约快30%到50%。bool cmp(const Query a, const Query b) { if (a.l / unit ! b.l / unit) return a.l b.l; if ((a.l / unit) 1) return a.r b.r; return a.r b.r; }维护众数次数时我用cnt[x]记录x出现次数num[k]记录出现次数为k的数字有多少个那么ans就是当前最大的k使得num[k] 0。每次移动指针时更新num[cnt[x]]--和num[cnt[x]±1]然后看ans是否需要调整。注意删除元素时可能出现ans对应的计数变成0要先减小ans再加新的计数。5.2 T9“矩阵覆盖构造”构造题的通用套路T9是一道构造题大致要求你在一个矩形网格里填数使得每一行每一列的和都满足某种奇偶性或者让指定位置的数字不同。这类题我自己的经验是先找出一个“平凡解”再去微调。对于这种构造最简单的做法是先全部填0然后根据约束按行按列逐个调整。很多约束可以转成“每个格子的奇偶性异或值”最后变成解一个异或方程组。如果题面里对每个格子有上下限还需要用网络流。我在这道题里用了贪心构造先满足行约束再调整列约束调整时只在同一行内交换数字即可保证行约束不变。这种题最怕的是“只验证了样例而没验证极限”。样例通常很小手动构造怎么都对但一上1e5的数据就各种越界。建议在本地写一个暴力对拍器随机生成小数据对比贪心答案和暴力答案能发现不少边界问题。5.3 T10“最大权闭合子图”建图比跑最大流更考验人T10的题面是一个经典的最大权闭合子图问题若干项目做每个项目有收益但需要依赖一些前置能力学习每个能力有成本。问能获得的最大净收益。这类问题只要建好图跑一遍最大流就能解决。建图方式源点向所有收益为正的项目连边容量为收益所有成本为负的能力向汇点连边容量为成本的绝对值项目依赖某个能力时从项目向能力连边容量为无穷大。跑完最大流后答案就是所有正收益之和减去最小割。这里最关键的是把“依赖关系”转成无限容量的边防止割掉不该割的关系。我当时卡了挺久不是不会最大流而是把“项目依赖能力”的方向连反了。正确的方向是收益节点指向成本节点如果搞反跑出来的最大流依然能算出流但答案完全是错的。注意Dinic的当前弧优化一定要写不然n到了几百条边多起来后会被卡成O(n^2m)。6. 赛题复盘中的常见问题与调试技巧速查6.1 常见错误对照表做完整场复盘后我把踩过或者见到别人踩过的坑整理成了一张表错误类型出现位置排查方向int溢出差值、求和、快速幂统一开long long边界RE倍增LCA、线段树检查数组开两倍或log大小浮点精度除法、比例、距离转整数或加eps答案偏大/偏小二分答案检查check函数是否单调图不连通并查集、最小环初始化父数组递归爆栈树上DFS改成BFS或迭代栈建图方向错网络流重新读题确认依赖方向6.2 调试技巧多用暴力对拍刷题复盘我有个习惯只要题目允许就在本地写一个暴力解和正解对拍。比如T8区间众数我写了一个每次询问直接遍历区间的程序随机生成1e4个数据和500个询问对照莫队答案。对拍跑几十组没问题我才会放心提交。对拍脚本也很简单核心是生成随机数据、运行两个程序、比对输出。Windows下可以用批处理Linux下写个shell循环。虽然在正式比赛时环境不一定允许但平时练习养成对拍习惯会极大地减少WA次数。6.3 一个关于“时间分配”的小经验这场我犯了一个比较典型的错误在T6区间DP优化上花了太多时间导致后面T10建图时间不够差点没调完。复盘时我意识到区域赛前几道题应当尽量控制在平均15分钟内中间档每道不超过30分钟压轴题遇到卡壳超过40分钟就果断跳过先拿稳能拿的分。 这次只做了10/13除去三道难题确实做不动之外T6多花的30分钟其实有点影响后面的节奏。7. 三道没做出来的题问题出在哪7.1 T11计算几何与半平面交T11几乎是一眼半平面交的题但写起来才知道细节多到炸直线求交、判点在多边形内、去重、判断空集每一步都有边界情况。我推到直线排序之后发现自己对极角排序后的“平行边去重”处理得不够熟越写越乱最后直接弃了。赛后看题解才明白半平面交模板必须提前准备得很熟练考场上第一次写就是送命。7.2 T12卷积优化DPT12的状态转移方程很容易写但是朴素转移是O(n^2)需要把卷积形式提出来用NTT加速。我虽然有NTT板子但对循环卷积和线性卷积的边界没搞明白pad长度算错了两次直接超时。这种题属于“题面看懂了算法也知道但模板不够熟练”的类型下来需要专门整理NTT的几种变形。7.3 T13复杂树分治与多限制T13涉及树上点分治和多个限制条件属于综合型题。我写到一半发现要维护的东西太多数组状态开不下。后来看别人的题解发现需要用“容斥单调队列”合并子树信息才能把状态压缩住。这题对我的启发是KDZ、点分治这类题先想清楚维护的最小信息集再动手写不然写着写着就改不动了。7.4 从三道题里提炼的后续练习方向三道题分别戳中我的三个短板计算几何代码能力、卷积类模板熟练度、树分治的信息维护。接下来我会专门各抽一天把这些板子重写一遍并且配上至少10道对应题目的练习。区域赛题单的复盘价值就在这里它不只是检验你会不会而是告诉你该往哪个方向补。8. 每日亿题系列的一点刷题心得最后聊点题外话。我开“每日亿题”这个系列初衷很简单每天定量补一场区域赛题写题解复盘。做了一段时间后我发现真正的进步不是靠刷题数量堆出来的而是靠“做一题总结一类”的习惯。比如这次沈阳站的T5树上差分如果只当成一道题AC就过了那和没做没啥区别但你把它和T4二分答案放一起看就会发现它们都在考“如何把复杂问题拆成单调性判断”这种提炼能力才是区域赛最需要的。另外复盘的时候尽量别对着别人的题解看一遍就觉得会了。我现在的习惯是先自己写AC再对一遍题解看有没有更优做法然后隔两天不看代码重新写一遍。能默写出来的题才算真会。如果你也在准备区域赛不妨试试这个节奏也许比一天刷十道新题更有效。