算法竞赛复盘：贡献法、滑动窗口与线性DP的典型陷阱

2019年6月17日我在某个入门OJ上参加了一场相当随cao机shuai的模拟考试。三个题分别叫Seq、photo和分组行动。本来我的目标是三题全部AC结果考完出来一算第一题想复杂了第二题被multiset的erase坑了一手第三题DP方程推对了但循环边界写错。趁着记忆还在把这场考试的题目、我的翻车过程、还有后来整理出的正解思路全部记录下来给同样在刷题的朋友们当一个参考。这篇文章适合什么人看如果你正在刷算法入门题尤其是对枚举区间类问题滑动窗口线性DP这几个模型还不太熟那这篇赛后复盘应该能帮你少走一点弯路。我会把每道题从读题到暴力再到优化的完整思考链路都写出来包括考场上一闪而过的错误念头。毕竟这种看似草率的考试反而最能暴露一个人的真实水平。1. 先交代一下这场随机考试到底长什么样1.1 三个题的直观印象考试是下午开始的三个题总共给了三个小时。题目名字很随意题面也很随意像是一个人临时从题库里捞了三道题拼在一起。我当时的第一感觉是名字都这么草率题目应该不难吧。结果事实狠狠教育了我。题目数据范围核心知识点我最后的得分Seqn≤1e5贡献法 / 数学统计100photon≤1e5滑动窗口 / 双指针70被边界拖累分组行动n≤1000线性DP / 异或前缀50一个if写错这种名字简单题不简单的体验可能每个刷OJ的人都有过。题面越是随意越要警惕它是不是在某个经典模型上套了一层包装。比如photo表面上是拍照合影实际上就是最经典的最长满足条件的连续子区间问题。这类题在笔试和面试里也经常出现属于必须掌握的基本功。1.2 考场上我的时间分配我给自己定的计划是每道题最多一小时剩下时间全部用来检查。实际执行情况是前30分钟读题把三个题面各看了两遍心里大概知道了这场的难度梯度。第30-70分钟写Seq中间有一段时间纠结要不要枚举所有区间最后绕回贡献法。第70-130分钟写photo调multiset的删除逻辑花了大量时间。第130-200分钟写分组行动DP方程半小时推出来边界条件又磨了一个小时。最后40分钟回头检查才发现分组行动里有个循环的起点写错了改完已经快到交卷时间。这个时间分配其实很不合理第一题和第二题应该在前90分钟解决把时间留给第三题。但实战中往往会因为一个没想到的点卡住时间就像漏水一样流掉了。事后回想如果我能更早意识到先按模型分类再动手写代码整场节奏会从容很多。2. Seq看似要暴力枚举区间实际上每个相邻差早就注定了出场次数2.1 先把题意说清楚题目名字叫Seq给了两个整数n和数组a[1..n]。定义一个区间[l,r]的权值是这个区间内所有相邻位置差的绝对值之和也就是val(l,r) |a[l1]-a[l]| |a[l2]-a[l1]| ... |a[r]-a[r-1]|单个元素组成的区间权值为0。要求计算所有区间[l,r]的权值之和其中1≤l≤r≤n答案对1e97取模。看着这个式子我第一反应是那不就是枚举所有区间每个区间用前缀和快速求但仔细一想前缀和最擅长的是求和这里求的是绝对值之和不能直接做差。而且n是1e5总区间数是n(n1)/2暴力枚举必然超时。就算想用类似区间DP再合并的思路状态数和转移成本也完全扛不住。2.2 从暴力到贡献法我卡了大概十分钟然后试着换一个角度不枚举区间而是考虑每一对相邻位置到底会被多少个区间算到。|a[i1]-a[i]|只会出现在那些同时包含i和i1的区间里。一个区间要包含i和i1它的左端点必须小于等于i右端点必须大于等于i1。左端点的选择有i种1到i右端点的选择有n-i种i1到n所以这一对相邻差被计算了i*(n-i)次。这样一来整个问题的答案就变成了一个简单的求和ans Σ_{i1}^{n-1} |a[i1]-a[i]| * i * (n-i)拿n4、a[2,5,1,4]举例。相邻差分别是|5-2|3、|1-5|4、|4-1|3。第1对相邻差的左端点有1种选择右端点有3种选择出现3次第2对相邻差的左端点有2种选择右端点有2种选择出现4次第3对相邻差的左端点有3种选择右端点有1种选择出现3次。所以答案是33443*334。暴力枚举所有10个区间也能得到同样的结果但复杂度天差地别。这个推导就像把一堆硬币按面值分类来数而不是一枚一枚数。解题时经常是这样换一个统计的粒度复杂度和思路都会立刻清晰起来。2.3 考场上的两个小坑第一个坑是数据类型。n最大1e5i*(n-i)最大约2.5e9虽然还在int范围边缘但乘上相邻差的绝对值后可能更大必须用long long。我一开始习惯性地把ans定义成了int样例过得很开心提交就WA检查了好久才醒悟。第二个坑是取模。乘积可能非常大每乘一步都取模最后再输出ans % MOD。这里细节上要特别注意差值要用long long的绝对值不要直接用int型的abs免得溢出或者负数混进来。我因为图省事直接调了std::abs在部分编译器上对long long没有正确重载还差点把代码写坏。#include bits/stdc.h using namespace std; typedef long long ll; const ll MOD 1000000007LL; int main() { ios::sync_with_stdio(false); cin.tie(0); int n; cin n; vectorll a(n 1); for (int i 1; i n; i) cin a[i]; ll ans 0; for (int i 1; i n; i) { ll diff a[i 1] a[i] ? a[i 1] - a[i] : a[i] - a[i 1]; ll cnt 1LL * i * (n - i) % MOD; ans (ans diff % MOD * cnt) % MOD; } cout ans \n; return 0; }用上面这段代码跑一遍n4、a[2,5,1,4]的样例输出34说明思路和实现都对了。2.4 这类题想告诉我们什么Seq看起来像是一个区间统计题但真正的考点是贡献法不关心每个区间内部长什么样而是思考每个原子元素在这里就是每一对相邻位置在整个答案里被计算了几次。这个思想在组合数学和很多计数题里都特别常见比如求所有子数组的和、所有子序列的最大值之和、逆序对数量等等。遇到求所有区间/所有子集满足某种性质的答案总和时第一反应应该是贡献法而不是枚举区间。我在考场上花了将近20分钟在暴力枚举的思路上打转其实就是缺乏这个条件反射。下来之后我把看到所有区间求和就立刻想贡献统计这句话写在了笔记本第一页。数据范围只要到1e5级别几乎所有所有区间总和类问题都在暗示你要找一种不枚举区间的统计方式。3. photo滑动窗口但我的multiset差点翻车3.1 题意与合影场景photo这题是这么个故事n个人站成一排准备拍照第i个人身高h[i]。摄影师只能拍一段连续的人而且这一段里任何两个人的身高差都不能超过k否则照片构图失衡。问一次最多能拍到几个人。题面翻译过来就是给定数组h[1..n]找出最长的连续子数组使得子数组内最大值与最小值之差不超过k。这类题的经典解法是滑动窗口。左指针l和右指针r维护当前区间每次r向右扩展一个位置然后检查区间内最大值-最小值是否大于k如果大于k就不断把l向右移动直到条件重新满足。期间更新答案ansmax(ans, r-l1)。3.2 为什么不是二分答案考场上的思路会分叉。很多人的第一反应是二分答案mid再用O(n)检查是否存在长度至少为mid的合法区间总复杂度O(n log n)。这个思路本身没错n1e5的时候也能过但代码量比双指针大而且二分答案要配合数据结构比如线段树或ST表来求区间最值写起来容易出错。双指针的做法是只扫描一遍关键在于维护当前窗口的最大值和最小值。维护最值的数据结构有很多种multiset、两个单调队列、甚至线段树。我选的是multiset因为它最直观插入一个数删除一个数用rbegin()取最大值用begin()取最小值。这里有一个很实用的判断标准如果题目要求的是满足某个条件的区间最长长度而且条件随着区间扩大单调变差那么双指针几乎总是比二分更好写。二分答案在最大化最小值最小化最大值这类问题时是主角但在是否存在长度至少为x的合法区间上双指针是更自然的工具。3.3 multiset的erase陷阱代码框架很简单真正把我坑住的是这一行s.erase(h[l]); // 错误会把所有等于h[l]的元素全删掉multiset的erase方法有两种语义传一个值会把所有等于这个值的元素都删除传一个迭代器只会删除该迭代器指向的一个元素。窗口里可能有多个身高相同的人如果直接传值会把所有同身高的人全删光导致窗口内的最大值和最小值维护出错。正确写法是s.erase(s.find(h[l])); l;先通过find找到等于h[l]的某个迭代器再删除它保证一次只删一个。我踩坑之后顺手做了一个小实验往multiset里插五个4然后erase(4)五个4全没了而erase(find(4))只会没一个。这两种语义在单元素set里没区别一旦有了重复元素就会爆炸。这也是很多资料里反复强调的经典陷阱只是考场上紧张的时候特别容易忽略。3.4 完整代码和单调队列改进用multiset的正解代码#include bits/stdc.h using namespace std; int main() { ios::sync_with_stdio(false); cin.tie(0); int n, k; cin n k; vectorint h(n); for (int i 0; i n; i) cin h[i]; multisetint win; int ans 0; for (int l 0, r 0; r n; r) { win.insert(h[r]); while (*win.rbegin() - *win.begin() k) { win.erase(win.find(h[l])); l; } ans max(ans, r - l 1); } cout ans \n; return 0; }考后我自己复盘发现如果用两个单调队列维护最大值和最小值代码不仅省去multiset的log因子还从根本上避开了erase的坑。思路是维护一个递减队列qmax和一个递增队列qmin队首分别是当前窗口最大值和最小值。每次窗口移动时先把新元素从队尾插入、弹出不满足单调性的队尾元素再用l是否越过队首决定是否弹出队首。dequeint qmax, qmin; for (int l 0, r 0; r n; r) { while (!qmax.empty() h[qmax.back()] h[r]) qmax.pop_back(); qmax.push_back(r); while (!qmin.empty() h[qmin.back()] h[r]) qmin.pop_back(); qmin.push_back(r); while (h[qmax.front()] - h[qmin.front()] k) { l; while (!qmax.empty() qmax.front() l) qmax.pop_front(); while (!qmin.empty() qmin.front() l) qmin.pop_front(); } ans max(ans, r - l 1); }不过考试的时候我用multiset也AC了问题不大。会双指针加一种最值维护手段就足够应付绝大多数滑动窗口题。3.5 k0这个边界让我丢了30分photo最后我只拿了70分原因是有一个隐藏边界没考虑到当k0时窗口里只能有同一个身高的人。我在样例里k都是正数没有专门测k0的情况结果多段相同身高连在一起时出错。其实这种错误完全可以避免。从那以后我做双指针题都会在本地把k0、数组全部相同、数组单调递增、n1这些极端用例提前跑一遍再提交。尤其要检查的是while循环里l会不会把r都追过去、空窗口时会不会调用rbegin这种未定义行为。边界条件不是靠眼睛看出来的是靠一组一组用例试出来的。4. 分组行动状态转移里最容易被忽略的偶数长度4.1 题意复述第三题叫分组行动。题面同样很简短n个人站成一排第i个人的战斗力是a[i]。现在要把所有人按编号顺序分成若干连续的组每组的人数必须是偶数每组的收益是组内所有人的战斗力异或和。问最大总收益是多少。题目保证n是偶数。比如n4a[3,1,4,2]一种方案是只分一组[1..4]异或和是3^1^4^24。另一种方案是分成[1..2]和[3..4]第一组异或和是3^12第二组异或和是4^26总收益8。所以答案是8。这里要特别说明一下异或运算的含义。两个数异或对应二进制位相同为0、不同为1。它和加法最明显的区别是a^a0所以一个数出现两次会互相抵消。正因如此区间异或和才非常适合用前缀异或来求因为中间重复的部分会被抵消掉这个特性是普通求和前缀做不到的。4.2 DP方程的构造过程看到分成若干连续段和最大化收益思维会立刻跳到线性DP。设dp[i]表示前i个人完成分组后的最大收益这里要求i必须是偶数因为奇数个人不可能全部组成合法分组。从最后一个分组入手假设最后一组是区间[l..i]那么这一组的人数是i-l1必须是偶数也就是说l-1和i的奇偶性相同。前l-1个人的分组情况由dp[l-1]决定。于是有dp[i] max(dp[l-1] (a[l]^a[l1]^...^a[i]))用异或前缀和preXor[i]表示a[1]^...^a[i]区间异或就可以简洁地表示为preXor[i]^preXor[l-1]所以转移式写成dp[i] max(dp[l-1] (preXor[i]^preXor[l-1]))为了让代码更好写我通常令jl-1表示上一组结束的位置那么要求j从0开始小于i且i-j为偶数。由于dp只在偶数位置有意义直接把j按偶数枚举即可。4.3 O(n^2)为什么在这里够了n≤1000两层循环的复杂度是O(n^2)在最坏情况下约50万次操作对现代计算机来说瞬间完成根本不用担心超时。这也是入门OJ常有的套路数据范围设置成让O(n^2)能过但O(n^3)不能过逼你写出正确的动态规划而不是暴力搜索。如果是更大的n比如1e5这个DP可以用字典树优化到O(n log A)因为dp[j] (preXor[i]^preXor[j])这个式子本质上是给定一堆候选的j每个j有一个价值dp[j]和一个特征值preXor[j]查询时给定一个询问特征值preXor[i]要求最大化价值特征值异或。这种结构正好可以用按位字典树处理每个节点维护子树里dp[j]-某个值严格说需要用可持久化trie或离线技巧。但在考场上先确认数据范围远比盲目追求高级优化重要。#include bits/stdc.h using namespace std; const long long NEG -4e18; int main() { ios::sync_with_stdio(false); cin.tie(0); int n; cin n; vectorint a(n 1); for (int i 1; i n; i) cin a[i]; vectorint px(n 1, 0); for (int i 1; i n; i) px[i] px[i - 1] ^ a[i]; vectorlong long dp(n 1, NEG); dp[0] 0; for (int i 2; i n; i 2) { for (int j 0; j i; j 2) { long long cur dp[j] (px[i] ^ px[j]); if (cur dp[i]) dp[i] cur; } } cout dp[n] \n; return 0; }4.4 考场上的低级错误循环起点我上面写的代码第二层循环是从j0开始的这个对。但我考试时第一版写的却是for (int j 2; j i; j 2)把j0漏掉了。这意味着我永远无法考虑前面没有人整段作为第一组的方案。当最优解恰好是把整个序列分成一段时比如上面那个样例的备选方案4答案就会算错。我最后只拿了50分就是栽在这个地方。这种错误很典型写DP时枚举的是上一组的结束位置我们很容易默认上一组必须存在却忘了上一组结束位置可以是0也就是从一开始就不存在任何已分组的人。正确理解dp[0]0的含义之后就不会漏掉这个转移了。还有一个更隐蔽的同类错误当n为奇数时有人会把答案输出dp[n]但dp[n]是负无穷正确答案应该无解或输出-1这需要看题面是否保证n为偶数。5. 复盘从这份草率里能带走什么5.1 三题的时间与失误汇总考完回家我把每道题的用时和失败点重新整理成一张表题目预估合理用时实际用时主要失误Seq25分钟40分钟一开始陷入暴力枚举photo30分钟60分钟erase用错、没测k0分组行动35分钟70分钟漏掉j0DP边界不熟三个小时看上去很长但真正的高效刷题需要的是在每一个模型上都有足够的肌肉记忆。贡献法、滑动窗口、线性DP都是入门阶段最重要的基础模型我在同一场考试里全部经历了一遍这本身就是一笔很大的收获。更重要的是这些失误都不是因为题目超纲而是因为我对自己学过的东西掌握得不够细。5.2 暴露出来的三个短板第一个短板是看问题的视角转换太慢。Seq那题暴力枚举的诱惑非常大但如果一开始就提醒自己所有区间求和优先想每个元素贡献几次可以直接省掉十几分钟。第二个短板是对容器语义不敏感。multiset的erase传值和传迭代器的区别我在使用之前完全没想过重复元素的情况。这不是multiset的问题是我对标准库容器底层行为理解不到位。以后遇到不熟悉的容器方法我会先在本地写十行代码验证行为而不是凭着印象直接上。第三个短板是DP边界意识不强。dp[0]这种哨兵状态在方程里是与其他状态平等的不应该在枚举时特殊跳过。以后写DP转移我会先问自己三个问题初始状态是谁转移枚举的边界是什么每个新状态能不能从初始状态一步到达5.3 以后遇到类似题的固定思考链经过这场考试我给自己总结了三条条件反射看到求所有区间的某某总和先想贡献法想清楚每个原子单位被包含在多少个区间里。看到最长连续子数组满足某条件先想滑动窗口再想用multiset、单调队列还是线段树维护窗口特征。看到从左到右分成若干连续段并最大化收益先想线性DP再从最后一段开始设计状态转移。这三条算不上什么高深技巧却是实打实的解题路径。入门OJ的题名不一定正经考场的状态也不一定理想但只要思考框架稳定哪怕面对一份十分随cao机shuai的题单也能稳住心态一道一道拆掉。就我个人来说这场考试的教训比AC三题还值——AC的题过两天就忘了踩过的坑真的能记住很久。