企业官网建设流程全解析

这场的 ABC437 打完，我直到补完最后一题才算彻底舒坦。说实话这场的难度阶梯做得挺友好：A、B 两题基本就是热身，C 题开始进入状态，D 题是典型的换思路题，E、F 则把常见的两种高阶技巧放进了比较干净的包装里。作为长期在周赛里挣扎的算法爱好者，我最喜欢这种“每题都能学到一点、又不会全程被按在地上摩擦”的场次。

本文就按我的复盘顺序，把每题的思考过程、实现细节、以及踩过的坑完整记录下来。里面给出的代码都以 C++ 17 为准，复杂度也都算了，希望能给准备参加同类比赛、或者正在刷题找思路的读者一点实际参考。

1. 这场的整体观察与复盘思路

1.1 难度分布与算法概览

先把六道题在脑子里的定位捋一遍。A 题基本是送分题，考的是最基本的条件判断；B 题是一个经典的枚举计数，暴力就能过；C 题换成了网格图连通块，如果平时写过 BFS 或者并查集，这题就是模板；D 题开始需要一点思维转化，虽然表面上很像贪心，但正确解法其实是用前后缀拆开考虑；E 题是一个图上的最短路径问题，核心在于拆点；F 题则是传统的数据结构题，需要手写线段树维护区间最大子段和。

这场的算法覆盖其实挺典型的：枚举、图遍历、动态规划、最短路径、线段树。唯一没怎么考的是数论和组合数学，对排序、二分这类基础技巧的考察也比较少。我觉得这种构成恰好适合用来查缺补漏：如果你 C、D 两道题做得不顺，大概率是图遍历和前后缀拆分的基本功还差一点；如果卡在 E，那拆点建图的套路还得再练；F 题就是纯考线段树的熟练度，平时模板不够熟就会写得很慢。

1.2 复盘时的三个切入点

很多同学打完比赛只看自己过了几题，其实复盘比比赛本身更重要。我会从三个角度去拆每一题：第一，这题的官方解法或者更优解法是什么，我在考场上为什么没想到；第二，我的代码边界情况处理够不够稳，比如n=1或者全负数时会不会直接爆炸；第三，把这道题抽象成哪种模型，下次遇到类似结构能不能一眼识别出来。

这篇文章也会沿着这三个切入点走。每一题不会只给结论和代码，还会尽量还原我当时是怎么想到这个思路的，以及中间踩了哪些坑。

2. 快速解决 A、B 两题

2.1 A 题：奇偶判断，简单但要写得稳

A 题题意是给定两个正整数 A 和 B，判断 A 加 B 之后的结果是否为偶数，是偶数输出Yes，否则输出No。这题本身没有思维难度，但恰恰是容易在细节上出问题的地方。数据范围虽然不大，我仍然建议直接用long long读入，而不是int。原因很简单：养成用大范围整数读入的习惯，可以避免在后续题中因为漏看数据范围而白白吃一次WA。

#include <bits/stdc++.h> using namespace std; int main() { ios::sync_with_stdio(false); cin.tie(nullptr); long long a, b; cin >> a >> b; if ((a + b) % 2 == 0) cout << "Yes\n"; else cout << "No\n"; return 0; }

这里有一个小细节：ios::sync_with_stdio(false)和cin.tie(nullptr)两行是 C++ 选手的“起手式”。很多新手在提交 C++ 代码时不写这两行，一旦数据量变大，cin就会慢得离谱，导致同样的代码在本地跑得飞快、提交后却超时。另外输出部分不要忘记换行，Yes和No的大小写也建议直接复制题面，避免手打出错。A 题虽然答案简单，但过程必须规范。

2.2 B 题：三角形计数，暴力枚举也有讲究

B 题给定 N 个互不相同的点坐标，问从中任选三个点能组成的三角形有多少个。N 的数据范围是 200，所以最简单的做法就是三重循环枚举三元组，然后用叉积判断三点是否共线。三点共线的条件是向量叉积等于 0，也就是说：

