企业官网建设流程全解析

昨晚AWC 0009 Beta结束之后，我把五道题的代码都重写了一遍，顺手把做题时踩到的坑记了下来。AtCoder Weekday Contest 0009 Beta这套题，从名字就能看出来是一个偏测试性质的比赛，题面风格很接近标准的ABC难度：A题送分，B题需要一点点哈希思维，C题如果反应不过来前缀和会卡一会儿，D题是典型的状压DP模板，E题则落在经典的线段树区间最大子段和上。整套题覆盖的知识点非常集中：取模边界、哈希计数、前缀和差值、状态压缩DP、区间信息合并，基本就是把平时刷题最常用的那几把刀都拿出来磨了一遍。

如果你是刚接触AtCoder的选手，建议先跟着A-C走一遍，重点体会“为什么这样想”；如果你已经在稳定AC A-C，那这篇的D和E部分值得逐行看，尤其是E题的查询合并逻辑，我自己在比赛里就栽了一次。下面我按比赛顺序逐题聊。

1. 先看整体：这五道题到底在考什么

1.1 难度与知识点分布

这场的A到E，难度曲线非常规整：前两题是纯粹的送分题，第三题开始需要一点思维转化，第四题进入算法模板，第五题才是真正考验代码综合能力的压轴。我整理了一张表，方便你对照自己卡在哪一层：

从这张表能看出，Beta赛的定位很清晰：不考偏门算法，不玩复杂数学推理，而是把最经典、最常考的知识点拿出来，看你能不能写得稳。所以这场比赛很适合用来检验自己的基础是否扎实。

1.2 我的做题节奏与时间分配

我自己的时间分配是：A题3分钟，B题10分钟，C题15分钟，D题30分钟（WA了一发），E题40分钟（第一次编译没过，第二次AC）。总共花了大约100分钟。

这个节奏其实暴露了一个问题：真正耗时的不是读题，而是那些“我以为很简单”的边界条件。A题快是因为公式一眼就能写出来，B题慢是因为我一开始差点写暴力，D和E则是标准的模板题但因为细节没处理干净而返工。如果你在这个节奏里遇到了和我相同卡壳的点，下面几节基本都能找到对应解释。

1.3 本场比赛的三个关键词

我复盘之后，给这五道题提炼了三个关键词。

第一个是“取模边界”。A题把星期几的1~7编号和取模运算搅在一起，等着你踩“周日输出0”的坑，还顺手埋了一个1e18的大整数。

第二个是“用历史信息换时间”。B题的哈希表和C题的前缀和，本质上在做同一件事：把“每次重新扫一遍”变成“查一下之前存好的表”。很多看似需要暴力的题，一旦你意识到可以存历史信息，复杂度立刻从O(n²)掉到O(n)。

第三个是“区间信息合并”。E题几乎就是为了这个主题而生的。单点修改加区间查询这种组合一旦出现，线段树就是标准答案，但如何合并左右儿子的信息，才是真正的考点。

2. A题：星期计算的取模陷阱

2.1 题意还原

题目输入两个数：D和X。D表示当前是星期几，用1到7表示，1代表周一，7代表周日。X表示距离下一场比赛还有多少天，X的上限给到了1e18。要求输出X天之后是星期几，同样用1到7表示。

这题看起来就是一行公式的事，但它埋了两个非常经典的坑：一个是星期编号从1开始而不是从0开始，另一个是X的范围大得离谱。

2.2 从模拟循环到O(1)公式的推导

最直觉的做法是for循环X次，每次让星期数加1，到7之后回到1。但看到X ≤ 1e18，这个方案立刻作废。哪怕一秒钟跑一亿次循环，也要跑三百多年才能读完整个X，这显然不是出题人的意图。

所以直接算模。星期数每过一天加1，本质上就是对7取模。但这里有一个很隐蔽的问题：编号是1到7而不是0到6。直接用(D + X) % 7，当结果落在星期天时算出来的是0，不是7。

解决办法是先把编号整体减1，取模之后再加回来。公式写成：

ans = (D + X - 1) % 7 + 1

