企业官网建设流程全解析

开篇先交代一下背景：这周我把学校OJ上编号为65、67、68、69的四道题连着刷完了。题号中间缺了个66，实际是之前已经写过，这四道是同一轮算法基础训练章节的收尾题。单独看每一题都不算难，但如果把它们放在一起看，会发现一条很清晰的递进路线：从一维区间查询，到有序序列查找，再到决策状态优化，最后落到集合关系维护。本篇文章就把这四道题放在一起复盘，重点讲每道题的思路、边界条件、以及我实际提交过程中踩过的坑，适合正在刷OJ入门算法、准备校赛、或者想系统捋一遍基础数据结构的读者。

1. 为什么把65、67、68、69放一起刷：这组题的出题逻辑

说句实在话，按题号一题一题刷OJ是效率很低的习惯。我这周之所以把65、67、68、69连着做，是因为它们正好是OJ上"基础算法专题四件套"的收尾题，前几题分别是数组、排序、枚举，后面的题开始引入数据结构与动态规划。

1.1 题号之间的隐藏递进关系

65题考的是前缀和，本质是"用空间换时间，把连续区间的重复计算预先合并"。67题考的是二分查找，本质是"在一个有序空间里，通过一次比较消去一半的搜索范围"。68题考的是0-1背包动态规划，这题开始不再是简单的查询和查找，而是要在所有组合中选择一个最优方案，出现了"选/不选"的状态决策。69题考的是并查集，处理的是"两个元素是否属于同一集合"这种抽象关系。

表面看四道题没有任何关联，但它们其实是在训练同一个底层能力：把暴力解法里重复出现的计算过程找出来，用某种结构去复用。

从实战角度来说，这四类问题是算法竞赛里出现频率最高的四种基本功。前缀和是线段树与树状数组的基石，二分是二分答案、实数二分、整体二分这些进阶技巧的前提，0-1背包是所有背包问题与状态压缩DP的入门款，并查集则是最小生成树的判环工具。理解这四道题，后续再往上走会顺很多。

1.2 刷题顺序建议与准备工作

如果读者也想按这个顺序刷，我建议不要直接打开OJ就写代码。先准备一个统一的模板文件，把常用的头文件、快读函数、数组空间都设定好。我的模板是固定用#include <bits/stdc++.h>，输入输出直接用scanf和printf，不混用cin且关闭同步，避免被IO耗时坑。

其次，这四道题最好分成两次刷：65和67是"查找与查询"一组，68和69是"状态与集合"一组。先做完前两题，理解了"有序性"和"可累加性"之后，再做后两题，会觉得动态规划和并查集的转移逻辑没有那么陡峭。我这次是周一刷65和67，周三刷68和69，中间留了两天消化。

2. 第65题：区间求和里藏着的三个边界陷阱

2.1 题目本质：如何把O(nm)降下来

65题的要求很简单：给定n个整数，之后有m次询问，每次给定l和r，求第l个数到第r个数的和。n和m的范围都到了10万甚至更大。最直接的写法是每次循环累加一次，复杂度O(nm)，在n和m都是10万时总计算量是10的10次方，跑一遍测试点基本稳超时。

正确做法是前缀和。开一个长度为n+1的数组s，s[i]表示前i个元素的总和，初始化时依次累加。查询[l, r]时直接输出s[r] - s[l - 1]。这一步之所以快，是因为查询时不再需要遍历任何区间，任何区间和都等价于两个前缀和的差。

很多刚入门的朋友会有个疑问：前缀和不就是换个方式存一遍数据吗？其实关键差别在于，一次性预处理的时间成本是O(n)，之后每次查询都是O(1)。而暴力方法每次查询都要线性扫，预处理没有复用价值。用一个生活里常见的例子打比方：如果每天记录当月累计花销，那么想知道某段时间花了多少，只需要拿月末累计减去月初累计，不需要把中间每一笔都重新加一遍。

2.2 ac代码之外的边界自查

这道题我一次AC了，但我知道很多同学会在下面三个位置挨个踩坑，所以直接把自查点列出来：

第一，数组下标从1开始。s[0]要保留为0，否则查询包含第1个元素时，s[l-1]就会落到s[0]之外，产生未定义行为。我习惯读入时从索引1开始，让前缀和数组天然对齐查询下标。

第二，计算区间差一定要用s[r] - s[l - 1]。如果错写成s[r] - s[l]，意味着扣掉了第l个元素本身，只有l=1时碰巧正确，其余全部偏小。这类错误特别容易出现在倒计时压力之下，因为样例往往恰好让l=1，一测就过，一交就WA。