(xj - xi) * (yk - yi) == (yj - yi) * (xk - xi)

如果满足这个条件，三个点落在同一条直线上，不能构成三角形；否则一定可以构成三角形。

#include <bits/stdc++.h> using namespace std; int main() { ios::sync_with_stdio(false); cin.tie(nullptr); int n; cin >> n; vector<int> x(n), y(n); for (int i = 0; i < n; i++) { cin >> x[i] >> y[i]; } int ans = 0; for (int i = 0; i < n; i++) { for (int j = i + 1; j < n; j++) { for (int k = j + 1; k < n; k++) { if ((x[j] - x[i]) * (y[k] - y[i]) != (y[j] - y[i]) * (x[k] - x[i])) { ans++; } } } } cout << ans << '\n'; return 0; }

复杂度是 O(N^3)，200 个点的最大组合数是 C(200,3)，也就是约 131 万个组合，这个计算量在 C++ 里连一毫秒都用不满，完全放心跑。这个题想考察的就是最基础的枚举能力，以及叉积判断共线的技巧。没有学过叉积的同学可能第一反应是用斜率判断，处理垂直情况时会很痛苦，所以叉积一定要作为基本功掌握。

2.3 简单题也容易踩的坑

A、B 两题虽然不难，但我在自己带新人时见过太多翻车现场。第一是忘记用long long，坐标运算的中间结果可能超出int范围；第二是叉积判断写成浮点比较，由于浮点精度问题可能在边界处出错；第三是循环边界写错，三重循环写成i <= n或者j <= n，导致访问越界。还有一个心态层面的问题，很多同学看到 A 题太简单就随手提交，结果因为少打一个换行或者输出大小写不对而吃WA。越是简单题，越要稳住，先自己把样例跑过，再提交不迟。

3. C 题：网格连通块的计数与搜索细节

3.1 把题目翻译成连通块模型

C 题给了一个 H 行 W 列的网格，每个格子上要么是字符.，要么是#。.表示可以走的空地，#表示障碍物，要求统计空地区域被分成了几个连通块。所谓连通，就是上下左右四个方向相邻的.格子属于同一个区域。

这个模型非常经典。只要对每一个没有被访问过的.格子进行搜索，把能走到的一整片都标记成访问过，然后计数加一，最后输出计数结果即可。这里我选择用 BFS 而不是 DFS，因为当 H 和 W 都接近 1000 时，网格有 100 万个格子，递归 DFS 可能会导致栈溢出。在实际比赛中，能用栈模拟递归、或者直接用队列的 BFS，往往是更稳的选择。

3.2 BFS 实现与细节处理

BFS 的核心思路是用一个队列存放待扩展的格子，每次从队首取出格子，检查上下左右四个方向，如果是没有访问过的.就入队并标记访问。

#include <bits/stdc++.h> using namespace std; int main() { ios::sync_with_stdio(false); cin.tie(nullptr); int h, w; cin >> h >> w; vector<string> grid(h); for (int i = 0; i < h; i++) { cin >> grid[i]; } vector<vector<int>> vis(h, vector<int>(w, 0)); int dx[] = {1, -1, 0, 0}; int dy[] = {0, 0, 1, -1}; int ans = 0; for (int i = 0; i < h; i++) { for (int j = 0; j < w; j++) { if (grid[i][j] == '.' && !vis[i][j]) { ans++; queue<pair<int, int>> q; q.push({i, j}); vis[i][j] = 1; while (!q.empty()) { auto [x, y] = q.front(); q.pop(); for (int k = 0; k < 4; k++) { int nx = x + dx[k]; int ny = y + dy[k]; if (nx < 0 || ny < 0 || nx >= h || ny >= w) continue; if (grid[nx][ny] == '#') continue; if (vis[nx][ny]) continue; vis[nx][ny] = 1; q.push({nx, ny}); } } } } } cout << ans << '\n'; return 0; }