验证一下：假设当前是周六，D = 6，X = 1，正确答案是周日也就是7。直接用(D + X) % 7算出来是0，而用上面的公式： (6 + 1 - 1) % 7 + 1 = 6 % 7 + 1 = 7，正确。再试一个跨越一周的例子：D = 1，X = 7，下周一，(1 + 7 - 1) % 7 + 1 = 7 % 7 + 1 = 1，正确。

我敢说这个“减一加一”是很多人写日期类题目时翻车的点。它错得悄无声息，如果样例刚好没覆盖周日，你根本发现不了。这也是为什么AtCoder的A题经常给人“样例过、提交WA”的体验。

2.3 参考实现

#include <bits/stdc++.h> using namespace std; int main() { ios::sync_with_stdio(false); cin.tie(nullptr); long long D, X; cin >> D >> X; long long ans = (D + X - 1) % 7 + 1; cout << ans << '\n'; return 0; }

代码短到有点不像一场算法竞赛的第一题，但注意这里用的是long long而不是int。X上限1e18，D + X虽然后果不大，但如果你在比赛中习惯性写int，WA就是一瞬间的事。

2.4 两个容易忽略的点

第一是long long。AtCoder的A题特别喜欢在那种“一秒能算完”的公式里埋伏数据范围，让你以为很简单，结果因为类型不够宽直接吃罚时。我之后学乖了：读入任何变量，先看一眼题目的数据范围约束，再决定用int还是long long，这个习惯能帮你省下大量无意义的WA。

第二是输出别用endl。endl会强制刷新输出缓冲区，在输出量大的题目里会明显拖慢速度。用'\n'就够了，这是一个很小的习惯，但对竞技编程来说很重要。

3. B题：不要见着两数之和就写两层for

3.1 题意还原

这题给定一个长度为n的整数数组a，以及一个目标值K。要求统计有多少个下标对(i, j)满足两个条件：i < j，并且a[i] + a[j] = K。n给到了2e5，a[i]和K的范围都在1e9左右。

“两数之和”这四个字一出来，很多人的第一反应是写两层循环，但这题这么做必死。

3.2 双重循环为什么在这里是陷阱

n = 2e5时，两层for循环的比较次数大约是4e10。C++一秒钟大概能跑1e8到1e9次基础操作，也就是说暴力要跑几十秒到几分钟，这在线性递推题和哈希表题面前完全不可接受。

而且这题的考察点不是“能不能写对暴力”，而是“能不能想到用空间换时间”。你看题目给定的数组是无序的，又不能排序后二分（排序会破坏下标关系），所以唯一合理的思路就是一边扫描数组，一边用东西记录已经看过的数。

3.3 哈希把查找变成O(1)与“先查后插”的顺序

对于当前读到的数x，能和它配对的另一个数一定是K - x。我们不需要关心未来会出现什么，只需要知道在已经读过的所有数字里，K - x出现了多少次。

于是算法很自然：用一个哈希表cnt记录每个数出现的次数，每读到一个x，先把cnt[K - x]累加到答案，再把cnt[x]加1。

这里有一个特别容易写错的细节：为什么必须先查后插？如果先插再查，当K = 2x时，当前这个x会被自己和自己的配对算进去一次。举个例子，数组里只有一个数5，K = 10，正确答案应该是0，但先插再查会得到1。更严重的是，如果后面还有一个5，先插再查会把(i, j)和(j, i)这种重复配对都算进去，答案直接翻倍。先查后插的逻辑保证了一个数只和它左边已经出现过的数配对，天然满足i < j，不会重复。

3.4 参考实现

#include <bits/stdc++.h> using namespace std; int main() { ios::sync_with_stdio(false); cin.tie(nullptr); int n; long long K; cin >> n >> K; unordered_map<long long, long long> cnt; long long ans = 0; for (int i = 0; i < n; i++) { long long x; cin >> x; ans += cnt[K - x]; cnt[x]++; } cout << ans << '\n'; return 0; }

复杂度是O(n)时间、O(n)空间。注意这里cnt的键值都用long long，因为K - x完全可能是负数，而且K本身给到了1e9，加上a[i]之后运算结果可能超过int上限，用long long是最稳妥的选择。