第三，数据范围。n个数累加后可能超过int上界，题目明确会给出大范围时，s数组一定要开成long long或者int64。我见过太多人因为改了long long后忘记改输出格式符，导致本地正常而评测错乱。

#include <bits/stdc++.h> using namespace std; int main() { int n, m; scanf("%d%d", &n, &m); vector<long long> s(n + 1, 0); for (int i = 1; i <= n; i++) { long long x; scanf("%lld", &x); s[i] = s[i - 1] + x; } while (m--) { int l, r; scanf("%d%d", &l, &r); printf("%lld\n", s[r] - s[l - 1]); } return 0; }

代码本身不复杂。我特别想提醒的一点是：不要以为这题太简单就轻视边界，OJ上这类题的正确率往往只有六成左右，大部分错误都出在l-1的细节上。写完后一定要造一个l=1、r=n的极端样例，以及l=r=1的单点样例，各跑一遍再提交。

2.3 如果题目从"询问"变成"询问加修改"

65题有个很自然的进阶：如果每次操作有时候是查询区间和，有时候是修改某个位置的值，前缀和还能用吗？能用，但每次修改都需要重新更新后续所有前缀和，复杂度又退化到O(n)。所以OJ后面必然会引出树状数组、线段树这类支持单点修改与区间查询的数据结构。

我这次刷完65后，没有立刻去碰树状数组，而是先记下这一个知识点：前缀和适用于"静态数据多次查询"。一旦数据会变，就要换结构。这也是为什么我建议把这类题整理成专题，而不是零散地刷，因为只有连起来才能看清前置依赖。

3. 第67题：二分查找，我在这道题上交了三次RE才摸清边界

3.1 二分题的核心不是"找到"而是"证明位置"

67题题意是在一个非降序列中，每次询问一个x，要求输出第一个大于等于x的元素下标，若不存在则输出n+1。

我先说结论：二分查找的真正难点不是循环条件，而是维护一个"区间性质"。拿这题举例，我们始终维护一个左闭右开区间[l, r)，并且保证：l左侧的元素全部小于x，r及其右侧的元素全部大于等于x。初始时l=0，r=n（这里n是数组长度），因为整个数组一开始没有被检查，这个区间性质天然成立。每一次取中点mid，比较a[mid]和x的关系：

• 若a[mid] >= x，说明mid已经满足"右侧性质"，我们让r=mid，把待定区间的右侧收缩到mid；
• 若a[mid] < x，说明mid不满足条件，则mid及其左侧都可以排除，令l=mid+1。

循环退出时l==r，这个位置就是第一个满足a[mid] >= x的下标。如果不存在这样的元素，l会一路推到n，正好等于题目要求的n+1对应的数组越界哨兵位置。

这种写法的好处是，不需要在循环里面额外判断"找到没找到"，也不需要记录一个答案ans去"临时保存"。很多同学写二分时总抱着"找到target退出"的思路，一旦target不存在就不知道返回什么，本质上是没有把二分当成区间收缩过程，而是仍然当成线性查找。

3.2 一个RE案例：左闭右闭写法的死循环

我第一次写67题用的是左闭右闭区间写法，也就是l=0, r=n-1，循环条件l <= r。代码长这样：

int l = 0, r = n - 1; while (l < r) { int mid = (l + r) / 2; if (a[mid] >= x) r = mid; else l = mid; } printf("%d\n", l + 1);

这段代码在数组中只有一个元素时会死循环。因为l=0, r=0，循环进不去，但明明l < r是不满足的，问题在于我把r的更新写成了r = mid，而左闭右闭里r是合法下标，r = mid时没有把已经检查过的点排除掉。

换成左闭右开写法之后，r表示的是"边界开区间"，允许等于数组长度，r = mid和l = mid+1天然保证了每次循环区间长度严格减小。这就是为什么我强烈建议初学者统一用左闭右开，不要混用两种区间语义。

3.3 mid溢出与"无解"输出

另一个提交时容易忽略的点是mid = (l + r) / 2的溢出。当l和r都接近int上限时，l + r会先溢出再除以2，结果就不是预期中点。正确写法是mid = l + (r - l) / 2。虽然校内OJ数据规模不会到那么极端，但从养成分习惯的角度，我每次写二分都直接用后一种写法，避免某天遇到大范围题目时栽跟头。

无解情况也要单独考虑。题目要求不存在时输出n+1，如果用左闭右开写法，l最终会等于n，此时输出l+1正好是n+1。需要注意的是，数组下标假设从0开始读入，但题目输出要求从1开始数，所以答案为l + 1。如果数组从1开始存储，那么答案是l。这两个写法稍不留神就会差1，提交前要对着样例手算一遍。