这里需要重点检查的两件事，一是越界判断，二是在入队前就要标记访问。很多人习惯先入队再标记，结果同一个格子被多次入队，不仅浪费时间，甚至可能死循环。类似的错误我在新手代码里见过太多次，必须养成“入队即标记”的习惯。

3.3 并查集和 BFS 的选择

连通块问题不止 BFS 一种写法，也可以用并查集。把网格中的每个点映射成一个编号，然后逐行逐列合并相邻的.格子，最后统计有多少个集合即可。并查集写起来比 BFS 稍长，但好处是可以支持后续的“动态加边”操作。就本题而言，BFS 和并查集都能过，看个人模板熟悉程度。

如果你只是为了比赛顺手，建议两种写法都准备一份。C 题现在越来越喜欢把连通分量藏在一个和其他算法的混合模型里，到时候你能快速判断出“哦，这里是并查集能解决的”，就会比现场重新想省下很多时间。

4. D 题：最多删除一个元素后的最大连续子段和

4.1 为什么不能靠贪心直接删最小负数

D 题的题面是：给一个长度为 N 的整数数组，元素可能为负数。你可以选择删除至多一个元素，也可以不删除，然后求数组中非空连续子段的最大和。

第一眼看到“删除至多一个元素”，很多人会想：我直接找到数组中最小的负数，把它删掉不就行了？这个想法在部分样例上能行，但很快就露出破绽。比如数组是[-5, 100, -1, 100, -5]，最小负数是-5，但你删任意一个-5都不能把两个100连起来。真正应该删除的是中间的-1，这样左右两段正数才能拼成200。这说明问题不能靠全局贪心解决，而是要考虑“删除某个位置后，以这个位置为中心，左右两侧最大能接出多少”。

这个思路最终会把问题拆成两个部分：每个位置左侧的“最大后缀”和右侧的“最大前缀”，然后枚举删除点拼接两侧。

4.2 前后缀数组法

定义pre[i]表示数组前 i 个元素中，以第 i 个元素结尾的最大连续子段和。这个转移就是经典的最大子段和：

pre[i] = max(a[i], pre[i-1] + a[i])

定义suf[i]表示从第 i 个元素开始到数组结尾，以第 i 个元素开头的最大连续子段和：

suf[i] = max(a[i], a[i] + suf[i+1])

如果不删除任何元素，答案是所有pre[i]中的最大值。如果删除第 i 个元素，那么可以取左侧以i-1结尾的最大子段、右侧以i+1开头的最大子段，再把两段拼起来。左侧和右侧都可以选择不取，因为取负数只会让结果更差。因此删除第 i 个元素后，可能的最大值为：

max(0, pre[i-1]) + max(0, suf[i+1])

这里有一个必须注意的地方：当左右两侧都为 0 时，拼接结果是空段，不合法。所以更新答案时不能直接把 0 写入答案，否则全负数数组会出问题。我用的方式是用原数组不删除的最大值兜底，并且只在左 + 右 > 0时更新答案。

#include <bits/stdc++.h> using namespace std; int main() { ios::sync_with_stdio(false); cin.tie(nullptr); int n; cin >> n; vector<long long> a(n + 2); for (int i = 1; i <= n; i++) cin >> a[i]; vector<long long> pre(n + 2, LLONG_MIN / 4); vector<long long> suf(n + 2, LLONG_MIN / 4); pre[1] = a[1]; for (int i = 2; i <= n; i++) { pre[i] = max(a[i], pre[i - 1] + a[i]); } suf[n] = a[n]; for (int i = n - 1; i >= 1; i--) { suf[i] = max(a[i], a[i] + suf[i + 1]); } long long ans = LLONG_MIN / 4; // 不删除的情况 for (int i = 1; i <= n; i++) { ans = max(ans, pre[i]); } // 枚举删除第 i 个元素 for (int i = 1; i <= n; i++) { long long left = (i > 1 ? max(0LL, pre[i - 1]) : 0LL); long long right = (i < n ? max(0LL, suf[i + 1]) : 0LL); if (left + right > 0) { ans = max(ans, left + right); } } if (n == 1) ans = a[1]; cout << ans << '\n'; return 0; }