3.5 一个关于unordered_map被卡的实战经验

大多数情况下unordered_map能轻松AC，但我印象很深的是在某次比赛里见过有人用unordered_map被精心构造的数据卡到超时。原因是C++标准库的unordered_map默认哈希函数在特定整数序列上会产生大量冲突，导致查找退化到接近O(n)。

AtCoder的一般比赛不太会这么狠，但如果想保险，有两个替代方案：一是直接用std::map，O(log n)的复杂度在2e5数据量下完全够用；二是给unordered_map挂一个自定义的splitmix64哈希函数。我个人的习惯是，只有在卡常严重的题目里才用第二种方案，平时用map反而更省心，毕竟wa比tle更容易让人烦躁。

4. C题：最长平衡子串，前缀和的经典变式

4.1 题意还原

给定一个长度为n的01字符串s，n不超过2e5。要求找出最长的连续子串，使得子串中0和1的数量相等。如果不存在这样的子串，输出0。

这题直接的想法是枚举所有子串，统计0和1的数量，但那是O(n²)的复杂度，2e5的数据量根本跑不动。所以需要换一个角度。

4.2 关键一步：把0改写成-1

这个转化我觉得是整场比赛里最漂亮的一步。把0记成-1，1记成+1，那么一个区间里0和1数量相等，就恰好等价于这个区间的累加和为0。两个变量的比较问题，被压缩成一个标量的相等问题，这比分别统计0的数量和1的数量要优雅得多。

用生活化的话说，就像记账时把支出记为负数、收入记为正数，想知道一段时间是否收支平衡，只要看余额是不是0就行。不用分别合计收入和支出，这个“余额为0”的判断就是我们的目标。

有了这个转化，定义prefix[i]表示前i个字符的累加和。那么区间(l, r]的累加和为0，等价于prefix[l] == prefix[r]。题目于是变成了：在所有满足prefix[i] == prefix[j]的下标对中，求最大的j - i。

4.3 为什么哈希表里存的是“最早出现的下标”

既然要最大距离，那么对于同一个前缀和值，我们只关心它第一次出现的位置。后续再遇到相同值时，拿当前下标减去最早出现的下标，一定比减去一个更晚的下标得到的长度更长。这个点特别容易想反，有些新手会把最新位置不断覆盖进哈希表，导致每个值只能配出长度为1的区间，答案当然不对。

另外千万别忘了把prefix[0] = 0、位置0放进哈希表。比如s = "10"，前缀和序列是0, 1, 0，第一个整段[1,2]对应的就是prefix[2] == prefix[0] == 0。如果不初始化prefix[0]，从字符串开头出发的合法子串会被全部漏掉。

4.4 参考实现

#include <bits/stdc++.h> using namespace std; int main() { ios::sync_with_stdio(false); cin.tie(nullptr); int n; string s; cin >> n >> s; unordered_map<int, int> first; first[0] = 0; int pref = 0; int ans = 0; for (int i = 1; i <= n; i++) { if (s[i - 1] == '1') pref++; else pref--; if (first.count(pref)) { ans = max(ans, i - first[pref]); } else { first[pref] = i; } } cout << ans << '\n'; return 0; }

复杂度O(n)，已经很优了。边界情况也简单：如果字符串全是0或者全是1，那么所有前缀和互不相同，ans始终是0，输出0符合题意。

4.5 同一思路能推广到什么题目

这套“前缀和加哈希表”的模板，在LeetCode上有一大批亲戚题：和为K的子数组个数、和至少为K的最短子数组、以及“最长子数组和为0”的加强版。处理一般的整数数组时，只需要把前缀和改成按a[i]直接累加，把s[i - 1] == '1'的判断改成a[i]即可，核心逻辑完全不动。所以C题非常值得当模板题收藏。

5. D题：哈密顿回路的最短路，状压DP标准模型

5.1 题意还原

这题给了一个n乘n的距离矩阵，n不超过16。dist[i][j]表示从城市i到城市j的距离，可能很大；如果dist[i][j] = -1，表示没有办法直接走这条路。要求从城市0出发，恰好经过每个城市一次，最后回到城市0，输出整个回路的最短距离。如果不存在这样的回路，输出-1。

