企业官网建设流程全解析

这周刷了一套 AWC 0017 Beta 的题单，从 A 到 E 五题完整走了一遍。先说结论：这是一场难度梯度非常舒服的周赛题单，A 题考的是最基础的取模与整数溢出意识，B 题是差分数组的板子题，C 题是经典的“截止日期 + 奖励最大化”贪心，D 题是网格路径计数的二维 DP，E 题则是线段树维护最大连续子段和。从纯签到到需要一点数据结构功底，五道题几乎把竞赛入门阶段最常碰到的几类模型都串了一遍。

如果你是刚开始接触算法竞赛，或者想系统练一下贪心、DP 和基础数据结构，这套题单值得认真复盘。我写这篇东西的目的，不是为了让你背代码，而是把我拿到题之后怎么一步步想清楚解法、选择数据结构、最后敲出来的过程讲明白，顺带把代码实现里容易翻车的点标出来。这篇文章按题号逐步拆解，每道题都会给题目大意、思路推导、参考代码和复杂度分析，最后再单独整理一份排坑记录。

1. 赛题速览与难度分布

1.1 五道题的知识点地图

先给一张总览表，方便你在刷题前对整体难度有个心理预期：

这个安排其实是很有讲究的。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^9，1 ≤ C ≤ 10^4，判断 (AA + BB) 能否被 C 整除，能则输出 YES，否则输出 NO。

这道题本身不难，但藏了一个很经典的坑：整数溢出。A 和 B 最大到 1e9，相乘以后达到 1e18 量级，这早就超出了 int 的表示范围。int 上限大概是 2.1e9，1e18 会直接溢出成别的值，导致判断错误。

正确做法是全程使用 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 ≤ 2e5，X 的绝对值可以到 1e9。

如果你没接触过差分，第一反应可能是直接两层循环，从 L 到 R 挨个加 X。但这样最坏复杂度是 O(N*M)，当 N 和 M 都是 2e5 时会直接超时。

差分的思路是：不直接在区间内部修改，而是只在端点打标记。开一个差分数组 diff，每次操作时让 diff[L] += X，diff[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; vector<long 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 ≤ 2e5，d_i 可以很大，v_i 是正数。

这道题第一眼看上去像排序，也有点像 DP，但 N 到了 2e5，DP 的 O(N^2) 肯定是过不去的。正确的方向是贪心加优先队列。

3.2 排序 + 小根堆的推理过程

我把任务按截止日期 d_i 从小到大排序，然后维护一个小根堆 pq，堆里存的是“当前已经入选的任务奖励”。每处理一个任务时，先把它的奖励 push 进堆，然后立刻检查堆的大小是否超过了当前任务的截止日期 d_i。如果超过，说明在 d_i 天之前我们不可能完成这么多任务，必须放弃一个。放弃谁呢？很明显应该放弃奖励最小的那个，所以弹出堆顶。

这个做法的正确性可以这样理解：当我们按截止日期从小到大扫描时，堆里所有任务的截止日期都不超过当前 d_i。如果堆里任务数量大于 d_i，那么无论怎么安排，一定至少有一个任务无法在期限内完成，必须剔除一个。剔除哪个对后续影响最小？剔除奖励最小的那个。因为后续任务截止日期不会比当前更早，已经剔除的任务不可能重新变得“合法”，所以这个决策不会错。

我举个例子。假设有 5 个任务：

按截止日期排序后顺序为：任务3（d=1, v=70），任务2（d=2, v=60），任务5（d=2, v=80），任务1（d=3, v=50），任务4（d=4, v=40）。

扫描过程：

• 处理 d=1, v=70：堆 {70}，堆大小 1 不大于 1，保留。
• 处理 d=2, v=60：堆 {60, 70}，堆大小 2 不大于 2，保留。
• 处理 d=2, v=80：堆 {60, 70, 80}，堆大小 3 大于 2，弹出最小值 60，堆变成 {70, 80}。
• 处理 d=3, v=50：堆 {50, 70, 80}，堆大小 3 不大于 3，保留。
• 处理 d=4, v=40：堆 {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; vector<pair<int, 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_queue<long long, vector<long long>, greater<long 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 默认是大根堆，我需要小根堆，所以要写成greater<long long>。如果你用的是大根堆，弹出的会变成最大奖励，那就全错了。每道题里定义清楚堆的性质，比写完再调试高效得多。

我还想多说一句，这题也有一个倒序写法：从最后一天往回扫，维护一个大根堆，每天把新到期的任务入堆，然后弹出最大奖励。两种写法本质是同一个贪心思路，你掌握其中一种就够用了。

4. D题：网格路径计数的DP写法

4.1 状态设计与转移方程

D 题是经典的网格路径计数。给你一个 H 行 W 列的网格，每个格子要么是空地.，要么是墙壁#。你从左上角 (1,1) 出发，每次只能向右或者向下走一步，要求走到右下角 (H,W)，路上不能经过墙。输出不同路径数量对 1e9+7 取模的结果。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; vector<string> g(h); for (int i = 0; i < h; i++) { cin >> g[i]; } vector<vector<long long>> dp(h, vector<long 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 滚动数组优化与边界处理

二维数组在 H=W=2000 时占用 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; vector<string> g(h); for (int i = 0; i < h; i++) { cin >> g[i]; } vector<long 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 + 右.sum
• lmax = 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; vector<Node> 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 vector<long 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; vector<long 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 long，4 * N 个节点，在 2e5 的数据范围下完全够用。

写这道题的时候我踩过一个坑：合并查询结果时，忘记先判断左右两边是否都参与了。如果我的写法是递归处理跨区间，那么一定要确保左右两个子查询结果存在才 merge，否则会拿一个不存在的节点和真实节点合并，导致结果完全错误。上面代码里通过qr <= mid和ql > mid两个分支已经排除掉这种情况，但还是值得提醒你自己推一遍流程。

最后补充一点：这道题如果把单点修改改成区间加法，那么合并公式依然成立，但节点还要维护懒标记，复杂度会显著上升。先吃透当前的四字段版本，再考虑扩展会更稳。

6. 排坑记录与做题节奏复盘

6.1 最容易踩的坑速查表

把这场 A-E 里值得记录的坑整理成一张速查表，以后遇到同类题可以直接对照：

我自己当年刚开始写这类题时，最喜欢在“整体思路对但实现细节崩”的地方丢分。尤其是 E 题这种代码量比较大的题目，如果调试时只看样例不自己构造极端情况，很容易漏掉负数和跨区间的情况。建议每题至少自测三组数据：全部正数、全部负数、正负交替。

6.2 时间分配与做题策略

A 题和 B 题属于热身题，正常情况下应该控制在 20 分钟以内。C 题如果思路顺畅，30 分钟左右能写完。D 题是经典 DP，25 到 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 题的单点修改改成区间加法并引入懒标记。每扩展一步，你对基础算法的理解就会更扎实一层。希望这篇题解对你有用，也欢迎你在评论区聊聊你对哪道题印象最深。