如果完全不允许空数组，那么n == 1时答案就是唯一的那个元素。这段代码在实现上还有一个小细节：LLONG_MIN / 4不是随便写的。直接把LLONG_MIN赋值给pre[i-1]然后参与加法运算，存在溢出风险。除一个比 1 大的数，可以让“负无穷”远离边界，避免奇怪的溢出问题。这个技巧我在很多题解里都会用，比直接写-1e18更不用记数据范围。

4.3 一些边界情况

考虑数组全为负数的情况，比如[-5, -1, -3]。不删除时最大子段和是-1。删除任意元素后，两边取 0 拼接可能会得到 0，但这是非法空段，不能计入答案。实测上面代码输出是-1，符合预期。

再看数组[100, -1, 100]。不删除时最大和是199，删除中间的-1后，左侧取100，右侧取100，拼接得到200，代码能正确输出 200。这个样例就直观体现了“删除负数的意义在于把两个正段连通起来”。

5. E 题：颜色交替最短路径与拆点法

5.1 为什么不能直接跑普通 BFS

E 题给了一个 N 个点 M 条边的无向图，每条边有一个颜色，颜色只有 0 或 1。路径要求从点 1 出发，到点 N 结束，并且路径上相邻两条边的颜色不能相同。问满足条件的最短路径长度是多少，不存在就输出 -1。

如果直接拿普通 BFS 去跑，会遇到一个很麻烦的问题：同一个点可能通过不同颜色的边到达，而下一步能走的边取决于“上一条边是什么颜色”。也就是说，光记住“当前在哪个点”是不够的，还要额外记住“当前是从什么颜色的边走过来”的。如果你在普通 BFS 里只用一个dist[u]，就会丢失信息，导致状态转移错误。

这种问题的标准解法叫拆点，也叫分层图。把一个点拆成两个状态：(u, 0)表示经过颜色 0 的边到达点 u，(u, 1)表示经过颜色 1 的边到达点 u。这样原图就变成了两倍点数的图，每条有颜色的边会在分层图里建立一条到对应颜色状态的边。起点因为是特殊状态，没有上一条边，所以(1,0)和(1,1)都可以作为起点，距离都是 0。

5.2 BFS 实现与复杂度证明

有了拆点思路后，代码并不复杂。每条边的颜色 c，从当前状态(u, last)出发，如果last == c，说明颜色没有交替，这条边不能走；如果last != c，就可以走到(v, c)，并更新dist[v][c]。

#include <bits/stdc++.h> using namespace std; int main() { ios::sync_with_stdio(false); cin.tie(nullptr); int n, m; cin >> n >> m; vector<vector<pair<int, int>>> g(n + 1); for (int i = 0; i < m; i++) { int u, v, c; cin >> u >> v >> c; g[u].push_back({v, c}); g[v].push_back({u, c}); } const int INF = 1e9; vector<vector<int>> dist(2, vector<int>(n + 1, INF)); queue<pair<int, int>> q; dist[0][1] = 0; dist[1][1] = 0; q.push({1, 0}); q.push({1, 1}); while (!q.empty()) { auto [u, last] = q.front(); q.pop(); int d = dist[last][u]; for (auto [v, c] : g[u]) { if (c == last) continue; if (dist[c][v] > d + 1) { dist[c][v] = d + 1; q.push({v, c}); } } } int ans = min(dist[0][n], dist[1][n]); if (ans == INF) cout << -1 << '\n'; else cout << ans << '\n'; return 0; }

复杂度方面，拆点后共有 2N 个状态，边数仍然是 M 条。每条边在 BFS 过程中最多从两个状态分别扫描一次，所以总复杂度是 O(N + M)，这个复杂度对 N、M 都是 2e5 的数据范围完全够用。

5.3 这个套路能扩展到哪