这题本质上是一个带权完全图上找最短哈密顿回路的问题，但不一定完全连通，因为有-1的限制。

5.2 为什么DFS剪枝也扛不住n=16

最简单的想法是DFS枚举全排列。16的阶乘大约是2.09e13，即使剪枝能删掉大部分状态，剩余搜索树仍然是指数级的规模。n = 12的时候DFS或许还能碰碰运气，n = 16就必须上状态压缩DP了。

状态压缩的核心思想是：“已经访问过哪些城市”本身就是一个完整且精确的状态。我们用二进制mask来表示它，每一位代表一座城市是否已经访问过，这样就能把重复的搜索子树合并掉。n = 16意味着有2^16 = 65536种不同的访问集合，这个数量完全可以直接枚举。

5.3 状态设计

定义dp[mask][i]表示：当前已经访问过的城市集合为mask，并且当前停留在城市i时，已经走过的最短路径长度。mask的第k位为1表示城市k已经被访问过。因为起点固定为城市0，所以初始状态是dp[1][0] = 0，表示集合里只有0号城市，当前在0号城市。

为什么需要二维而不是只存mask？因为下一步要去哪个城市，取决于当前停在哪座城市。只知道mask不知道当前位置的话，转移无从谈起。所以在状压DP里，“当前在哪”这维信息几乎总是少不了的。

5.4 状态转移与循环顺序

从某个状态dp[mask][i]出发，先要求i确实在mask中，然后枚举一个不在mask中的城市j，如果dist[i][j]不是-1，就可以尝试用dp[mask][i] + dist[i][j]去更新dp[mask | (1 << j)][j]。

循环顺序上，外层按mask从小到大枚举即可。理由很直观：每次转移都会让mask至少多一个二进制1位，所以新状态对应的mask数值一定大于旧状态。从小到大枚举正好让所有前置状态在轮到它们时都已经被算好，这也是状压DP天然的无后效性。如果你以后见过有的题需要按集合大小分层，那是因为转移可能发生在mask大小相同的状态之间，这道题不会出现那种情况。

最后，当mask变成全1的full时，枚举最后停留的城市i，用dp[full][i] + dist[i][0]更新答案。如果dist[i][0]不可达就跳过。

5.5 参考实现

#include <bits/stdc++.h> using namespace std; int main() { ios::sync_with_stdio(false); cin.tie(nullptr); int n; cin >> n; vector<vector<int>> dist(n, vector<int>(n)); for (int i = 0; i < n; i++) { for (int j = 0; j < n; j++) { cin >> dist[i][j]; } } if (n == 1) { cout << 0 << '\n'; return 0; } const int INF = 1e9; int full = (1 << n) - 1; vector<vector<int>> dp(1 << n, vector<int>(n, INF)); dp[1][0] = 0; for (int mask = 1; mask <= full; mask++) { if (!(mask & 1)) continue; for (int i = 0; i < n; i++) { if (!(mask & (1 << i))) continue; if (dp[mask][i] == INF) continue; for (int j = 0; j < n; j++) { if (mask & (1 << j)) continue; if (dist[i][j] == -1) continue; int nmask = mask | (1 << j); dp[nmask][j] = min(dp[nmask][j], dp[mask][i] + dist[i][j]); } } } int ans = INF; for (int i = 0; i < n; i++) { if (dist[i][0] == -1) continue; ans = min(ans, dp[full][i] + dist[i][0]); } cout << (ans == INF ? -1 : ans) << '\n'; return 0; }

很多选手关心这个DP到底算多少遍，我实际算了一下：n = 16时，把所有的mask、最后停留点、下一个点的枚举加起来，完整转移次数大约只有两百万次。对比16!，这个加速完全就是状态压缩的威力。

5.6 我在这一题上交WA的两个真实坑

第一次WA出在最后一步。我只写了ans = min(ans, dp[full][i] + dist[i][0])，没有判断dist[i][0]是不是-1。当i回不到0时，-1会参与加法，得到一个比INF小得多但看起来完全正常的数。因为INF取1e9时，INF + (-1)约等于999999999，然后被min当成“最优答案”取走了。

