这周刷了一套 AWC 0017 Beta 的题单从 A 到 E 五题完整走了一遍。先说结论这是一场难度梯度非常舒服的周赛题单A 题考的是最基础的取模与整数溢出意识B 题是差分数组的板子题C 题是经典的“截止日期 奖励最大化”贪心D 题是网格路径计数的二维 DPE 题则是线段树维护最大连续子段和。从纯签到到需要一点数据结构功底五道题几乎把竞赛入门阶段最常碰到的几类模型都串了一遍。如果你是刚开始接触算法竞赛或者想系统练一下贪心、DP 和基础数据结构这套题单值得认真复盘。我写这篇东西的目的不是为了让你背代码而是把我拿到题之后怎么一步步想清楚解法、选择数据结构、最后敲出来的过程讲明白顺带把代码实现里容易翻车的点标出来。这篇文章按题号逐步拆解每道题都会给题目大意、思路推导、参考代码和复杂度分析最后再单独整理一份排坑记录。1. 赛题速览与难度分布1.1 五道题的知识点地图先给一张总览表方便你在刷题前对整体难度有个心理预期题号核心知识点大致难度拿分关键A取模检测、整数溢出签到题用 long long别用 int 直接乘B差分数组、前缀和基础题理解区间加转为端点修改C贪心、优先队列小根堆中档题排序后按截止日期动态淘汰D动态规划、滚动数组中档题状态定义和障碍处理顺序E线段树、区间信息合并进阶题维护四个字段而非一个答案这个安排其实是很有讲究的。A 题让大家在开局拿分建立手感顺便提醒所有人“乘法用 long long”这个老生常谈的问题。B 题把差分数组放在这里很妙因为差分是后续很多数据结构题的基础如果不理解“区间操作转端点修改”的思路后面遇到高级数据结构会非常吃力。C 题是整场的分水岭。它表面上是排序加模拟实际上需要你意识到“当已选任务数量超过当前截止日期时必须放弃一个任务而放弃的永远应该是最小奖励”。D 题回到动态规划经典的左上到右下路径计数属于 DP 入门必修课。E 题直接跨到线段树而且不是简单的区间求和而是要求维护最大连续子段和这个模型在很多进阶题里都会反复出现。1.2 这套题单适合谁、怎么刷如果你是刚接触算法竞赛的选手我建议你先跳过 E 题把 A 到 D 完整写出来尤其是 B 题的差分和 D 题的 DP这两类题几乎在每场比赛中都会以不同形态出现。C 题的贪心如果你能自己想到排序加堆说明你的思维已经超过很多同龄选手了。如果你已经会线段树、树状数组这些基础数据结构E 题的核心价值在于“信息合并”。线段树不是只能维护 sum、max、min 这类单一字段E 题要求你用四个字段互相配合这是从“会用线段树”到“理解线段树”的关键一步。刷题方式上我建议每道题先自己写一遍再看题解比对。尤其是 C 题我见过不少人第一次看到“堆大小大于截止日期就弹出最小奖励”时完全反应不过来但当你把样例手算一遍后这个操作会变得非常直觉。2. A题与B题热身阶段怎么稳拿分2.1 A题取模运算与整数溢出先说 A 题的题面。给定三个正整数 A、B、C其中 1 ≤ A, B ≤ 10^91 ≤ C ≤ 10^4判断 (AA BB) 能否被 C 整除能则输出 YES否则输出 NO。这道题本身不难但藏了一个很经典的坑整数溢出。A 和 B 最大到 1e9相乘以后达到 1e18 量级这早就超出了 int 的表示范围。int 上限大概是 2.1e91e18 会直接溢出成别的值导致判断错误。正确做法是全程使用 long long。代码非常简单#include bits/stdc.h using namespace std; int main() { ios::sync_with_stdio(false); cin.tie(nullptr); long long A, B, C; cin A B C; long long sum A * A B * B; if (sum % C 0) cout YES\n; else cout NO\n; return 0; }你可能会想这题不是在考取模吗其实它更想提醒你取模之前先保证数值没有溢出。实际写的时候我也建议先分别对 C 取模再合并因为 (AA BB) % C 等价于 ((A%C)(A%C) (B%C)(B%C)) % C在 C 很大时能进一步防止中间数值暴涨。虽然这道题用 long long 就够了但这个习惯在后续很多题目里能帮你少调试很久。2.2 B题差分数组解决区间加B 题是个很典型的差分题。给你一个长度为 N 的数组初始全是 0然后有 M 次操作每次操作把区间 [L, R] 内的每个元素加上 X最后输出整个数组。数据范围是 N, M ≤ 2e5X 的绝对值可以到 1e9。如果你没接触过差分第一反应可能是直接两层循环从 L 到 R 挨个加 X。但这样最坏复杂度是 O(N*M)当 N 和 M 都是 2e5 时会直接超时。差分的思路是不直接在区间内部修改而是只在端点打标记。开一个差分数组 diff每次操作时让 diff[L] Xdiff[R 1] - X。所有操作结束后对 diff 做一遍前缀和得到的就是最终数组。为什么这样是对的你把 diff 数组看成相邻元素的差值前缀和就是把差值还原回原数组。区间 [L, R] 同时加上 X等价于在 L 位置引入一个正的增量在 R 1 位置引入一个负的增量中间所有元素的值在累加过程中自然就带着 X 了。代码#include bits/stdc.h using namespace std; int main() { ios::sync_with_stdio(false); cin.tie(nullptr); int n, m; cin n m; vectorlong long diff(n 2, 0); for (int i 0; i m; i) { int L, R; long long X; cin L R X; diff[L] X; diff[R 1] - X; } for (int i 1; i n; i) { diff[i] diff[i - 1]; cout diff[i] \n[i n]; } return 0; }这里有两个小细节容易踩坑。第一diff 数组要开到 n 2因为当 R 等于 n 时R 1 会访问到 n 1如果你只开 n 的大小会越界。第二最终输出时要用 long long因为区间可能被反复加很多次累加结果很容易超出 int 范围。我在实际写 B 题时会习惯性把所有累加变量都定义成 long long。宁可在不需要的地方多耗一点内存也不要让一次溢出毁掉整个提交。3. C题靠推理而不是枚举的任务安排3.1 题目还原与数据范围C 题是这套题单里最有教学价值的一道。题意大概是有 N 个任务每个任务有两个参数 d_i 和 v_i表示第 i 个任务必须在第 d_i 天或之前完成完成后获得奖励 v_i。每天最多完成一个任务每个任务耗时一天求能获得的最大总奖励。数据范围 N ≤ 2e5d_i 可以很大v_i 是正数。这道题第一眼看上去像排序也有点像 DP但 N 到了 2e5DP 的 O(N^2) 肯定是过不去的。正确的方向是贪心加优先队列。3.2 排序 小根堆的推理过程我把任务按截止日期 d_i 从小到大排序然后维护一个小根堆 pq堆里存的是“当前已经入选的任务奖励”。每处理一个任务时先把它的奖励 push 进堆然后立刻检查堆的大小是否超过了当前任务的截止日期 d_i。如果超过说明在 d_i 天之前我们不可能完成这么多任务必须放弃一个。放弃谁呢很明显应该放弃奖励最小的那个所以弹出堆顶。这个做法的正确性可以这样理解当我们按截止日期从小到大扫描时堆里所有任务的截止日期都不超过当前 d_i。如果堆里任务数量大于 d_i那么无论怎么安排一定至少有一个任务无法在期限内完成必须剔除一个。剔除哪个对后续影响最小剔除奖励最小的那个。因为后续任务截止日期不会比当前更早已经剔除的任务不可能重新变得“合法”所以这个决策不会错。我举个例子。假设有 5 个任务任务截止日期 d奖励 v13502260317044405280按截止日期排序后顺序为任务3d1, v70任务2d2, v60任务5d2, v80任务1d3, v50任务4d4, v40。扫描过程处理 d1, v70堆 {70}堆大小 1 不大于 1保留。处理 d2, v60堆 {60, 70}堆大小 2 不大于 2保留。处理 d2, v80堆 {60, 70, 80}堆大小 3 大于 2弹出最小值 60堆变成 {70, 80}。处理 d3, v50堆 {50, 70, 80}堆大小 3 不大于 3保留。处理 d4, v40堆 {40, 50, 70, 80}堆大小 4 不大于 4保留。最终答案是 40 50 70 80 240。可以自己验证一下这四个任务分别安排在第 1、2、3、4 天完全满足各自的截止日期所以 240 是可达到的而且没有更优方案。3.3 参考代码与复杂度#include bits/stdc.h using namespace std; int main() { ios::sync_with_stdio(false); cin.tie(nullptr); int n; cin n; vectorpairint, long long jobs(n); for (int i 0; i n; i) { int d; long long v; cin d v; jobs[i] {d, v}; } sort(jobs.begin(), jobs.end()); priority_queuelong long, vectorlong long, greaterlong long pq; for (auto job : jobs) { pq.push(job.second); if ((int)pq.size() job.first) { pq.pop(); } } long long ans 0; while (!pq.empty()) { ans pq.top(); pq.pop(); } cout ans \n; return 0; }时间复杂度是 O(N log N)主要来自排序和堆操作。空间复杂度 O(N)。这里有一个容易忽略的点priority_queue 默认是大根堆我需要小根堆所以要写成greaterlong long。如果你用的是大根堆弹出的会变成最大奖励那就全错了。每道题里定义清楚堆的性质比写完再调试高效得多。我还想多说一句这题也有一个倒序写法从最后一天往回扫维护一个大根堆每天把新到期的任务入堆然后弹出最大奖励。两种写法本质是同一个贪心思路你掌握其中一种就够用了。4. D题网格路径计数的DP写法4.1 状态设计与转移方程D 题是经典的网格路径计数。给你一个 H 行 W 列的网格每个格子要么是空地.要么是墙壁#。你从左上角 (1,1) 出发每次只能向右或者向下走一步要求走到右下角 (H,W)路上不能经过墙。输出不同路径数量对 1e97 取模的结果。H 和 W 最大都是 2000。看到这种题条件反射就是 DP。定义 dp[i][j] 表示从起点走到 (i,j) 的路径数量。因为只能向右和下移动所以到达 (i,j) 的上一步只可能来自 (i-1,j) 或 (i,j-1)。转移方程就是如果 (i,j) 是墙dp[i][j] 0否则 dp[i][j] dp[i-1][j] dp[i][j-1]边界条件 dp[1][1] 1前提是起点不是墙。这里为什么不需要记忆化搜索或者更复杂的图论算法因为移动方向被限制成向右和向下状态之间不会形成环天然满足 DP 的无后效性。换句话说你不可能从 (i,j) 再回到 (i-1,j)所以按行从上到下、每行从左到右遍历就足够了。二维版本代码#include bits/stdc.h using namespace std; const long long MOD 1000000007; int main() { ios::sync_with_stdio(false); cin.tie(nullptr); int h, w; cin h w; vectorstring g(h); for (int i 0; i h; i) { cin g[i]; } vectorvectorlong long dp(h, vectorlong long(w, 0)); dp[0][0] (g[0][0] . ? 1 : 0); for (int i 0; i h; i) { for (int j 0; j w; j) { if (i 0 j 0) continue; if (g[i][j] #) { dp[i][j] 0; continue; } if (i 0) dp[i][j] (dp[i][j] dp[i - 1][j]) % MOD; if (j 0) dp[i][j] (dp[i][j] dp[i][j - 1]) % MOD; } } cout dp[h - 1][w - 1] \n; return 0; }4.2 滚动数组优化与边界处理二维数组在 HW2000 时占用 4e6 个 long long也就是 32MB在大多数平台的限制下是可以接受的。但如果你想把空间压到 O(W)就可以用滚动数组优化。因为 dp[i][j] 只依赖上一行的 dp[i-1][j] 和当前行左侧的 dp[i][j-1]我们只需要保存一整行的值。状态用一维数组 dp[j] 表示“当前已经遍历到的位置第 j 列对应的路径数量”。具体做法是每行从左到右遍历dp[j] 本身保存上一行同列的值加上 dp[j-1] 就相当于从上方和左方两个方向累加。滚动数组版本#include bits/stdc.h using namespace std; const long long MOD 1000000007; int main() { ios::sync_with_stdio(false); cin.tie(nullptr); int h, w; cin h w; vectorstring g(h); for (int i 0; i h; i) { cin g[i]; } vectorlong long dp(w, 0); dp[0] (g[0][0] . ? 1 : 0); for (int i 0; i h; i) { for (int j 0; j w; j) { if (i 0 j 0) continue; if (g[i][j] #) { dp[j] 0; continue; } if (j 0) dp[j] (dp[j] dp[j - 1]) % MOD; } } cout dp[w - 1] \n; return 0; }这个写法里的墙处理非常关键。当遇到墙时直接把 dp[j] 清零这样右侧的格子就不能再从墙“穿过”来上方下来的路径也会被强制切断。我最初写滚动数组时曾经忘了在墙的位置清零导致整个网格下半部分全部多算样例都过不了。还有一个边界问题如果终点本身是墙或者起点是墙答案应该直接是 0。上面代码里 dp[0] 在起点是墙时已经置为 0所以基本上能正确处理但我建议你在做题时单独判断一下逻辑会更清楚。D 题的启示其实很简单当题目限制移动方向时不要总想着搜索先考虑 DP当空间吃紧时想想每一行状态的依赖关系通常都能用滚动数组压掉一维。5. E题线段树维护最大连续子段和5.1 为什么要维护四个字段E 题是这套题单里最有分量的题。题意是维护一个长度为 N 的整数数组支持两种操作单点修改某个位置的值以及查询某个区间内“最大非空连续子段和”。N 和操作次数都可以到 2e5。如果只是查询区间和线段树每个节点只需要存一个 sum 字段。但最大连续子段和不一样一个区间的最大子段可能有三种情况完全在左半部分、完全在右半部分、跨越左右两个半区。前两种可以直接用左右子节点的答案跨种情况则需要知道左半部分的最大后缀和右半部分的最大前缀。所以线段树的每个节点需要存四个字段sum区间总和lmax区间内最大前缀和rmax区间内最大后缀和all区间内最大连续子段和叶子节点比较简单因为只有一个数 v所以 sum、lmax、rmax、all 都是 v。注意这里是非空连续子段所以即使 v 是负数all 也只能是 v不能是 0。5.2 合并规则与查询套路合并两个相邻区间时公式是固定的sum 左.sum 右.sumlmax max(左.lmax, 左.sum 右.lmax)rmax max(右.rmax, 右.sum 左.rmax)all max(左.all, 右.all, 左.rmax 右.lmax)我来解释一下 lmax 为什么这样算。一个区间的最大前缀和要么完全落在左区间内部那就是左.lmax要么从最左边开始把左区间整个都包含进去再延伸到右区间的前缀部分那就是左.sum 右.lmax。两者取最大就是答案。rmax 的逻辑是完全对称的。all 的计算是最后一步。三种情况分别对应完全在左、完全在右、跨越中点。跨越中点的子段等于左区间的一个后缀加上右区间的一个前缀也就是左.rmax 右.lmax。这些合并公式可以用一个 merge 函数封装起来这样建树、单点修改、区间查询都会简单很多。struct Node { long long sum, lmax, rmax, all; }; Node mergeNode(const Node a, const Node b) { Node c; c.sum a.sum b.sum; c.lmax max(a.lmax, a.sum b.lmax); c.rmax max(b.rmax, b.sum a.rmax); c.all max({a.all, b.all, a.rmax b.lmax}); return c; }对于查询操作我习惯写一个递归版本按照当前节点区间与查询区间的关系分三种情况处理如果查询完全覆盖当前区间直接返回该节点如果查询只在左半递归左半只在右半递归右半跨中点则合并两个递归结果。这个写法避免了设计“空节点”的麻烦因为任何一层递归都保证查询区间和节点区间有交集。5.3 参考代码与复杂度#include bits/stdc.h using namespace std; struct Node { long long sum, lmax, rmax, all; }; int n, q; vectorNode tree; Node mergeNode(const Node a, const Node b) { Node c; c.sum a.sum b.sum; c.lmax max(a.lmax, a.sum b.lmax); c.rmax max(b.rmax, b.sum a.rmax); c.all max({a.all, b.all, a.rmax b.lmax}); return c; } void build(int node, int l, int r, const vectorlong long a) { if (l r) { tree[node] {a[l], a[l], a[l], a[l]}; return; } int mid (l r) / 2; build(node * 2, l, mid, a); build(node * 2 1, mid 1, r, a); tree[node] mergeNode(tree[node * 2], tree[node * 2 1]); } void update(int node, int l, int r, int pos, long long val) { if (l r) { tree[node] {val, val, val, val}; return; } int mid (l r) / 2; if (pos mid) update(node * 2, l, mid, pos, val); else update(node * 2 1, mid 1, r, pos, val); tree[node] mergeNode(tree[node * 2], tree[node * 2 1]); } Node query(int node, int l, int r, int ql, int qr) { if (ql l r qr) return tree[node]; int mid (l r) / 2; if (qr mid) return query(node * 2, l, mid, ql, qr); if (ql mid) return query(node * 2 1, mid 1, r, ql, qr); return mergeNode( query(node * 2, l, mid, ql, qr), query(node * 2 1, mid 1, r, ql, qr) ); } int main() { ios::sync_with_stdio(false); cin.tie(nullptr); cin n q; vectorlong long a(n 1); for (int i 1; i n; i) { cin a[i]; } tree.resize(4 * n 5); build(1, 1, n, a); while (q--) { int op; cin op; if (op 1) { int p; long long x; cin p x; update(1, 1, n, p, x); } else { int l, r; cin l r; cout query(1, 1, n, l, r).all \n; } } return 0; }单点修改和区间查询都是 O(log N)建树 O(N)总体复杂度 O((N Q) log N)。空间上每个节点四个 long long4 * N 个节点在 2e5 的数据范围下完全够用。写这道题的时候我踩过一个坑合并查询结果时忘记先判断左右两边是否都参与了。如果我的写法是递归处理跨区间那么一定要确保左右两个子查询结果存在才 merge否则会拿一个不存在的节点和真实节点合并导致结果完全错误。上面代码里通过qr mid和ql mid两个分支已经排除掉这种情况但还是值得提醒你自己推一遍流程。最后补充一点这道题如果把单点修改改成区间加法那么合并公式依然成立但节点还要维护懒标记复杂度会显著上升。先吃透当前的四字段版本再考虑扩展会更稳。6. 排坑记录与做题节奏复盘6.1 最容易踩的坑速查表把这场 A-E 里值得记录的坑整理成一张速查表以后遇到同类题可以直接对照位置坑点解决办法A 题int 相乘溢出使用 long long必要时先取模B 题diff 数组越界数组开到 n 2R 1 一定安全C 题堆类型用错明确需要小根堆用 greaterC 题堆为空时 pop每次 pop 前判断 sizeD 题墙的位置没清零遇到墙直接赋 0切断路径D 题起点/终点是墙初始化 dp[0][0] 前先判断字符E 题合并顺序错误lmax/rmax/all 依次计算不要漏左.rmax 右.lmaxE 题查询时未区分单边/跨区间先判断查询区间落在左右哪侧再决定是否 merge我自己当年刚开始写这类题时最喜欢在“整体思路对但实现细节崩”的地方丢分。尤其是 E 题这种代码量比较大的题目如果调试时只看样例不自己构造极端情况很容易漏掉负数和跨区间的情况。建议每题至少自测三组数据全部正数、全部负数、正负交替。6.2 时间分配与做题策略A 题和 B 题属于热身题正常情况下应该控制在 20 分钟以内。C 题如果思路顺畅30 分钟左右能写完。D 题是经典 DP25 到 40 分钟都是正常范围。E 题作为压轴建议留至少 50 分钟因为线段树代码长写完后还要调试和构造自测数据。如果你的目标是刷完整套题而不是追求排名我还有一个建议先把所有题读一遍然后按 A、B、C、D、E 的顺序写。千万不要倒着做否则容易在 E 题上卡太久导致后面连 B 题这种送分题都没时间写。如果 C 题卡住了我的习惯是回头看看题目里的约束和数据范围。看到 N ≤ 2e5基本可以排除 O(N^2) 的 DP 和直接模拟看到 d_i 很大就应该联想到“排序后贪心”或者“数据结构维护动态集合”。数据范围从来不是摆设它是在给你提示算法复杂度。6.3 一些题外话和个人习惯最后说点题外话。刷完这一套 AWC 0017 Beta我最大的感受是E 题的那套线段树四字段合并公式值得你亲手多敲几遍不要只是看懂。看懂和能默写之间隔着至少五遍的重复这种手感只能靠敲出来积累。我自己在写线段树时习惯先把 mergeNode 函数写完并验证一遍再写 build 和 update。因为后面所有操作都依赖合并逻辑合并逻辑一旦错误建树和查询全是错。代码里我也会用字母 l、r、mid 这些常规命名减少思维切换成本。这套题单刷完之后你还可以自己尝试扩展把 C 题的截止日期改成“必须连续完成且不能中断”这就会变成另一道综合题把 D 题加上若干不能走的方向把 E 题的单点修改改成区间加法并引入懒标记。每扩展一步你对基础算法的理解就会更扎实一层。希望这篇题解对你有用也欢迎你在评论区聊聊你对哪道题印象最深。