67题让我最有价值的收获不是背下模板，而是学会"画区间"。实际做题时，我习惯在草稿纸上画一条数轴，标出左闭右开的两个端点，每次更新后把区间边界重新标一遍。这个过程只要做两三题，二分的基本功就稳了。

4. 第68题：0-1背包里那个"重量为0"的坑

4.1 从暴力列举到动态规划

68题是一个经典的0-1背包：有n件物品，第i件重量为w[i]、价值为v[i]，背包容量为V，问能带走的最大总价值。n大概在1000量级，V在10000量级。

暴力做法是枚举所有子集，也就是2的n次方种选法，n到1000后完全不可行。动态规划的思路是把"决策前i件物品，背包还剩容量j时能获得的最大价值"记录下来。定义dp[i][j]为前i件物品在容量不超过j条件下的最大价值，转移方程长这样：

如果不选第i件物品，dp[i][j] = dp[i-1][j]；如果选，前提是j >= w[i]，则dp[i][j] = max(dp[i][j], dp[i-1][j-w[i]] + v[i])。

注意这里的状态来自dp[i-1][j-w[i]]，也就是上一层的状态，绝不能用本层已经被更新过的值去推导。这一点是后面一维压缩能否成立的关键。

4.2 一维数组为什么必须逆序

二维DP空间是n * V，1000乘10000就是1千万个整数，内存通常还能接受，但很多题目会把V放大到1e5、1e6，所以必须学会压缩成一维。所谓滚动数组，就是将第一维度i省略，让dp[j]表示"当前循环到第i件物品时，容量j下能获得的最大价值"。

转移变成：

for (int i = 0; i < n; i++) { for (int j = V; j >= w[i]; j--) { dp[j] = max(dp[j], dp[j - w[i]] + v[i]); } }

为什么j必须从大到小？因为dp[j - w[i]]如果已经被本轮更新过，就代表第i件物品可能已经被放入了。如果j从小到大遍历，dp[j-w[i]]在j较小时已经被同一个物品更新，结果就是"同一个物品重复选了很多次"，这就不再是0-1背包，而变成了完全背包。

用一个简单例子验证。假设只有一件物品，重量2，价值3，容量V=4。如果正序循环，j=2时dp[2]=3，j=3时dp[3]=3，j=4时dp[4]=max(dp[4], dp[2]+3)=6，一看就知道错了，因为我只有一件物品，最大价值只可能是3。逆序循环时，j=4先算，此时dp[2]还没被本轮更新，dp[4]=3；再算j=3取到3；最后j=2取到3，结果正确。

4.3 重量为0时一维背包会悄悄出错

我重点想讲这个坑，因为不少同学的模板里把内层循环条件写成j >= w[i]，一旦出现w[i] == 0，循环条件变成j >= 0，遍历范围是全容量。此时无论逆序与否，都会出问题：因为dp[j - w[i]]就是dp[j]本身，在同一个物品的同一轮更新中，dp[j]被读取时可能是自己刚被更新过的值，理论上同一件物品能被不断叠加。

实际表现通常是dp[V]偏大，和暴力枚举结果对不上。这个问题在校内OJ的数据范围里不一定会被卡，因为题目数据生成时可能有意避免了0重量，但到了正式比赛，出题人非常喜欢塞这种隐藏边界。

解法有两种。一种是在DP前把重量为0的物品单独拎出来，直接把价值累加到一个全局变量里，因为重量为0的物品无论如何都会带上，不会影响其他物品；另一种是老老实实用二维DP，让状态来源锁定在i-1层，彻底规避同层污染。我个人更推荐在0-1背包模板最开头加一句对w[i] == 0的特判，先把价值累加，再在循环里跳过它，这样模板更加稳健。

68题整体不复杂，但它把"状态转移的来源必须是上一个阶段"这句话讲透了。以后再学完全背包、多重背包、分组背包，全都建立在理解这个逆序原因的基础上。

5. 第69题：并查集，路径压缩之外还要不要按秩合并

5.1 连通性判断与Kruskal场景

69题的背景是一张n个点m条边的无向图，之后有q次询问，每次问两个点u和v是否连通。如果对每个询问都做一次DFS或BFS，最坏情况下每次都要遍历整张图，次数一多程序就直接超时。

并查集的做法是把所有点初始化为独立的集合，读入每条边时合并两个端点所在的集合。之后每个询问只需要比较两个点的"代表元素"是否一致，也就是find(u) == find(v)，单次接近O(1)。

我在代码里常用这样一套写法：