这个Bug非常恶心，因为结果看起来像是合法距离，你很难怀疑它。后来我养成习惯：凡是涉及-1代表不可达的题目，在做加法之前一定先检查能不能走这条路。第二个坑是n = 1的情况，只有一座城市时，从0出发经过它再回到0，路程就是0。没加这个特判，程序可能会去访问dp[0][...]或者直接越界。Beta赛里这种边界题很常见，考的就是你读题时有没有注意到n的下界。

6. E题：区间最大子段和的线段树解法，重点在四个信息

6.1 题意还原

给定一个长度为n的整数数组a，n和操作次数q都不超过2e5。a[i]可以是正数也可以是负数。操作有两种：第一种操作是单点赋值，把某个位置的数改成v；第二种操作是查询区间[l, r]内最大子段和，这里的子段必须非空。

单点修改加区间查询的组合，几乎就是线段树的出场信号。但这题的关键不在线段树本身，而在于节点里到底要维护什么信息。

6.2 为什么不能只存一个“区间最大值”

线段树节点如果只存一个最大值mx，合并左右儿子时只能取max(L.mx, R.mx)。但最大子段和还有可能横跨两个儿子：从左儿子的右半部分一直延续到右儿子的左半部分。光有mx，这个跨中点的子段根本算不出来。

所以需要扩充分信息。任何一个区间都可以用四个值描述：

• sum：区间总和
• lmx：必须包含区间左端点的最大前缀和
• rmx：必须包含区间右端点的最大后缀和
• mx：区间最大非空子段和

记住lmx和rmx的理由很直观：跨中点的子段起点一定在左区间，终点一定在右区间，所以它由左区间的某个后缀和右区间的某个前缀拼接而成。没有这两个信息，跨中点的答案就是空中楼阁。

6.3 合并公式的推导

假设左儿子是L，右儿子是R，把两者合并成父节点P，那么P的四个值分别这样算：

• P.sum = L.sum + R.sum
• P.lmx = max(L.lmx, L.sum + R.lmx)
• P.rmx = max(R.rmx, R.sum + L.rmx)
• P.mx = max(L.mx, R.mx, L.rmx + R.lmx)

lmx的两种可能：要么最大前缀完全落在左儿子里，也就是L.lmx；要么从L的最左边一路延伸到R的某个位置，这种情况下前半段是整个L，后半段是R的lmx，所以是L.sum + R.lmx。rmx完全对称。mx的三种可能：整个子段完全在左儿子、完全在右儿子、跨过中点。跨中点就是L.rmx + R.lmx。

用一个具体数组验证这个公式：[−2, 1]和[3, 4]合并。L区间[−2, 1]的mx是1，R区间[3, 4]的mx是7，但L.rmx + R.lmx = 1 + 7 = 8，对应子段[1, 3, 4]，这才是真正的最大子段和。如果只存mx，我们只会得到7，丢掉正确答案。这个例子能很清楚地说明为什么四元组缺一不可。

6.4 查询操作里最容易出错的合并逻辑

标准线段树的查询函数，返回值应该是Node而不是一个整数。为什么非要这样？因为查询区间可能横跨多个线段树节点，这些节点之间也要按相同的合并公式组合。如果你写成返回int、两边直接取max，那等于完全无视跨中情况，答案必错。

查询里的边界分支条件要和build、update保持一致。我自己常用的写法是这样的：

Node query(int p, int l, int r, int ql, int qr) { if (ql <= l && r <= qr) return seg[p]; int mid = (l + r) >> 1; if (qr <= mid) { return query(p << 1, l, mid, ql, qr); } if (ql > mid) { return query(p << 1 | 1, mid + 1, r, ql, qr); } return combine( query(p << 1, l, mid, ql, qr), query(p << 1 | 1, mid + 1, r, ql, qr) ); }

其中qr <= mid和ql > mid两个直退分支必须写对。漏掉其中一个，或者把等于号写反，都会让递归多走一路，并在合并时把不该包含进答案的区间也合进去，最终得到错误结果。