拆点法不仅仅是用来处理颜色交替的限制，凡是题目里出现“状态除了当前位置外，还和某个附加属性有关”的模型，都可以往拆点上想。比如有些图论题会要求“花费若干代价后改变模式”“走过一条特殊边后解锁另一类边”等等，本质上都可以通过增加状态维度来把非标准的图问题转化回普通的 BFS 或最短路。

扩展一步：如果边权不是 1，而是 0 或 1，那么 BFS 就要换成 0-1 BFS 或者 Dijkstra。这个方向也很常见，比如“从点 1 到点 N，普通边代价为 1，特殊边代价为 0”，那就是典型的 0-1 BFS。拆点本身不改变边权，只改变图的拓扑结构，所以只要基础的最短路算法熟练，E 题完全可以拿下。

6. F 题：线段树维护区间最大连续子段和

6.1 四个信息的设计过程

F 题要求维护一个长度为 N 的数组，支持单点修改和查询任意区间内“最大连续子段和”，并且子段必须非空。数据范围在 2e5 级别，操作数也在 2e5 级别，所以必须用线段树。

线段树的每个节点需要维护四个信息：

• sum：区间总和
• lmax：区间内从最左边开始的最大连续子段和，即最大前缀和
• rmax：区间内以最右边结束的最大连续子段和，即最大后缀和
• ans：区间内任意位置的最大连续子段和

合并左右两个儿子时，公式是固定的。假设左儿子是 L，右儿子是 R，那么：

sum = L.sum + R.sum lmax = max(L.lmax, L.sum + R.lmax) rmax = max(R.rmax, R.sum + L.rmax) ans = max(L.ans, R.ans, L.rmax + R.lmax)

这四个公式理解起来不难。lmax要么完全来自左儿子的前缀，要么从左边开始、把左儿子全取之后，再接到右儿子的前缀上。rmax同理。而ans有三种可能：完全在左边、完全在右边、或者跨过中点由左儿子的后缀和右儿子的前缀拼起来。

为什么必须设这四个值？因为“跨左右区间”的答案需要同时知道左儿子后缀和右儿子前缀，如果只维护一个全局最大值，合并时就会丢失信息。这也是很多线段树进阶题目的通用设计思路：不是只维护答案，而是维护能合并出答案的若干辅助信息。

6.2 查询的关键：顺序不能乱

F 题真正容易写错的地方在查询。单点修改很简单，麻烦的是区间查询时要把多个节点合并起来。因为查询区间会递归跨越两个子区间，所以函数返回值不能只写一个数，最好是返回Node结构体。查询时遵循一个顺序：先查左子树的结果，再查右子树的结果，然后按左结果 + 右结果的顺序合并。

#include <bits/stdc++.h> using namespace std; struct Node { long long sum, lmax, rmax, ans; Node() : sum(0), lmax(0), rmax(0), ans(0) {} }; Node mergeNode(const Node& L, const Node& R) { Node res; res.sum = L.sum + R.sum; res.lmax = max(L.lmax, L.sum + R.lmax); res.rmax = max(R.rmax, R.sum + L.rmax); res.ans = max({L.ans, R.ans, L.rmax + R.lmax}); return res; } const int MAXN = 200005; int n, q; long long a[MAXN]; Node tree[MAXN * 4]; void pushUp(int p) { tree[p] = mergeNode(tree[p * 2], tree[p * 2 + 1]); } void build(int p, int l, int r) { if (l == r) { tree[p].sum = a[l]; tree[p].lmax = a[l]; tree[p].rmax = a[l]; tree[p].ans = a[l]; return; } int mid = (l + r) / 2; build(p * 2, l, mid); build(p * 2 + 1, mid + 1, r); pushUp(p); } void update(int p, int l, int r, int pos, long long val) { if (l == r) { tree[p].sum = val; tree[p].lmax = val; tree[p].rmax = val; tree[p].ans = val; return; } int mid = (l + r) / 2; if (pos <= mid) update(p * 2, l, mid, pos, val); else update(p * 2 + 1, mid + 1, r, pos, val); pushUp(p); } Node query(int p, int l, int r, int L, int R) { if (L <= l && r <= R) { return tree[p]; } int mid = (l + r) / 2; if (R <= mid) return query(p * 2, l, mid, L, R); if (L > mid) return query(p * 2 + 1, mid + 1, r, L, R); Node left = query(p * 2, l, mid, L, R); Node right = query(p * 2 + 1, mid + 1, r, L, R); return mergeNode(left, right); } int main() { ios::sync_with_stdio(false); cin.tie(nullptr); cin >> n >> q; for (int i = 1; i <= n; i++) cin >> a[i]; build(1, 1, n); 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).ans << '\n'; } } return 0; }

