打完Codeforces 1072 Div3我在小房间里坐了很久盯着六道题发愣。这轮比赛让我非常直观地看到“Div3”这个标签到底意味着什么它不是说题目简单而是说题目结构足够友好——A到F从纯签到到压轴DP优化刚好给所有水平的人留了一个可攀爬的阶梯。尤其是最后一题叫“Artistic Partition”光看名字就很艺术但实际拆开之后它的内核反而比前几题更纯粹。这篇文章就是我的赛后复盘不搞虚的直接按记忆梳理ABCDEF六道题的做法、思路拐点、以及我踩过的坑顺便聊聊Div3这种赛制最适合怎么用来练功。1. 赛前读题与时间轴先给ABCDEF画好难度地图先别急着开打。每次Div3我最大的建议都是先花两分钟把六道题全部看一遍在草稿纸上写下每道题的大致类型。这比抢A题手速重要得多。这轮六道题的直观画像大概是这样的题目核心类型我预估的难度我实际完成时间A数学/规律签到3分钟B字符串模拟简单9分钟C二分/贪心中偏易22分钟D图论BFS中等35分钟E动态规划/状态压缩中偏难50分钟F区间划分DP优化难赛后补题为什么要把A题和F题放在同一张表格里因为Div3的核心价值就是难度梯度完整。你不需要为了看懂F题去读什么高深paper它前面五道题都在给你铺垫同一种思维模式怎么把题目条件一步一步压缩成可以计算的东西。读题阶段我特别注意看F题题名“Artistic Partition”。即使还没有题面光是“划分”这个词我就知道八九成和区间DP或者分组决策有关。所以我在精神上很早就开始准备DP的转移方程而不是等做到那一题才开始想。这就是读题地图的意义。注意Div3虽然叫Div3但它并不应该被轻视。F题和D题之间经常隔着一条巨大的鸿沟。如果你只想过题D题以后建议留足完整的一小时。2. AB题拿分速度决定整场比赛的心态上限A题永远是用来建立信心的但也最容易让人翻车。这场的A题是典型的数学找规律类题目题目给了一串变换规则问某个量最终是多少。拿到题那一刻我没急着写代码而是先用笔算了三个样例确认输出和样例完全吻合后才打开编辑框写了一个两行的循环。这种“先手动模拟”的方法在A题特别好用。因为A题通常不是你不会做而是你容易看错条件。比如这题里面有个条件是“每次操作必须同时改变两个数字”如果直接开始写模拟代码很可能把“同时”这两个字理解成“先后”导致输出永远差一个数。我在赛场上见到有人就在A题卡了十五分钟原因就是没有先手动推一遍样例。B题则是字符串模拟。说实话B题这场的味道很典型给你一堆字符串要求按某种规则合并或消除。它的难点不在算法而在于你想不想得到那个“只有一种合理解读”的边界情况。我做完之后复盘发现这道题本质上就是检查相邻字符的特定关系。这类题在Div3里常年霸占B位。string s; cin s; // 简单示例检查是否存在连续相同的字符 for (int i 1; i s.size(); i) { if (s[i] s[i - 1]) { // 处理某种操作 } }这段代码不是完整题解但我想说的重点是B题不要追求优雅解法要追求防御性写代码。在写循环的时候把边界条件全部用注释列出来空字符串、只有两个字符、重复字符串、所有字符都不相同。把这些case列完B题基本就不会罚时了。A和B的共用经验第一优先级是“样例全过 手推的小case也过”不是“代码写得漂亮”。两个题加起来控制在15分钟以内多花的时间都是从C题那里借来的。Div3的Penalty是跟着错误提交走的与其赌一把再交不如多花30秒检查一遍数组边界。3. C题先猜结论再证明是Div3的常用打法C题我做了22分钟不算快因为前半段我一直陷在“怎么把它写成一个标准算法”的泥潭里。题目大概意思是给定一个序列你需要找到某个最小或最大的分割点使满足某个条件。我第一反应是二分答案但推了一遍后发现问题不具备单调性。Div3的C题经常会出现这样的情况——它看起来像二分其实不是看起来像贪心其实也不是。处理这种题唯一靠谱的办法是先把结论猜出来然后快速验证。我当时是怎么做的我把题目条件在草稿纸上写成不等式然后试着调参数看结果变化。试到第三次的时候发现无论怎么调整最优解一定出现在某个固定极值的边界点。于是猜测答案也可能是边界值之一直接把边界值全部枚举一遍O(n)解决。这种“不做全量搜索只搜索边界”的思考方式说实话就是C题想要的。// 伪代码框架 for (int i 1; i n; i) { // 更新某种前缀状态 } long long ans INF; for (int i 1; i n; i) { // 用前缀状态和全局状态拼接答案 ans min(ans, f(pref[i], suff[i])); }这题让我意识到一件事Codeforces的Div3 C题并不会真的考你高级数据结构。它考的是你愿不愿意做纸面推导而不是急于打开编辑器。很多人在C题栽跟头不是能力不够而是太想直接写代码。我的习惯是当一道题在脑子里超过5分钟没有明确思路时强制自己停下来拿笔写两页纸的推导不管是画样例还是列公式总之不能双手放在键盘上发呆。提示Div3的C题经常埋了一个障眼法——它把所有条件都放在一个看起来很复杂的函数里但那个函数的性质比你想的简单得多。先把函数画成图像或者分解成多个独立的部分往往下一秒就豁然开朗。4. D题图论题的模型转换与邻接表细节D题在Div3里通常是个分水岭AC掉D题的基本上可以稳稳结束这场。这场的D题是一道图论题图上每个点有若干条边问题是判断从某一点出发能否在步数限制内到达所有合法点。第一眼我就知道要用BFS。但这里有一个关键的坑节点数和边数的上限非常大如果用邻接矩阵直接爆炸用vector邻接表没问题但需要对每个点的邻接表进行排序或者去重。另外这道题不是一个标准的单源BFS而是有多个起点并且每种状态的转移条件不一致。这类“非标准BFS”是Div3 D题的典型出题手法它不会要求你写SPFA或者Dijkstra而是希望你能看出来“核心图结构”其实是一个无权图。既然无权那就直接BFS。我在BFS时踩了个教训不要用vis数组标记整个图要标记“状态”。比如本题中同一个点可能通过不同路径被访问多次但只有当某个额外状态不一样时才是有效的。如果你只标记了坐标就会漏掉一些方向上的可达性。queuetupleint, int q; // 点 某种状态 int dist[N][K]; memset(dist, -1, sizeof(dist)); dist[Start][0] 0; while (!q.empty()) { auto [v, s] q.front(); q.pop(); for (int to : adj[v]) { int ns f(s); if (dist[to][ns] -1) { dist[to][ns] dist[v][s] 1; q.push({to, ns}); } } }这题给我最大的体会是写BFS之前一定要在纸上把“状态维度”定义清楚。不要被“节点”这个实体迷惑了。许多图论题节点本身不是状态节点步数奇偶性、节点某种开关状态才是真正的状态。如果你一上来就开个一维dist数组那大概率会在某个case上卡死。还有Div3的D题很少考复杂的图性质它更常考的是你能否把一个看似奇怪的约束翻译成BFS/DFS的额外维度。这个翻译过程就是模型转换。把模型转换做好了代码量其实不大。5. E题从一个怪异的条件想通状态设计E题通常就是Div3的“思路天花板”了。这一场的E题题意叙述得很绕——它给出一个数组要求从中选出若干个数使它们满足某个互斥条件并最大化某个价值。我一开始想的是贪心从大到小取划算但如果互斥那可能取小的更好。于是贪心瞬间崩塌。然后我想到排序后DP。设f[i]表示前i个元素能取到的最大价值转移时枚举上一个取的位置。这个复杂度是O(n^2)够呛但可以优化。关键问题是怎么把互斥条件变成一个可以高效转移的东西我尝试把互斥条件改写成“两个数相差小于某个阈值”。如果是这样那么排序之后满足互斥关系的两个数距离是相近的。经过分析后发现可以只枚举当前位的倒数几个位置。因为当距离超过某个上限以后两个数一定兼容没必要再当转移来源。改进之后DP变成O(n * k)k是一个很小的常数。这道题能AC核心不在于DP本身而在于能看出来“只有相邻的若干项需要转移”。这个洞察来自对约束条件的数感如果互斥只发生在很近的位置那等于把全场的视野缩小到了局部整个问题就从一个全局优化问题塌缩成了局部比较问题。这里我想多说一句Div3的E题很喜欢用“看似很大的条件实则很小”的方式出题。它们不会真让你设计一个nlogn的高级数据结构而是让你发现规模的虚假性。一旦意识到转移来源的上限很小代码实现就很简单了。另外如果你在赛场上想到一个DP但时间开销太大不要立刻放弃。先尝试在纸上写一下转移方程看它能不能被前缀和、单调队列或者邻域截断优化。这比自己硬憋一个O(nlogn)的怪算法快多了。6. F题Artistic Partition 的 DP 优化思路F题叫“Artistic Partition”我第一眼看到就笑了——这名字比题目本身还难翻译。题面大意是给定一个长度为n的数组a以及一个正整数k要求把数组分成k段partition每一段有一个代价这个代价等于段内不同数值的个数求所有段代价总和的最小值。你要让这个划分足够“艺术”也就是用最小的成本去框住所有的数字。说实话这个题面第一眼让我想到的就是“区间划分DP”。直接定义dp[j][i] 为前i个数划分成j段的最小总代价那么转移式非常自然dp[j][i] min(dp[j-1][p] cost(p1, i))其中p i。这个式子的正确性没有任何问题问题在于复杂度。如果直接做O(n^2 * k)n到1e5就完全不可行。所以这题核心就落在了“如何优化这个分割点搜索”上。我当时思考了三个可能的优化方向四边形不等式优化如果代价函数满足四边形不等式那么分割点具有决策单调性可以利用分治优化到O(k n log n)。数据结构优化用线段树或树状数组维护dp[j-1][p] 加上 cost(p1, i) 的最小值一边移动i一边更新cost。值域分块因为代价是当前区间内不同数字的个数可以考虑用双指针维护新加入一个数字对cost的影响。实测之后我会说对于这个题四边形不等式优化是最稳妥、最好写的路径。因为不同数字个数的函数天然满足“成本随区间拉伸而增加”的单调性而且它的交叉不等式也基本成立。只要你能证明或感知到位直接套分治优化模板就能把复杂度压下来。我赛后复现代码时用了一个经典的dc优化函数void solve(int l, int r, int optL, int optR, int dep) { if (l r) return; int mid (l r) 1; int bestPos optL; // 枚举p在 [optL, min(optR, mid)] 范围 // 计算 dp[dep-1][p] cost(p1, mid) 的最小值 for (int p optL; p min(optR, mid); p) { int val calc(p, mid, dep - 1); if (val dp[dep][mid]) { dp[dep][mid] val; bestPos p; } } solve(l, mid - 1, optL, bestPos, dep); solve(mid 1, r, bestPos, optR, dep); }要注意的是这个模板里的cost函数不能每次现算否则还是会退化。常见的做法是开一个指针数组随着mid的变化用双指针维护当前区间内不同数字的个数。这个过程需要精细的前移和缩进处理但写熟了之后其实非常机械。这里我分享一下我学到的调试技巧先写一个O(n^2 * k)的暴力DP跑小数据验证四边形不等式优化版本的结果与暴力完全一致然后再拿去跑大数据。没有这个验证你根本不知道是转移式写错了还是分治边界写错了或者还是指针维护错了。F题帮助我理清了一个很重要的概念很多DP优化的核心不是在优化“状态转移”本身而是在优化“候选分割点集合”。四边形不等式可以帮你把候选集合缩小到一条单调区间数据结构可以帮你直接维护所有候选点的最小值。两者本质上都是减少“无效计算”。7. 赛后复盘从AC到完全理解再到举一反三一场Div3打完比积分更重要的其实是后面的补题整理。如果打完就扔下一场的你并不会变得更强。我一般做三件事第一把每道题的错误原因记录下来。比如我C题一开始为什么走向错误方向因为我默认了二分答案一定单调没有回头验证。这样记录下来以后下次我就不会再犯“见二分手痒”的错误。第二把每道题的解法从“会用”变成“能讲给别人听”。我给F题写了一篇六行的题解笔记内容包括状态定义、转移方程、优化依据、复杂度分析。写到第三行时我发现自己对cost函数的性质其实不太确定于是又回去推了一遍。这个过程虽然痛苦但收获极大。第三做一道同等类型的加强版例题。比如F题用了决策单调性优化DP我赛后就会去题库里找一道类似“划分 代价函数 单调优化”的题不求秒杀只要能把状态转移方程独立写出来就算完成目标。这种习惯坚持下去你会发现Div3不仅仅是一场小比赛更是一套自带的训练教案。ABCDEF六个字母正好对应由浅入深的六个思维层次读题、模拟、猜结论、图论建模、状态设计、高级优化。每一题都比上一题多一点点思考量但又不至于让你望而生畏。我个人在实际操作中还有一个小技巧比赛结束后的三十分钟内趁热打铁把F题代码写出来。别管是不是AC只要能跑过自己构造的样例就算复盘成功。超过这半个小时你的大脑会倾向于“遗忘痛苦”第二天再补题会困难很多。所以如果你也正在用Codeforces的Div3练手我建议你不要只关心分数。试着把每道题都当成一次算法课A题学快速验证B题学边界检查C题学结论猜想D题学状态抽象E题学邻域剪枝F题学DP优化。一串六颗糖吃完下一场你会明显感觉到脑子转得不一样了。