6.5 参考实现

#include <bits/stdc++.h> using namespace std; struct Node { long long sum; long long lmx; long long rmx; long long mx; }; int n, q; vector<long long> a; vector<Node> seg; Node combine(const Node& L, const Node& R) { Node res; res.sum = L.sum + R.sum; res.lmx = max(L.lmx, L.sum + R.lmx); res.rmx = max(R.rmx, R.sum + L.rmx); res.mx = max({L.mx, R.mx, L.rmx + R.lmx}); return res; } void build(int p, int l, int r) { if (l == r) { seg[p] = {a[l], a[l], a[l], a[l]}; return; } int mid = (l + r) >> 1; build(p << 1, l, mid); build(p << 1 | 1, mid + 1, r); seg[p] = combine(seg[p << 1], seg[p << 1 | 1]); } void update(int p, int l, int r, int pos, long long v) { if (l == r) { seg[p] = {v, v, v, v}; return; } int mid = (l + r) >> 1; if (pos <= mid) { update(p << 1, l, mid, pos, v); } else { update(p << 1 | 1, mid + 1, r, pos, v); } seg[p] = combine(seg[p << 1], seg[p << 1 | 1]); } Node query(int p, int l, int r, int ql, int qr) { if (ql <= l && r <= qr) { return seg[p]; } int mid = (l + r) >> 1; if (qr <= mid) { return query(p << 1, l, mid, ql, qr); } if (ql > mid) { return query(p << 1 | 1, mid + 1, r, ql, qr); } return combine( query(p << 1, l, mid, ql, qr), query(p << 1 | 1, mid + 1, r, ql, qr) ); } int main() { ios::sync_with_stdio(false); cin.tie(nullptr); cin >> n >> q; a.resize(n + 1); seg.resize(4 * (n + 1)); for (int i = 1; i <= n; i++) { cin >> a[i]; } build(1, 1, n); while (q--) { int op; cin >> op; if (op == 1) { int x; long long v; cin >> x >> v; update(1, 1, n, x, v); } else { int l, r; cin >> l >> r; Node ans = query(1, 1, n, l, r); cout << ans.mx << '\n'; } } return 0; }

复杂度是每次操作O(log n)，整体O((n + q) log n)。注意Node里的四个值全部用long long，因为a[i]可以到1e9，多个负数相加、再跨区间合并之后，答案很容易超过int范围。这个问题我在自己第一次写这类题时也吃过亏。

6.6 一个关于空子段的延伸

这道题要求最大子段必须非空，所以即使数组全是负数，答案也是最大的那个负数，而不是0。LeetCode 53那类允许空子段的题目是另一个版本，做法也不一样：允许空子段时，lmx和rmx可以为0，mx至少是0，sum仍然照常维护。这个改动可以作为课后练习，把上面代码改上几行，看它能否正确处理全负数的情况。能把这个改动想明白，说明你对lmx和rmx的语义已经是真理解而不是背板子了。

7. 赛后复盘：我建议下一场AWC这样准备

这场Beta赛打完，我最大的感受是：题本身不难，但每个坑都藏在“理所当然”里。A题的星期模7、B题的哈希顺序、C题漏掉的prefix[0]、D题的-1回程、E题的查询合并，五个看似独立的考点，其实指向同一个能力——在会写代码之外，能不能稳准地处理边界条件。

对新手来说，A到C是非常好的“想清楚再写”训练。建议在草稿纸上先把公式和边界列出来再敲代码，不要急着提交。对想冲击D和E的朋友，状压DP和线段树是AtCoder中段题的常客，模板要练到能在一分钟内默写出来的程度，尤其是线段树的Node合并函数，那道query的分支判断值得反复默写几遍。

最后分享一个我坚持了很久的小习惯：每场周赛结束后，不管AC没AC，都把每道题的重写版本存到本地，并在代码注释里写一句这题最容易错的地方。坚持十几场下来，你会发现自己看题的第一反应明显变快，因为很多坑你已经提前踩过了。下一场AWC正赛，我准备拿这套复盘经验去试试，尤其是这次WA过的两个点，我不允许自己再交同样的学费。