这周末刷完了AtCoder Beginner Contest 442A到E五题都过了赛后冷静下来复盘了一下发现这场题目其实分层非常明显A、B两题就是送分题C题开始有点思维量D题是典型的状态设计题E题则是数据结构优化难度梯度拉得很舒服。如果你是刚开始打ABC的选手这场的A到C是很好的练习题如果你在冲击D、E这场的D题和E题也很值得用来校准自己的算法实现能力。这篇文章我会把自己从读题到提交的完整过程拆开讲包含每道题的思考路径、代码实现、复杂度分析还有一些只有实际写完才知道的细节坑。我会尽量写得具体让你看完之后能直接拿去练手而不是只得到一个“这题要用XXX”的空话。1. 赛前准备与整体策略复盘1.1 从A题到E题的难度分布与定位先说整体印象。ABC 442这场的A到E难度分布大致可以概括成“两易一中一难一深”。A、B题基本是签到级别适合用来找手感C题属于典型的中等思维题考的是你能不能从暴力思路里跳出来D题是区分度最大的一道题状态设计得好代码就很短状态设计偏了就会陷入改bug的死循环E题则是妥妥的进阶题算法模型一眼能看出来但实现细节多稍不注意就会TLE或者WA。我一般打ABC会先花两分钟把A到E的题面都扫一遍这个动作很关键。A、B先不急着写确认一下C题是什么类型、D题可不可做、E题大概要用到什么数据结构这样心里就有了一张地图。拿到题不要像无头苍蝇一样从A开始闷头写先把时间预算分配好。这场的A、B我加起来只用了不到八分钟C题用了大约十五分钟D题接近四十分钟E题写写改改花了半小时整体节奏还算健康。还有一点值得说ABC的题面英文一般比较直白但偶尔会有几个容易误解的表述。这场的C题就有一个关于“不同元素”的定义如果不注意是整数位置不同还是元素值不同很容易把思路带偏。我的习惯是读完题面先用自己的话复述一遍题意尤其是对于“相等”、“不同”、“至少”、“最多”这类限定词绝不放过。1.2 时间分配与心态管理时间分配上我有个固定的策略前25分钟是A、B、C的固定窗口。A、B不需要犹豫看到能写的模拟就立刻写C题给自己10到15分钟一旦超过这个时间还没思路果断跳过先去看D。这样做不是因为C不重要而是ABC的D题通常比C更偏向模板题在会写的情况下D的性价比反而更高。这场的D题确实是那种“会者不难”的题状态转移想清楚之后代码不到四十行。而如果你在C题上死磕了四十分钟再过来做D脑子已经疲劳了很容易写出低级错误。我见过不少选手C题做不出来D题其实能做结果因为心态崩了D也写挂了这才是最亏的。心态方面我给自己定了一条规矩每道题如果连续两次提交WA就停下来离开代码在纸上重新推一遍样例而不是继续“试错式修改”。这次D题我就差点犯这个毛病第一次状态转移的顺序写错了好在自己意识到问题重新画了状态图才纠正过来。打比赛时最怕的不是不会而是用错误思路反复提交浪费时间和罚时。2. A、B题签到题的快准狠2.1 A题的常规套路与提交策略A题这场的难度属于标准签到水平题意基本就是给一个整数或字符串让你按某个简单条件输出结果。这种题考的是手速和读题准确度没啥算法含量唯一的要求就是别读错题。A题的实现想分享一下我的习惯能用一层循环解决的绝不用两层能直接数学计算的绝不做数组遍历。有的选手习惯上来就开一个长度为100005的数组其实很多A题的数据范围根本没必要反而增加了出错的可能性。遇到这种题我的原则是“代码越短越好”因为代码越短出bug的概率就越低。代码层面提个醒用C写这类签到题时注意数据类型。有一些A题会给出看起来不大但乘起来会溢出的数据比如两个10^5级别的数相加或相乘虽然题目一般会保证结果在int范围内但养成用long long的习惯总没坏处。赛后看了一些选手的讨论确实有人因为int溢出在A题上吃了一发WA这种罚时真的不该吃。还有一个小技巧A题这种签到题样例一定是弱样例。就算你本地把样例全过了也可能因为边界条件WA。我习惯在提交之前自己造两三组边界数据比如最小值、最大值、只有一个元素的情况跑一遍再交。这个习惯帮我在B题也避免过一次WA。2.2 B题的模拟细节与边界处理B题依然是模拟题但相比A题会多一些规则。通常是一个字符串或数组按某个规则进行变换或判断数据范围不大直接按题面模拟即可。这场的B题我印象比较深的是规则里有一个“循环”的概念处理起来要特别注意边界比如下标越界、循环次数为0、空串输入等。写B题时我最常用的方式是拆函数。把题面里描述的规则拆成独立的判断函数比如“是否满足条件”“下一步应该移动到哪个位置”然后主函数只是按流程调用。这样做有几个好处一是逻辑清晰不容易漏规则二是如果WA了可以直接定位是哪一步的辅助函数写错了。边界处理上我总结了一个清单每次写模拟题都过一遍循环变量是否可能从0开始还是从1开始字符串或数组的长度为1时逻辑是否正确数据范围里提到的最大值和最小值情况是否覆盖操作顺序是否严格按照题面描述有没有被样例“带偏”。B题还有一个常见坑就是输出格式。有的题要求输出空格分隔有的要求换行分隔有的要求固定保留几位小数。这场的B题没有小数问题但我见过太多人在输出格式上吃WA。我的建议是提交前最后十秒专门检查输出那一行不要改完逻辑就急着交。3. C题从暴力到最优的思维跳跃3.1 题目分析与常见误区C题是这场比赛的第一个分水岭。题意简单概括是给定一个序列让你统计满足某种配对条件的数量朴素做法是O(n^2)枚举所有数对数据范围稍微大一点就会超时。题目本身不难难的是你能不能第一时间意识到暴力会超时以及能不能快速切换到O(n log n)的优化思路。我先说说我最初看到这道题时的判断过程。首先看了一眼数据范围n到10^5级别O(n^2)是10^10肯定不行。接着想配对类的问题往往能用排序、哈希表、双指针、二分或者前缀和来优化于是开始逐个尝试。这题的核心是把条件拆开你会发现它其实是在问“有多少对数满足某种偏序关系”这种模型十有八九和排序脱不了干系。常见的误区有两个。第一个误区是没注意到“不同元素”的定义有的选手会理解成数值不同实际上题目说的可能是下标不同导致统计结果偏大。第二个误区是用了哈希表存值却没有处理好重复元素的计数多计数或者少计数都在所难免。赛后我翻了评论区不少选手都是卡在这两个点上。C题的坑提醒我思维题第一步不是想算法而是把题面里的每个限定词都翻译成数学条件。条件翻译对了算法自然就浮出水面条件翻译错了就算用上再高级的数据结构也是错。3.2 排序加双指针优化思路讲一下这道C题的最终解法。我们先把数组排序这样原本无序的配对条件就变成了有序序列上的区间查询问题。针对每个位置i我们需要找到满足条件的最大右边界然后累计数量。因为数组有序右边界随着i增大只会单调右移所以我们用一个指针维护这个边界即可这就是经典的双指针解法。复杂度方面排序是O(n log n)双指针扫描是O(n)整体是O(n log n)在n为10^5时完全够用。代码实现上双指针有一个细节需要注意每次i移动后右边界指针不应该回退而是从当前位置继续向右扩展。如果你每次让指针重置复杂度又变回O(n^2)了。我还想补充一个用二分替代双指针的写法。对于每个i用二分查找最大的满足条件的j复杂度是O(n log n)加排序的O(n log n)也能过。二分的代码有时候比双指针更容易写对尤其当你对双指针的边界不熟的时候。我在比赛里用的是双指针但赛后试着用二分实现了一遍发现两个做法的时间相差不大。C题如果做不出来我建议先别急着看题解自己把排序和双指针这两个基础内容吃透然后总结一下“统计配对”这类题的常见套路。这类题的变种包括两数之和、三数之和、区间计数、子序列计数本质上都是一个思路学会了能一打十。4. D题动态规划与状态设计的经典套路4.1 状态定义与转移方程推导D题是这场ABC 442里最值得复盘的一道题它考的是动态规划的状态设计。这类DP题有一个共同特点题目给你一个序列或图结构要求你求某个最优值或方案数直接贪心是错的必须枚举状态。我当时的状态定义思路是这样先看题目的操作是“分阶段决策”的每个阶段会影响到后面的状态而且阶段之间有明显的前后依赖。我定义dp[i][j]为处理到前i个元素、当前处于某个状态j时的最优答案。关键是j有几个取值、每个取值代表什么意思这里一定要画图理清楚不能用眼睛看。转移方程的推导可以这样展开对于第i个位置它可以从第i-1个位置转移过来而转移时根据前一个状态的不同会有不同的代价或收益。把这些代价整理成公式就是dp的转移方程。写转移方程时我犯了一个典型的错误转移顺序写反了导致后更新的状态覆盖了还没用到的旧状态。这个问题在滚动数组的写法中尤为常见后面我会详细说。我在代码里通常会用-INF初始化所有状态然后用一个循环正常转移。如果你发现最终答案是0或者一个很离谱的大数很可能不是转移方程错了而是初始化或者状态枚举的起点错了。D题我第一次提交WA就是因为初始化起点设错了整个状态图全乱了好在最后排查出来了。4.2 空间优化与实现注意事项D题的数据范围如果很大比如n到2000以上dp数组直接开二维可能会超内存。这时候需要用滚动数组优化成一维或者至少把第一维压缩成两个交替使用的状态。滚动数组是DP实现里的经典技巧但在ABC这种短平快的比赛里也是WA高发区。最常见的问题是你在更新dp[i % 2][j]的时候用到了dp[(i-1) % 2][k]但如果某一个j没有被更新到它残留着上上轮的数据就会导致转移错误。我的习惯是每轮开始前先把当前要写的这一行全部重置成初始值再执行转移。有些选手为了省这几行代码结果WA了三四发得不偿失。D题的代码量其实不大但逻辑密度很高。我写完之后没有马上提交而是手工推了三组数据一组是题面样例一组是边界情况比如n1一组是自己构造的最坏情况。这三组数据过了我才敢提交。这个习惯在D题这种中等题上尤其重要因为WA一发就要等五分钟penalty太影响排名了。如果你感觉自己DP题总是卡住我强烈建议练一下“状态图”方法把每种状态画成节点把转移画成有向边然后从图上检查是否有遗漏的边。这个方法在遇到复杂DP时特别管用比空想转移方程靠谱得多。D题我一开始状态设计得不够细后来补了一个维度才顺利通过靠的就是画状态图。5. E题进阶算法的攻坚指南5.1 识别题目背后的算法模型E题这次属于“模型一眼可见实现地狱难度”的题。题目表面上是区间查询或区间修改实际上考的是一个标准的数据结构模型。看到这种题首先要判断的是用线段树、树状数组、并查集、平衡树还是分块这个判断直接决定了你能不能在比赛时间内写完。我当时识别模型的方法是看操作类型。如果题目只有单点修改加区间查询树状数组就能搞定如果有区间修改加区间查询线段树加懒标记是常规方案如果涉及集合合并和连通性问题并查集往往是正解。这场的E题的模型偏向区间最值或区间第k大类的问题所以正解是线段树。顺便提一句E题的整体感觉让我想起ARC076那场的某道经典题同样是数据结构优化同样是对懒标记的理解深度有很高要求。如果你刷过ARC076那道题这场的E题应该会感觉亲切一些。做题多的人往往会在这种时刻体会到“题感”这种东西——它其实是你见过的模型足够多之后的自然反应。5.2 线段树实现的常见陷阱线段树的实现看起来模板化但这场的E题把几个常见的坑全部踩了一轮。第一个坑是懒标记的累积规则。区间修改时懒标记不仅能“覆盖”还可能“叠加”这取决于操作的类型。如果叠加规则写错查询结果就会偏大或偏小而且这种错误很难用样例发现因为样例通常覆盖不到复杂的多次叠加。第二个坑是数组大小。线段树的数组一般是4倍空间这个大家应该都知道但问题是如果build或者update时用了错误的边界比如写成r1而不是r就可能越界访问导致本地能过、提交就RE。我的经验是在实现线段树时统一采用左闭右闭区间每次递归前先判断lr这样可以减少很多边界错误。第三个坑是查询区间与修改区间完全不相交的情况。很多线段树模板是在函数入口判断如果当前节点区间完全在查询区间外就返回但如果你把判断条件写反了就会导致递归永远不终止最后栈溢出。这个错误我在E题调试时遇到过花了不少时间才意识到是判断条件的问题。E题这种题想提速没有捷径就是大量刷题把模板写熟。我推荐你手写线段树不要复制模板每个字母都自己敲敲到形成肌肉记忆这样比赛时就能把精力集中在题目分析而不是写代码上。如果你还没有自己的线段树模板建议花一个下午把它彻底吃透包括建树、查询、区间修改、单点修改、懒标记这些都是ABC高阶题的常客。关于时间优化E题还有一个容易被忽略的点输入输出。当数据量比较大的时候建议使用scanf/printf或者关闭同步的cin/cout否则很容易因为IO太慢导致TLE。这次我的E题代码核心逻辑没有问题但第一次提交居然因为忘了加ios::sync_with_stdio(false)被卡了100ms左右差点超时真的很冤。6. 参赛常见问题与调试技巧实录6.1 WA、TLE、RE的排查思路每次比赛复盘都能看到大量WA、TLE、RE。我把这三类错误做一个速查表方便你对照排查。错误类型常见原因排查方向WA状态转移顺序错误重新画状态图检查每一条转移路径WA边界条件遗漏补测n1、空串、最大/最小值数据WA题面理解偏差回读题面尤其注意“不同”“最多”等限定词TLE算法复杂度超标确认是否用O(n^2)替代了O(n log n)TLE输入输出未优化加ios::sync_with_stdio(false)或改用scanfTLE递归层数过深或常数过大改成迭代或精简线段树操作RE数组越界检查所有下标尤其线段树边界RE栈溢出检查递归终止条件避免无限递归RE除零或未初始化检查分母、初始化所有变量我的排查顺序是先看错误类型如果TLE就先优化复杂度如果WA就先检查样例之外的自造数据。不管什么错误我都不建议在没想清楚之前乱改代码。每一次提交都应该带着一个明确的假设。6.2 高效的本地测试与数据生成方法这里分享一个我在比赛后复盘时常用的方法写一个数据生成器用暴力解法和小数据量去对拍。对拍是ACM圈里最经典的调试手段但在AtCoder这种不提供judge数据的平台上同样适用。做法很简单写一个solve_brute.cpp用最简单的思路解题确保结果正确写一个solve_fast.cpp用你比赛时的优化解法写一个gen.cpp随机生成小范围数据写一个对拍脚本循环执行生成数据 → 用两个程序分别跑 → 对比输出。如果两边输出不一致再把那组数据缩小到最小复现规模然后单步调试solve_fast。这个方法几乎可以解决所有WA和边界问题。我这次D题就是通过这个方法发现了状态初始化的问题暴力解法和我比赛时的解法在n3时结果不一样顺着diff的数据一行行排查最终定位到问题。对拍脚本我一般在脚本环境里用循环写语言不限核心逻辑就是生成数据、运行程序、比较输出、出现差异就停止。对于TLE问题我还会加一个计时命令统计solve_fast在最大数据规模下的运行时间如果超过0.5秒说明常数优化还有空间。最后再提醒一下对拍要用随机数据但也要用定向构造的边界数据。比如你已经猜到某道题可能卡某个边界就专门写一个生成器构造那种边界而不是只靠随机碰运气。好的测试应该是有针对性的不是跑一万组随机数就叫充分测试。打比赛这种事儿最怕的就是“我本地能过”四个字。你永远不知道judge上藏着什么数据。多花五分钟做对拍和边界测试省下来的是更稳的AC和更漂亮的排名。我见过太多人因为少测一组n1的数据丢掉了一道题真的很可惜。这周的ABC 442刷完最大感受是做题的节奏感比做出一道难题重要得多。如果你能稳住前半小时拿掉A、B、C后面D和E的做题体验会完全不一样。希望这份复盘能给你带来一些参考下次ABC赛场见。
ABC 442 A-E题复盘：从双指针到线段树的算法思维进阶
这周末刷完了AtCoder Beginner Contest 442A到E五题都过了赛后冷静下来复盘了一下发现这场题目其实分层非常明显A、B两题就是送分题C题开始有点思维量D题是典型的状态设计题E题则是数据结构优化难度梯度拉得很舒服。如果你是刚开始打ABC的选手这场的A到C是很好的练习题如果你在冲击D、E这场的D题和E题也很值得用来校准自己的算法实现能力。这篇文章我会把自己从读题到提交的完整过程拆开讲包含每道题的思考路径、代码实现、复杂度分析还有一些只有实际写完才知道的细节坑。我会尽量写得具体让你看完之后能直接拿去练手而不是只得到一个“这题要用XXX”的空话。1. 赛前准备与整体策略复盘1.1 从A题到E题的难度分布与定位先说整体印象。ABC 442这场的A到E难度分布大致可以概括成“两易一中一难一深”。A、B题基本是签到级别适合用来找手感C题属于典型的中等思维题考的是你能不能从暴力思路里跳出来D题是区分度最大的一道题状态设计得好代码就很短状态设计偏了就会陷入改bug的死循环E题则是妥妥的进阶题算法模型一眼能看出来但实现细节多稍不注意就会TLE或者WA。我一般打ABC会先花两分钟把A到E的题面都扫一遍这个动作很关键。A、B先不急着写确认一下C题是什么类型、D题可不可做、E题大概要用到什么数据结构这样心里就有了一张地图。拿到题不要像无头苍蝇一样从A开始闷头写先把时间预算分配好。这场的A、B我加起来只用了不到八分钟C题用了大约十五分钟D题接近四十分钟E题写写改改花了半小时整体节奏还算健康。还有一点值得说ABC的题面英文一般比较直白但偶尔会有几个容易误解的表述。这场的C题就有一个关于“不同元素”的定义如果不注意是整数位置不同还是元素值不同很容易把思路带偏。我的习惯是读完题面先用自己的话复述一遍题意尤其是对于“相等”、“不同”、“至少”、“最多”这类限定词绝不放过。1.2 时间分配与心态管理时间分配上我有个固定的策略前25分钟是A、B、C的固定窗口。A、B不需要犹豫看到能写的模拟就立刻写C题给自己10到15分钟一旦超过这个时间还没思路果断跳过先去看D。这样做不是因为C不重要而是ABC的D题通常比C更偏向模板题在会写的情况下D的性价比反而更高。这场的D题确实是那种“会者不难”的题状态转移想清楚之后代码不到四十行。而如果你在C题上死磕了四十分钟再过来做D脑子已经疲劳了很容易写出低级错误。我见过不少选手C题做不出来D题其实能做结果因为心态崩了D也写挂了这才是最亏的。心态方面我给自己定了一条规矩每道题如果连续两次提交WA就停下来离开代码在纸上重新推一遍样例而不是继续“试错式修改”。这次D题我就差点犯这个毛病第一次状态转移的顺序写错了好在自己意识到问题重新画了状态图才纠正过来。打比赛时最怕的不是不会而是用错误思路反复提交浪费时间和罚时。2. A、B题签到题的快准狠2.1 A题的常规套路与提交策略A题这场的难度属于标准签到水平题意基本就是给一个整数或字符串让你按某个简单条件输出结果。这种题考的是手速和读题准确度没啥算法含量唯一的要求就是别读错题。A题的实现想分享一下我的习惯能用一层循环解决的绝不用两层能直接数学计算的绝不做数组遍历。有的选手习惯上来就开一个长度为100005的数组其实很多A题的数据范围根本没必要反而增加了出错的可能性。遇到这种题我的原则是“代码越短越好”因为代码越短出bug的概率就越低。代码层面提个醒用C写这类签到题时注意数据类型。有一些A题会给出看起来不大但乘起来会溢出的数据比如两个10^5级别的数相加或相乘虽然题目一般会保证结果在int范围内但养成用long long的习惯总没坏处。赛后看了一些选手的讨论确实有人因为int溢出在A题上吃了一发WA这种罚时真的不该吃。还有一个小技巧A题这种签到题样例一定是弱样例。就算你本地把样例全过了也可能因为边界条件WA。我习惯在提交之前自己造两三组边界数据比如最小值、最大值、只有一个元素的情况跑一遍再交。这个习惯帮我在B题也避免过一次WA。2.2 B题的模拟细节与边界处理B题依然是模拟题但相比A题会多一些规则。通常是一个字符串或数组按某个规则进行变换或判断数据范围不大直接按题面模拟即可。这场的B题我印象比较深的是规则里有一个“循环”的概念处理起来要特别注意边界比如下标越界、循环次数为0、空串输入等。写B题时我最常用的方式是拆函数。把题面里描述的规则拆成独立的判断函数比如“是否满足条件”“下一步应该移动到哪个位置”然后主函数只是按流程调用。这样做有几个好处一是逻辑清晰不容易漏规则二是如果WA了可以直接定位是哪一步的辅助函数写错了。边界处理上我总结了一个清单每次写模拟题都过一遍循环变量是否可能从0开始还是从1开始字符串或数组的长度为1时逻辑是否正确数据范围里提到的最大值和最小值情况是否覆盖操作顺序是否严格按照题面描述有没有被样例“带偏”。B题还有一个常见坑就是输出格式。有的题要求输出空格分隔有的要求换行分隔有的要求固定保留几位小数。这场的B题没有小数问题但我见过太多人在输出格式上吃WA。我的建议是提交前最后十秒专门检查输出那一行不要改完逻辑就急着交。3. C题从暴力到最优的思维跳跃3.1 题目分析与常见误区C题是这场比赛的第一个分水岭。题意简单概括是给定一个序列让你统计满足某种配对条件的数量朴素做法是O(n^2)枚举所有数对数据范围稍微大一点就会超时。题目本身不难难的是你能不能第一时间意识到暴力会超时以及能不能快速切换到O(n log n)的优化思路。我先说说我最初看到这道题时的判断过程。首先看了一眼数据范围n到10^5级别O(n^2)是10^10肯定不行。接着想配对类的问题往往能用排序、哈希表、双指针、二分或者前缀和来优化于是开始逐个尝试。这题的核心是把条件拆开你会发现它其实是在问“有多少对数满足某种偏序关系”这种模型十有八九和排序脱不了干系。常见的误区有两个。第一个误区是没注意到“不同元素”的定义有的选手会理解成数值不同实际上题目说的可能是下标不同导致统计结果偏大。第二个误区是用了哈希表存值却没有处理好重复元素的计数多计数或者少计数都在所难免。赛后我翻了评论区不少选手都是卡在这两个点上。C题的坑提醒我思维题第一步不是想算法而是把题面里的每个限定词都翻译成数学条件。条件翻译对了算法自然就浮出水面条件翻译错了就算用上再高级的数据结构也是错。3.2 排序加双指针优化思路讲一下这道C题的最终解法。我们先把数组排序这样原本无序的配对条件就变成了有序序列上的区间查询问题。针对每个位置i我们需要找到满足条件的最大右边界然后累计数量。因为数组有序右边界随着i增大只会单调右移所以我们用一个指针维护这个边界即可这就是经典的双指针解法。复杂度方面排序是O(n log n)双指针扫描是O(n)整体是O(n log n)在n为10^5时完全够用。代码实现上双指针有一个细节需要注意每次i移动后右边界指针不应该回退而是从当前位置继续向右扩展。如果你每次让指针重置复杂度又变回O(n^2)了。我还想补充一个用二分替代双指针的写法。对于每个i用二分查找最大的满足条件的j复杂度是O(n log n)加排序的O(n log n)也能过。二分的代码有时候比双指针更容易写对尤其当你对双指针的边界不熟的时候。我在比赛里用的是双指针但赛后试着用二分实现了一遍发现两个做法的时间相差不大。C题如果做不出来我建议先别急着看题解自己把排序和双指针这两个基础内容吃透然后总结一下“统计配对”这类题的常见套路。这类题的变种包括两数之和、三数之和、区间计数、子序列计数本质上都是一个思路学会了能一打十。4. D题动态规划与状态设计的经典套路4.1 状态定义与转移方程推导D题是这场ABC 442里最值得复盘的一道题它考的是动态规划的状态设计。这类DP题有一个共同特点题目给你一个序列或图结构要求你求某个最优值或方案数直接贪心是错的必须枚举状态。我当时的状态定义思路是这样先看题目的操作是“分阶段决策”的每个阶段会影响到后面的状态而且阶段之间有明显的前后依赖。我定义dp[i][j]为处理到前i个元素、当前处于某个状态j时的最优答案。关键是j有几个取值、每个取值代表什么意思这里一定要画图理清楚不能用眼睛看。转移方程的推导可以这样展开对于第i个位置它可以从第i-1个位置转移过来而转移时根据前一个状态的不同会有不同的代价或收益。把这些代价整理成公式就是dp的转移方程。写转移方程时我犯了一个典型的错误转移顺序写反了导致后更新的状态覆盖了还没用到的旧状态。这个问题在滚动数组的写法中尤为常见后面我会详细说。我在代码里通常会用-INF初始化所有状态然后用一个循环正常转移。如果你发现最终答案是0或者一个很离谱的大数很可能不是转移方程错了而是初始化或者状态枚举的起点错了。D题我第一次提交WA就是因为初始化起点设错了整个状态图全乱了好在最后排查出来了。4.2 空间优化与实现注意事项D题的数据范围如果很大比如n到2000以上dp数组直接开二维可能会超内存。这时候需要用滚动数组优化成一维或者至少把第一维压缩成两个交替使用的状态。滚动数组是DP实现里的经典技巧但在ABC这种短平快的比赛里也是WA高发区。最常见的问题是你在更新dp[i % 2][j]的时候用到了dp[(i-1) % 2][k]但如果某一个j没有被更新到它残留着上上轮的数据就会导致转移错误。我的习惯是每轮开始前先把当前要写的这一行全部重置成初始值再执行转移。有些选手为了省这几行代码结果WA了三四发得不偿失。D题的代码量其实不大但逻辑密度很高。我写完之后没有马上提交而是手工推了三组数据一组是题面样例一组是边界情况比如n1一组是自己构造的最坏情况。这三组数据过了我才敢提交。这个习惯在D题这种中等题上尤其重要因为WA一发就要等五分钟penalty太影响排名了。如果你感觉自己DP题总是卡住我强烈建议练一下“状态图”方法把每种状态画成节点把转移画成有向边然后从图上检查是否有遗漏的边。这个方法在遇到复杂DP时特别管用比空想转移方程靠谱得多。D题我一开始状态设计得不够细后来补了一个维度才顺利通过靠的就是画状态图。5. E题进阶算法的攻坚指南5.1 识别题目背后的算法模型E题这次属于“模型一眼可见实现地狱难度”的题。题目表面上是区间查询或区间修改实际上考的是一个标准的数据结构模型。看到这种题首先要判断的是用线段树、树状数组、并查集、平衡树还是分块这个判断直接决定了你能不能在比赛时间内写完。我当时识别模型的方法是看操作类型。如果题目只有单点修改加区间查询树状数组就能搞定如果有区间修改加区间查询线段树加懒标记是常规方案如果涉及集合合并和连通性问题并查集往往是正解。这场的E题的模型偏向区间最值或区间第k大类的问题所以正解是线段树。顺便提一句E题的整体感觉让我想起ARC076那场的某道经典题同样是数据结构优化同样是对懒标记的理解深度有很高要求。如果你刷过ARC076那道题这场的E题应该会感觉亲切一些。做题多的人往往会在这种时刻体会到“题感”这种东西——它其实是你见过的模型足够多之后的自然反应。5.2 线段树实现的常见陷阱线段树的实现看起来模板化但这场的E题把几个常见的坑全部踩了一轮。第一个坑是懒标记的累积规则。区间修改时懒标记不仅能“覆盖”还可能“叠加”这取决于操作的类型。如果叠加规则写错查询结果就会偏大或偏小而且这种错误很难用样例发现因为样例通常覆盖不到复杂的多次叠加。第二个坑是数组大小。线段树的数组一般是4倍空间这个大家应该都知道但问题是如果build或者update时用了错误的边界比如写成r1而不是r就可能越界访问导致本地能过、提交就RE。我的经验是在实现线段树时统一采用左闭右闭区间每次递归前先判断lr这样可以减少很多边界错误。第三个坑是查询区间与修改区间完全不相交的情况。很多线段树模板是在函数入口判断如果当前节点区间完全在查询区间外就返回但如果你把判断条件写反了就会导致递归永远不终止最后栈溢出。这个错误我在E题调试时遇到过花了不少时间才意识到是判断条件的问题。E题这种题想提速没有捷径就是大量刷题把模板写熟。我推荐你手写线段树不要复制模板每个字母都自己敲敲到形成肌肉记忆这样比赛时就能把精力集中在题目分析而不是写代码上。如果你还没有自己的线段树模板建议花一个下午把它彻底吃透包括建树、查询、区间修改、单点修改、懒标记这些都是ABC高阶题的常客。关于时间优化E题还有一个容易被忽略的点输入输出。当数据量比较大的时候建议使用scanf/printf或者关闭同步的cin/cout否则很容易因为IO太慢导致TLE。这次我的E题代码核心逻辑没有问题但第一次提交居然因为忘了加ios::sync_with_stdio(false)被卡了100ms左右差点超时真的很冤。6. 参赛常见问题与调试技巧实录6.1 WA、TLE、RE的排查思路每次比赛复盘都能看到大量WA、TLE、RE。我把这三类错误做一个速查表方便你对照排查。错误类型常见原因排查方向WA状态转移顺序错误重新画状态图检查每一条转移路径WA边界条件遗漏补测n1、空串、最大/最小值数据WA题面理解偏差回读题面尤其注意“不同”“最多”等限定词TLE算法复杂度超标确认是否用O(n^2)替代了O(n log n)TLE输入输出未优化加ios::sync_with_stdio(false)或改用scanfTLE递归层数过深或常数过大改成迭代或精简线段树操作RE数组越界检查所有下标尤其线段树边界RE栈溢出检查递归终止条件避免无限递归RE除零或未初始化检查分母、初始化所有变量我的排查顺序是先看错误类型如果TLE就先优化复杂度如果WA就先检查样例之外的自造数据。不管什么错误我都不建议在没想清楚之前乱改代码。每一次提交都应该带着一个明确的假设。6.2 高效的本地测试与数据生成方法这里分享一个我在比赛后复盘时常用的方法写一个数据生成器用暴力解法和小数据量去对拍。对拍是ACM圈里最经典的调试手段但在AtCoder这种不提供judge数据的平台上同样适用。做法很简单写一个solve_brute.cpp用最简单的思路解题确保结果正确写一个solve_fast.cpp用你比赛时的优化解法写一个gen.cpp随机生成小范围数据写一个对拍脚本循环执行生成数据 → 用两个程序分别跑 → 对比输出。如果两边输出不一致再把那组数据缩小到最小复现规模然后单步调试solve_fast。这个方法几乎可以解决所有WA和边界问题。我这次D题就是通过这个方法发现了状态初始化的问题暴力解法和我比赛时的解法在n3时结果不一样顺着diff的数据一行行排查最终定位到问题。对拍脚本我一般在脚本环境里用循环写语言不限核心逻辑就是生成数据、运行程序、比较输出、出现差异就停止。对于TLE问题我还会加一个计时命令统计solve_fast在最大数据规模下的运行时间如果超过0.5秒说明常数优化还有空间。最后再提醒一下对拍要用随机数据但也要用定向构造的边界数据。比如你已经猜到某道题可能卡某个边界就专门写一个生成器构造那种边界而不是只靠随机碰运气。好的测试应该是有针对性的不是跑一万组随机数就叫充分测试。打比赛这种事儿最怕的就是“我本地能过”四个字。你永远不知道judge上藏着什么数据。多花五分钟做对拍和边界测试省下来的是更稳的AC和更漂亮的排名。我见过太多人因为少测一组n1的数据丢掉了一道题真的很可惜。这周的ABC 442刷完最大感受是做题的节奏感比做出一道难题重要得多。如果你能稳住前半小时拿掉A、B、C后面D和E的做题体验会完全不一样。希望这份复盘能给你带来一些参考下次ABC赛场见。