为什么查询时不能用“先初始化一个空结果，然后一直 merge”？因为默认的空节点{0,0,0,0}并不是“空区间”的正确语义，当一个合法区间和空区间合并时，结果会错。所以我上面的写法是按递归顺序返回左右子查询结果，只有两段都存在时才合并，这样能保证不会把空节点混进去。这是区间合并类线段树查询最实用的一个写法。

6.3 关于“非空子段”的坑

最后提醒一个非常隐蔽的问题：这道题要求子段非空，所以叶子节点初始化时不能把负数设成 0。很多人写线段树维护最大子段和时，会在build的时候写成lmax = max(0, a[l])，这在允许“空子段”的题目里是对的，但在这题里就错了。比如数组[-1, -2]，允许空段时最大答案是 0，非空答案应该是 -1。如果按允许空段的写法初始化，查询结果会直接错掉。

解决方法是叶子节点一律直接用原始值。合并公式里的L.rmax + R.lmax也没有取 0 再相加，因为一旦取 0，空段就又混进来了。这个细节是 F 题区分会不会写的一个关键点。

7. 实战复盘：时间安排与易错点清单

7.1 我这场踩过的坑

先说说自己在 D 题上浪费的十几分钟。一开始我确实走了贪心路线，想直接找数组里最小的负数去删，结果第二个样例就挂了。后来冷静下来，把题目抽象成“删除位置 i 后，左右两侧能不能接起来”，很快就想到了前后缀数组。这个思维转换看起来简单，但如果没有提前意识到“连续性”的重要性，很容易陷在局部最优里出不来。

E 题我写代码时犯了一个低级错误：从队列里取出状态后，忘了同时取出last对应的距离，直接用了当前点 u 的另一个状态距离去更新，导致答案一直偏小。排查了半天才意识到，dist[last][u]和dist[other][u]是两个完全不同的数组元素，不能用混。这种错误在做拆点题时很常见，因为它本质上就是把一个点复制成了多个，但人在写代码时还容易把它当成同一个点来对待。

F 题我的问题出在查询函数。第一次写的是用一个res变量去不停 merge 递归结果，结果在跨区间查询时顺序乱了，返回的lmax和rmax完全不对。后来改成了“如果是两侧都有，就直接merge(left, right)”，代码一下子就清晰了。遇到这种区间合并类的题目，返回结构体比返回一个值要安全得多。

7.2 给下次比赛的 5 条建议

第一，开赛先花三分钟把六道题的题面全部读一遍，对大概难度做到心里有数，别卡死在 A 题上。第二，简单题再简单，也要先跑一遍样例再提交，别省这一下。第三，遇到“删除类”问题，优先想前后缀拆分的思路，再想贪心，因为删除对连续性的破坏往往需要用左右两段拼合来处理。第四，图论题如果觉得状态记不住，赶紧往拆点、分层图上靠，不要硬套普通最短路模板。第五，线段树代码平时要整理成自己的模板，连 build、update、query 的标准写法都现场推，比赛时间根本不够用。

说实话，这场的六道题没有一道是需要“灵光一现”才能做的，全部是基本功的组合体。C 题是搜索，D 题是前后缀，E 题是拆点，F 题是线段树。如果你能把这几块基础内容练熟，下次遇到类似的场次就会轻松很多。我自己把这套题补完之后，最大的收获是把线段树区间合并的模板又重构了一遍，以后再做带区间查询的题，至少不会在合并顺序这种地方翻车了。