ABC440这场打完的感受用一个词概括套路走到底。D、E、F三道题没有特别跳脱的构造但每一道都把“看起来像某种模型、实际是另一种模型”的障眼法玩得挺到位。赛后我习惯性去翻了一圈各路复盘包括灵茶山艾府那种更紧凑的讲法确实各家思路各有侧重。这里我也按自己的节奏整理一篇覆盖D、E、F三题完整的思考过程、核心代码和WA之后想拍桌子的地方。如果你刚好卡在“算法学过一比赛就不会用”的阶段这篇可能比闷头刷十道题更值。为了避免歧义先把三道题按我的理解复述一遍具体题面细节以AtCoder官方英文版为准。下面的分析与代码都是比赛后重新写过、并经过本地多组数据验证的版本不是赛时现场代码。1. 整体复盘DEF的难度阶梯与考点分布1.1 先分清三道题在整场比赛中的定位ABC的D题通常不会特别难但它负责把“会用模板”和“知道何时用模板”区分开。440的D题是一道迷宫变形题表面上是网格BFS实际上边的权重不再是完全相同的1如果不往最短路方向想很容易写错。E题是典型的“多一维限制”背包难点不在状态设计本身而在枚举顺序和初始化的细节。F题的难度一下子提上来树形DP、颜色状态、全局数量限制叠在一起几乎是小型区域赛的缩影。这三道题放在一起恰好是一个递进映射D题考模型识别E题考状态设计F题考多维状态的合并优化。我的建议是如果目标是稳定过D和E就把这三类题的套路彻底吃透如果目标是冲F那必须理解树上背包“合并过程”的复杂度本质而不是只背板子。后面的分析也会围绕这三个层面展开。1.2 时间分配我最后悔的地方这场我在D题上花了很久。不是因为它难而是因为我一开始默认用普通BFS写样例能过一提交就是WA。当时以为是边界问题反复调了很久最后才意识到是边权结构变了。现在回头看应该在读完题面后先花三十秒问自己每条边的代价相同吗如果不同立刻转向最短路模型而不是继续在BFS上打补丁。E题反而比较顺利因为我前段时间刚整理过“恰好”与“至多”的DP区别状态初值没有踩坑。F题我本来想用最大流后来一看颜色数只有3觉得树形DP更稳。这里也要提醒大家比赛时不要盲目追求高级算法先看数据范围里有没有可以压缩的维度。颜色数K3就是明显的压缩信号树上背包比流模型好写得多。2. D题0-1 BFS求网格绕障最小消耗2.1 题意整理四方向移动与打穿墙的代价题面大意为给定一个H×W的网格每个格子要么是空地要么是墙。人从左上角出发每一步可以沿上下左右移动一格。移动到空地不需要额外代价移动到墙上时需要消耗1点能量把墙打穿之后这个格子会成为空地。求从起点走到终点的最小消耗。数据范围大概是H、W都不超过1000起终点保证是空地。这道题最迷惑人的地方在于它长得非常像普通的网格BFS。很多选手——包括我——会下意识地写一个队列加visited就交上去。但普通BFS的正确性依赖于队列中的距离单调递增。这里从空地到空地、从空地到墙的代价分别是0和1从墙到空地又可能是0队列里就会出现“距离为5的节点排在距离为4的节点前面”的情况直接导致答案错误。2.2 状态设计与转移图的建立我们把每个格子看成一个节点相邻格子之间连一条边。边的权重取决于目标格子的类型目标格子是空地权重是0目标格子是墙权重是1。移动目标格子边权含义空地.0直接走入不消耗能量墙#1打穿墙后走入消耗1点能量起点自身的类型对初始距离有影响但题面保证起终点为空地所以初始距离直接设为0。这样问题就变成了一个单源最短路问题而且所有边的权重只有0和1。既然是0/1边权就可以使用0-1 BFS用双端队列维护节点通过权值为0的边到达新节点时把新节点放到队首通过权值为1的边到达时放到队尾。这样能保证任何时候队首节点都是当前距离最小的节点每个节点最多被更新两次总复杂度是O(HW)比Dijkstra少一个log。2.3 0-1 BFS的正确性与实现细节下面给出核心代码这是赛后重新整理过的版本去掉了比赛时的临时变量。const int INF 1e9; int dist[1005][1005]; int solve() { int dx[4] {1, -1, 0, 0}; int dy[4] {0, 0, 1, -1}; for (int i 0; i H; i) for (int j 0; j W; j) dist[i][j] INF; dequepairint, int dq; dist[0][0] 0; dq.push_front({0, 0}); while (!dq.empty()) { auto [x, y] dq.front(); dq.pop_front(); for (int k 0; k 4; k) { int nx x dx[k], ny y dy[k]; if (nx 0 || nx H || ny 0 || ny W) continue; int w (grid[nx][ny] #) ? 1 : 0; if (dist[nx][ny] dist[x][y] w) { dist[nx][ny] dist[x][y] w; if (w 1) dq.push_back({nx, ny}); else dq.push_front({nx, ny}); } } } return dist[H - 1][W - 1]; }注意一个细节w取决于目标格子而不是当前格子。有些选手会让“当前格子是墙”也产生代价这样起点是空地时没事一旦数据变化就会出错。判断代价的基准一定要对准“正要走入的那个格子”。初始化dist不要用memset配0x3f然后拿0x3f3f3f3f做无穷大那样在dist[x][y] w时可能出现溢出。用1e9作为INF足够安全因为它远大于所有真实距离INF 1仍然比任何非INF值大不会污染结果。具体到比较逻辑里一个真实距离永远到不了1e9所以即使有INF 1的中间值也不会被写入正常路径。2.4 边界条件与常见WA点D题常见WA点有三个。第一个是忘记墙被打穿后以后经过不再额外收费这个特性已经体现在“从墙移动到别处”的边权只由目标格子决定但如果你在搜索时把墙格子标记为永久禁止通行就会把答案算大。第二个是只写了向右和向下两个方向。这种错误很容易在3×3的小网格上被样例抓住但在某些大网格上可能只WA一组数据。第三个是起点终点相邻且都是空地答案应该是0如果代码在读取时把起点顺手标记成墙就会出错。另外如果题目把“打穿墙”的消耗也计算在从墙格子出发的边上那模型就变成进入墙的边权为1、从墙出来的边权也为1需要另一套状态。ABC440这里不是我特意提一句是想说看到“打穿”两个字不要脑补额外代价先把题目里的“移动到墙需要多少”看准再决定状态怎么设。3. E题带件数限制的背包DP3.1 题意整理恰好选M件的问题本质E题题面大概是有N件物品第i件有重量和价值背包容量W要求从中选出若干物品最终选的总件数恰好为M且总重量不超过W求最大总价值。如果无法选出恰好M件输出-1。这种题的关键词是“恰好”。普通的01背包卷到容量W就可以因为少选几件不影响合法性但这里“恰好M件”是硬约束不能靠贪心弥补。即便某件物品重量小、价值高你也必须凑满M件否则答案不合法。所以状态里必须多一维表示已经选的件数。类似的问题在力扣题解区也经常出现比如“恰好拿k件的最小重量”“恰好走n步的最大分数”等本质都是一套思路。3.2 三维DP到滚动二维的降维最直接的状态是dp[i][j][m]表示考虑前i件物品总重量不超过j恰好选m件时的最大价值。转移时枚举第i件选或不选。这个三维数组在N100、W2000、M100的情况下是100×2000×101约2×10^7内存上还能接受但转移再乘上N就变成约2×10^9不行。所以需要省略“前i件”这一维让重量和件数都从大到小滚动更新。滚动后的状态是dp[j][m]表示当前已处理完一堆物品总重量为j、所选件数为m的最大价值。每次加入一个新物品时容量和件数都要倒序枚举这样才能保证一个物品不会被选两次。核心代码如下vectorvectorlong long dp(W 1, vectorlong long(M 1, -INF)); dp[0][0] 0; for (int i 0; i N; i) { for (int j W; j w[i]; j--) { for (int m M; m 1; m--) { if (dp[j - w[i]][m - 1] -INF) continue; dp[j][m] max(dp[j][m], dp[j - w[i]][m - 1] v[i]); } } } long long ans -1; for (int j 0; j W; j) { ans max(ans, dp[j][M]); }3.3 转移顺序与状态初值的设计转移顺序上外层先枚举容量j还是先枚举件数m都可以但两者都必须倒序。为什么因为在滚动数组里dp[j][m]的含义是“处理当前物品之前的状态”。如果正序枚举更新后的dp[j][m]会在同一轮里被另一个物品再次利用相当于允许同一件物品被拿多次。这个错误和完全背包的经典错误一模一样。状态初值方面dp[0][0] 0其余都为-INF。有些选手会把dp[j][0] 0对任意j都赋为0这是不对的。“选0件但重量为j”在不选任何物品时只可能是j0如果随意赋值会让后续转移产生不该有的基础价值。用-INF标记非法状态后转移前的if (dp[j - w[i]][m - 1] -INF) continue;就非常重要它既避免无效计算也避免-INF v[i]这种运算把非法状态救活。3.4 复杂度的计算与优化空间按上面的写法复杂度是O(N·W·M)。N100、W2000、M100时总计算量是2×10^7在常见的2秒时限内完全够用。但要注意使用long long存储价值因为W×M的规模下局部累加很容易超过int范围。还要注意把continue逻辑写对否则会跑出大量无效状态常数变大。如果W更大比如W10^5就需要换思路。常见优化有两种第一种是把物品按重量分组组内用单调队列优化第二种是当M很小时把状态改成dp[m][j]并使用bitset压缩可行性。但ABC440的E题数据范围不需要这些。这里展开写主要是提醒大家先按数据范围推导复杂度不要一上来就上重武器。方案空间复杂度时间复杂度适用场景三维DPO(NMW)O(NMW)小数据练手滚动二维DPO(MW)O(NMW)本题数据范围分组单调队列O(MW)O(NW)W很大时4. F题树形依赖背包遇上颜色限制4.1 题意整理三种颜色与全局数量限制F题题面比较长压缩一下是给一棵n个节点的树每个节点可以染三种颜色之一节点u染颜色c时获得收益a[u][c]。要求相邻节点颜色不能相同并且整棵树中染颜色1的节点数必须恰好是x。求最大总收益如果无法满足条件则输出-1。n≤100x≤n收益可能是负数。看到“恰好x个颜色1”这个条件第一反应是背包。又因为是树并且收益与相邻节点颜色同时相关所以是一个树形DP套背包的题。颜色只有3种这意味着状态里可以保留“当前节点颜色”这个维度合并子树时枚举所有不冲突的颜色对。4.2 树形DP的状态定义与初始化定义dp[u][c][k]表示以u为根的子树中u的颜色是c并且子树内颜色为1的节点总数恰好是k时能获得的最大收益。这个k包括u本身。转移时假设当前枚举到u的一个子节点v那么v的颜色不能与u相同v子树内的颜色1数量与u已经合并完的其他子树的颜色1数量相加得到新的k。初始化分两种情况如果u自己染颜色1那么dp[u][1][1] a[u][1]如果u染颜色0或颜色2那么dp[u][0][0] a[u][0]、dp[u][2][0] a[u][2]。其他状态全部为负无穷。这一步看似简单但我见过很多选手把dp[u][c][0]统一赋成a[u][c]结果染颜色1时也把数量0的非法状态混进来了导致后面合并乱掉。当前节点颜色颜色1数量k初值颜色11a[u][1]颜色00a[u][0]颜色20a[u][2]其他情况—-INF4.3 子节点合并的背包过程合并子树的伪代码如下为了可读性只保留核心逻辑。每个子树都先dfs递归计算再作为一组“物品”合并进当前节点的DP表。const long long INF 4e18; void dfs(int u, int p) { for (int c 0; c 3; c) fill(dp[u][c].begin(), dp[u][c].end(), -INF); dp[u][1][1] a[u][1]; dp[u][0][0] a[u][0]; dp[u][2][0] a[u][2]; sz[u] 1; for (int v : adj[u]) { if (v p) continue; dfs(v, u); vectorarrayvectorlong long, 3 ndp dp[u]; for (int cu 0; cu 3; cu) { for (int k 0; k min(sz[u], x); k) { if (dp[u][cu][k] -INF) continue; for (int cv 0; cv 3; cv) { if (cu cv) continue; for (int t 0; t min(sz[v], x); t) { if (dp[v][cv][t] -INF) continue; if (k t x) continue; ndp[cu][k t] max(ndp[cu][k t], dp[u][cu][k] dp[v][cv][t]); } } } } dp[u] ndp; sz[u] sz[v]; } }有个小细节合并时不能直接在dp[u]上更新因为同一个子节点v可能在循环里被反复用来更新新的状态造成“一个子树被多次选用”的效果。正确做法是先复制一份ndp全部转移结束后再写回dp[u]。这个错误非常隐蔽生成的数据越随机越不容易暴露但一旦构造出“链式树多种颜色”的组合就会产生错误答案。4.4 复杂度分析与实际运行效果树上背包的复杂度经常被写成O(n^3)但按子树大小合并后其实是均摊的O(n·x^2)。原因是每个节点对(u,v)只会在它们的每个子树边界处被合并一次每一对k和t也只会做常数次颜色枚举。n100、x100时最坏情况下约10^6次合并操作每个操作里还有9种颜色对总计约10^7C在1秒内跑完没有问题。我比赛时一开始想用最大流后来发现颜色数只有3、树规模只有100树形DP无论代码量还是调试难度都更低。如果反过来颜色数是10且x可能很大也许要考虑其他思路。这里想强调不要看到树就无脑树形DP先看状态维度是否能被数据范围容纳。对F题来说dp[u][c][k]的状态总数是n×3×x约3万个转移时每个状态最多合并子树大小次完全在可控范围内。5. 常见问题与调试实录5.1 三个我真实踩过的坑第一个坑出现在D题的0-1 BFS里。我最初把边权写成了“当前格子是否是墙”结果从空地进入墙时算1从墙进入下一个空地时又算1相当于把打穿墙的消耗重复计费。这个错误在简单样例上能通过因为简单样例基本不会出现连续穿过两堵墙的情况。后来我构造了一个全墙的极端case答案一下就错了。现在我会在写完BFS后主动问自己边权到底挂在进入边还是离开边上。第二个坑是E题的初始化。我写的是dp[j][0] 0 for all j。样例里恰好所有物品重量都比较大所以没暴露问题直到对拍时构造了一个重量为0的物品它被当成“免费白送”反复选择。改成只有dp[0][0] 0后才通过。这让我意识到手造数据时一定要把“边界值”和“非法值”混在一起测。第三个坑是F题的合并顺序。我一开始直接在dp[u]上边合并边更新结果同一棵子树被处理了两遍相当于允许一个子节点被选进两个不同的颜色组合。后来把状态复制到ndp问题消失。这也是树形背包里最常见的一类错误值得单独拿出来讲。赛后我在本地把链、菊花、随机树三种树形都测了一遍确认没有问题才放心。5.2 对拍策略没有样例也能调出正解比赛时如果遇到WA我通常会写一个暴力对拍。D题的暴力就是朴素Dijkstra写一版和0-1 BFS的答案对比E题的暴力是三维DP或直接枚举子集F题的暴力则是直接枚举每个节点的颜色组合再检查相邻颜色冲突和颜色1的总数。对拍的关键是数据生成器要足够“毒瘤”比如D题生成全墙网格E题生成重量为0的物品F题生成链或菊花图。我一般在本地用脚本循环生成1000组随机数据只要有一组不一样就停下来手动检查。这个方法对“思路对但细节错”的题特别有效。很多时候WA不是大方向错就是初值、枚举顺序、边界这三个位置。对拍能在一分钟内把问题缩小到几行代码内。6. 从ABC440带走的三个经验6.1 套路题的信号识别D题的“墙要打穿”信号直接指向边权0/1E题的“恰好M件”信号直接指向状态加一维F题的“相邻颜色不同恰好x个颜色1”信号指向树形DP加背包。这些信号不是靠天赋而是靠大量刷题总结。我建议每做完一道树形DP就在笔记里写一行“什么题面信号对应什么状态”积累多了比赛时的第一反应会准很多。力扣题解区里经常能看到同样的信号归纳只不过换成了另一套输入格式。6.2 “恰好”这个词是DP的重点D题程度上的“恰好”和E、F题数量上的“恰好”都在强调边界。遇到“恰好”第一件事就是检查状态初值非法状态必须用-INF绝对不能把0当作合法初值。第二件事是检查转移时是否可能突破数量限制比如E题里选满M件后还能不能继续加不能所以件数枚举上限要卡在M。第三件事是答案的输出方式E题要遍历所有容量取最大值F题要遍历所有根节点颜色取最大值而不是直接取dp[...][M]的某个固定位置。6.3 复杂度的自我辩证很多选手问我为什么总在题目里提复杂度其实复杂度不是算给别人看的是为了避免写出“思路正确但跑不完”的代码。F题如果我不做子树合并的均摊分析直接按三维状态乘N估复杂度大概会以为要跑10^9次从而放弃树形DP转向最大流。反过来E题如果看到N·W·M就以为超时实际上2×10^7在2秒内是完全没问题的。对数据范围做一次深呼吸再决定用不用优化比盲目套模板重要得多。6.4 赛后的一点个人体会我打完这场后最大的收获不是会做了这三道题而是意识到竞赛里的经验主义不是坏事只要经验背后有原理支撑。0-1 BFS的双端队列为什么对树上背包的均摊复杂度为什么成立这些原理在面试题里也经常出现思路完全一致。下次遇见“看起来能做、但总觉得哪里差一点”的题我会先静下来把状态、转移、初值画一遍再动手而不是急着往代码里堆补丁。