const int MAXN = 100005; int fa[MAXN], sz[MAXN]; int find(int x) { while (fa[x] != x) { fa[x] = fa[fa[x]]; x = fa[x]; } return x; } void unite(int a, int b) { int ra = find(a), rb = find(b); if (ra == rb) return; if (sz[ra] < sz[rb]) swap(ra, rb); fa[rb] = ra; sz[ra] += sz[rb]; }

find里用了路径压缩，让沿途节点直接指向根，后续查找会越来越快。unite里做了按秩合并，用集合大小作为秩，把小的集合合并到大的集合下面。如果只做路径压缩不按秩合并，绝大多数情况下也很快，但极端构造下可能退化成一条长链，路径压缩虽然能缓解，总是一次调用要沿链走到底。按秩合并能让树高始终保持在O(log n)，与路径压缩配合后效果更稳定。

5.2 一个容易写错的点：合并前必须先找到根

很多新手会写fa[a] = b这种直接赋值，忘了两个端点可能原本就在同一个集合里，也可能其中一个不是根。直接钦定父子关系会破坏集合的代表性，导致后续find返回错误节点。

正确顺序是先ra = find(a), rb = find(b)，如果相同就直接返回，否则才把其中一个根挂到另一个根下面。这属于常识，但比赛时一紧张很容易忘。我刷69题时故意在第一次提交中写了直接合并，结果在一条由多个边连通的点上出现查询错误，样例偏偏又没覆盖到，最后读代码才排查出来。

5.3 并查集"删除"为何不能顺手删点

另一个我在这道题之后才意识到的问题：并查集不支持删除操作。路径压缩本质上改变了树的结构，如果某个点被删掉，它的子树关系变得混乱，很难恢复。常见补救是把操作离线倒过来跑，把"删除"变成"加点"，具体做法是先处理出最终状态下哪些点还在，然后从后往前逐条添加边。

校内OJ里一般不考这种花活，但69题之后我顺手搜了一下带删除的并查集题目，发现自己一直没考虑过离线思想。所以我把这条记在错题本里：当题目看似要求"动态删边"时，先看是否允许离线，如果允许，倒序处理往往比在线维护简单得多。

6. 刷完这四道题后我做的事情：模板整理与自查清单

四道题全部AC之后，我没有直接开下一组题，而是花了半小时把代码重新对着看了一遍，把公共部分抽出来，形成自己的刷题模板。

6.1 最终沉淀下来的通用代码习惯

第一，固定用全局数组而不是vector。OJ上多组测试数据时，vector反复分配会带来额外开销，我一般直接在全局开MAXN大小的数组，每组数据开始前用fill或memset重置。

第二，统一输入输出。scanf和printf是稳定选择，读取整数用%d，64位整数用%lld。我在68题里特意检查了每个dp数组类型，防止int溢出导致样例对但大数据WA。

第三，所有区间查询、二分查找一律写左闭右开。这样做的好处是循环条件和返回结果都很统一，不容易出现+1/-1混乱。模板统一能减少大量低级失误。

6.2 每道题的提交前自查清单

这张表我是真的贴在了显示器边上。很多WA不是思路问题，而是这种固定的小点反复出现。与其每次盯着代码逐行猜，不如形成一张清单，提交前逐项打勾。

6.3 从这组题里总结出来的三个长期习惯

第一，手算小样例再提交。65题我手算了[1,3,5]的全部子区间和，67题手算了[1,3,5,7]查4和查8两种情况，68题手算了单件物品的重选问题，69题手算了一个小三角形的三点连通性。手算过程能暴露大多数边界漏洞。

第二，被卡住时先怀疑三类问题：下标差一、int溢出、初始化遗漏。我在这四道题里踩的所有坑都能归到这三类，后来遇到其他题也是先按这三条排查。

第三，每道题提交后记录一个"一句话要点"。65是"区间和=前缀和之差"，67是"二分维护区间性质而非找值"，68是"状态转移必须来自上一层"，69是"合并前先找根，按秩合并稳"。这些短句后来帮我快速复习，也成了我写专题笔记的骨架。

最后再分享一点个人体会。很多人刷OJ追求AC数量，我刷完65、67、68、69之后反而觉得，AC只是最低要求，真正有价值的是把每道题背后的边界条件和适用范围想清楚。这四道题看起来彼此独立，实际构成了从"快速查询"到"集合维护"的一条完整链路。把这条链路走通之后，再去看线段树、二分答案、状态压缩DP和最小生成树，至少不会觉得底子是空的。如果你也正在刷类似的基础算法专题，建议不要只追题号进度，多花十分钟把前一题的边界和适用场景记下来，后面的路会走得稳很多。