第一章：算法分析与解题方法
算法设计通常从分析题意开始：先明确需要计算的对象，写出能够直接解决问题的做法，再根据数据范围寻找重复工作或可利用的性质，逐步改进算法。每一次改进都需要说明保留了哪些信息、为什么仍能得到正确答案，以及时间和空间开销发生了什么变化。
本章使用循环、条件判断和一维数组完成这些分析。阅读前需要掌握基本输入输出、整数与字符类型。
1. 从题意到算法
1.1 分析题意，建立直接做法
简易题面：给出 (n) 个互不相同的正整数，统计其中有多少个数能够表示为另外两个不同数的和。同一个数即使有多种表示方法，也只计数一次。
数据范围：(3 \le n \le 100)，(1 \le a_i \le 10000)，所有 (a_i) 互不相同。
题目要求统计满足条件的输入数。对于每个输入数，需要判断其余数中是否存在两个数，它们的和恰好等于这个数。例如，输入 (1,2,3,4,5) 时，(3=1+2)，(4=1+3)，(5=1+4=2+3)。满足条件的是 (3,4,5)，答案为 (3)；虽然 (5) 有两种表示方法，它仍然只贡献一次答案。
因此，可以先固定一个数 (a_k) 作为目标，再依次尝试两个加数 (a_i,a_j)，检查是否满足 (a_i+a_j=a_k)。检查完一个目标后，换下一个目标，直到全部输入数都被检查。这个做法直接遍历目标和加数的可能选择，对应三层循环。
两个加数交换顺序不会产生新的选择，所以只枚举 (i<j)。此外，所有输入数都是正数，若 (a_i+a_j=a_k)，两个加数都必然小于 (a_k)，不可能是目标本身。因此，循环不需要额外排除下标 (k)。
计数时，每个目标使用一个布尔变量 ok，表示是否找到过合法的加数对。找到一对后只把 ok 设为真，等该目标检查结束后再累加答案，便能避免把多种表示方法重复计数。以下假设输入已存入 a[1] 至 a[n]，答案变量 ans 初始为 (0)。
for (int k = 1; k <= n; ++k)
{
bool ok = false;
for (int i = 1; i <= n; ++i)
{
for (int j = i + 1; j <= n; ++j)
{
if (a[i] + a[j] == a[k])
{
ok = true;
}
}
}
if (ok)
{
++ans;
}
}1.2 发现重复计算，改用预处理
上述做法对每个目标都枚举一遍加数对。例如，判断 (3) 能否表示为两数之和时，会计算 (1+2)；判断 (4) 或 (5) 时，还会计算同一个和值。改变的是目标，两个加数及其和值并没有改变。
这一重复来自三层循环的依赖关系：(a_i+a_j) 只由 (i,j) 决定，与目标下标 (k) 无关。如果先记录所有加数对能够得到哪些和值，之后判断一个目标时，就可以直接查看记录，不必重新枚举加数。
输入数不超过 (10000)，所以两数之和不超过 (20000)。这个范围可以用数组保存：令 has[s] 表示是否存在一对合法加数，它们的和等于 s。数组初始全为假；枚举所有 (i<j)，将对应和值的位置设为真；最后依次检查每个输入数对应的标记。
仍以 (1,2,3,4,5) 为例，(1+4) 和 (2+3) 都会将 has[5] 设为真，但真假标记只记录“存在”，不会记录两种表示方法。最后检查输入数 (5) 时，答案只增加一次。
以下假设 has 能容纳下标 (0) 至 (20000)，已初始化为假，ans 初始为 (0)。
for (int i = 1; i <= n; ++i)
{
for (int j = i + 1; j <= n; ++j)
{
has[a[i] + a[j]] = true;
}
}
for (int k = 1; k <= n; ++k)
{
if (has[a[k]])
{
++ans;
}
}每个被标记的和值都由一对合法加数产生，每对合法加数也都会在 (i<j) 的循环中出现，因此标记既不会凭空增加可行结果，也不会遗漏可行结果。最后每个输入数只检查一次，计数对象与原题一致。
这次优化将“对每个目标分别枚举加数”改成了“统一枚举加数，再查询目标”。节省重复计算所付出的代价，是增加一个保存和值的数组。
1.3 检查优化所依赖的条件
按和值开数组依赖于较小的值域。如果同类问题把每个输入数的上限改成 (10^9)，和值就可能达到 (2\times 10^9)，需要的数组位置也会达到二十亿量级。即使输入只有 (100) 个数，这种保存方式仍会占用大量内存。元素个数与数值范围必须分别分析。
保存的信息也由题目要求决定。本题只需判断某个和值是否存在，布尔标记已经足够；如果改为统计某个和值有多少种表示方法，就需要保存次数。优化可以改变计算顺序和保存方式，但不能丢掉答案所需的信息。
2. 时间复杂度与数据范围
2.1 从循环次数得到复杂度
《珠心算测验》的直接做法中，固定一个目标后，加数对的数量为
[ (n-1)+(n-2)+\cdots+1=\frac{n(n-1)}{2}. ]
全部 (n) 个目标合计进行
[ n\cdot\frac{n(n-1)}{2}=\frac{n^3-n^2}{2} ]
次和值比较。代入 (n=100)，得到 (495000) 次，因此直接做法已经能够处理原题的数据规模。
输入规模增大时，上式中增长最快的项是 (n^3)。忽略常数系数和较低次项，时间复杂度记为 (O(n^3))。这里的复杂度描述工作量随规模增长的速度，并不是程序的精确运行时间。当 (n) 翻倍时，主要工作量约变成原来的 (8) 倍。
改用标记数组后，只需枚举一遍数对，再检查 (n) 个目标。设最大可能的和值为 (V)，把数组初始化也计入，总时间复杂度为 (O(n^2+V))。原题最多生成 (4950) 个和值、检查 (100) 个目标，另需初始化约两万个标记。
如果直接做法加入“找到一对后立即停止”的处理，部分输入会少做一些比较，但最坏情况的复杂度仍为 (O(n^3))。例如，输入全部来自 (6001) 至 (6100) 时，任何两数之和都不在输入中，每个目标仍需检查全部数对。
2.2 按总工作量分析循环
循环层数不能单独决定复杂度，还需要统计各层循环实际执行的次数。
| 循环结构 | 总执行次数 | 时间复杂度 |
|---|---|---|
| 先执行 (n) 次，再执行 (m) 次 | (n+m) | (O(n+m)) |
| 外层执行 (n) 次，每轮内层都执行 (m) 次 | (nm) | (O(nm)) |
| 外层变量从 (1) 到 (n)，第 (i) 轮内层执行 (i) 次 | (n(n+1)/2) | (O(n^2)) |
若令正整数变量 x 初始等于 (n)，每轮执行 x /= 2，直到变为 (0)，循环次数则与 (n) 的二进制位数相同。例如，初值为 (20) 时，数值依次变为 (10,5,2,1,0)，共执行 (5) 轮。一般需要 (\lfloor\log_2 n\rfloor+1) 轮，时间复杂度为 (O(\log n))。
常见复杂度与工作量结构如下。表中的结构用于识别增长速度，不代表某个规模一定能通过所有题目的时限。
| 时间复杂度 | 典型的工作量结构 |
|---|---|
| (O(1)) | 固定次数的算术运算或判断 |
| (O(\log n)) | 每轮把剩余规模缩小到固定比例 |
| (O(n)) | 每个元素处理固定次数 |
| (O(n\log n)) | 约 (\log n) 层，每层总工作量为 (O(n)) |
| (O(n^2)) | 枚举全部数对 |
| (O(n^3)) | 枚举全部三元组 |
| (O(2^n)) | 枚举 (n) 个位置各选或不选的全部方案 |
| (O(n!)) | 枚举 (n) 个不同对象的全部排列 |
2.3 把全部数据限制计入估算
算法是否需要继续优化，首先取决于最大数据下的工作量。例如，将一个平方复杂度算法的规模分别取为 (500) 和 (10^5)，对应的主要操作次数约为 (2.5\times 10^5) 和 (10^{10})。同样是两层循环，处理这两种规模的可行性有很大差别。
询问次数和测试组数也需要计入。如果一次查询需要扫描 (n) 个数，连续进行 (q) 次查询，总时间复杂度就是 (O(nq))。如果每组数据都要清空长度为 (V) 的数组，这部分初始化也有 (O(V)) 的开销。
在复杂度相同的情况下，操作内容仍会影响运行时间。例如，整数比较与长字符串比较的代价不同。因此，复杂度和操作次数用于初步判断，接近时限时还需要结合具体实现与实际测试，不能依赖固定的“每秒运算次数”。
3. 空间、下标与整数范围
3.1 从重复移树到位置标记
简易题面：数轴上从 (0) 到 (L) 的每个整数位置都有一棵树。给出 (m) 个闭区间，移走这些区间内的树，输出剩余树的数量。区间可以重叠。
数据范围：(1 \le L \le 10000)，(1 \le m \le 100)，每个区间满足 (0 \le l \le r \le L)。
初始共有 (L+1) 棵树，单个区间 ([l,r]) 包含 (r-l+1) 棵。如果所有区间互不重叠，可以从总数中依次减去每段包含的树数。但题目允许重叠，直接相减会把重叠位置的树重复扣除。
例如，取 (L=10)，移走 ([2,5]) 和 ([4,7])。两段各包含 (4) 棵树，但位置 (4,5) 同时属于两段。实际移走的是位置 (2) 至 (7) 的 (6) 棵树，剩余 (5) 棵。
重复扣除的原因是只记录了区间包含多少棵树，没有记录具体哪些树已经移走。为每个整数位置保存一个真假状态，就能区分“已经移走”与“仍然存在”。令 cut[x] 表示位置 x 的树是否已移走，初始全为假。每读到一个区间 ([l,r])，执行以下标记：
for (int x = l; x <= r; ++x)
{
cut[x] = true;
}同一个位置被多次标记，结果仍然为真。处理完全部区间后，cut[x] 为真当且仅当位置 x 至少属于一个移树区间，因此只需统计仍为假的位置。
int ans = 0;
for (int x = 0; x <= L; ++x)
{
if (!cut[x])
{
++ans;
}
}每个区间最多标记 (L+1) 个位置，最后扫描 (L+1) 个位置，总时间复杂度为 (O(mL+L))。原题最多约一百万次标记，直接按位置处理即可。每读到一个区间便完成标记，不必保存全部区间；标记数组需要 (O(L)) 空间。
3.2 根据下标范围确定数组容量
《校门外的树》需要访问 cut[0] 至 cut[L]，一共 (L+1) 个元素。若声明 bool cut[10000];，合法下标只有 (0) 至 (9999)，访问位置 (10000) 就会越界。按原题范围，可以声明 bool cut[10010];，覆盖全部合法位置。
《珠心算测验》则用和值作为 has 的下标。虽然输入最多只有 (100) 个数，标记数组仍需容纳到 (20000) 的下标。数组容量由最大访问下标决定，不能只根据输入元素个数确定。
全局数组会被零初始化，布尔元素因此初始为假；普通局部数组若未初始化，元素值不能直接使用。多组数据共用同一数组时，还需要在新一组开始前恢复初始状态。
3.3 估算总内存
空间复杂度描述存储量随规模增长的变化，实际内存还需要乘每个元素的字节数。常见竞赛环境中，int 占 (4) 字节，long long 占 (8) 字节，bool 通常占 (1) 字节，具体大小可用 sizeof 查看。
三个各含一百万个元素的 long long 数组，仅元素存储就需要约 (24) MB。多个数组的空间需要相加；把数组放在全局可以避免部分栈空间限制，但不会减少这些数组占用的总内存。
例如，《珠心算测验》的优化做法需要保存 (n) 个输入数和到下标 (V) 的和值标记，总空间复杂度为 (O(n+V))。时间上少做了重复枚举，空间上则增加了与值域相关的存储。
保存哪些数据取决于后续操作。移树结束后需要按位置查看状态，因此保留标记数组；若只求一串输入数字的总和，则可以边读边累加，只保存累计和。后续不再使用的单个输入无须全部存入数组。
3.4 检查中间结果的整数范围
考虑求和问题：输入 (n) 个非负整数并输出总和，其中 (1\le n\le 10^5)，每个数不超过 (10^9)。单个输入可以用常见的 (32) 位有符号 int 保存，但总和可能达到 (10^{14})，因此累计变量需要使用 long long。
常见的 (32) 位有符号 int 最大值约为 (2.147\times 10^9)，(64) 位有符号 long long 最大值约为 (9.22\times 10^{18})。类型选择需要同时考虑输入、保存的状态、中间表达式和最终答案。
例如，两个 int 变量 x、y 都可能达到 (10^9)。写成 long long s = x * y; 时，右侧仍然先按 int 进行乘法，可能在赋值前就已溢出。写成 long long s = 1LL * x * y;，才能让乘法从开始就在 long long 范围内进行。加法同理，需要时应在运算前提升类型。
如果已经证明整个计算过程中都不会超出 int 的范围，就可以保留 int。类型由数值上界决定，不需要把所有整数变量统一加宽。
4. 正确性与循环不变量
4.1 从筛选日期到维护当前最优结果
简易题面：连续七天，每天给出两段上课时间。当天总时间超过八小时才会不高兴，总时间越大越不高兴。输出最不高兴的那一天；并列时选最早的一天；如果七天都没有超过八小时，输出 (0)。
数据范围：固定输入七组数据，每段时间都是 (0) 至 (9) 的整数。
将第 (i) 天两段时间相加，记为 (h_i)。题目可以分成两步：先排除 (h_i\le 8) 的日期，再从其余日期中找出总时间最大且最早的一天。直接做法是算出七天的总时间，然后依次比较各天是否应当成为答案。
比较过程中，不必反复查看所有已经处理的日期。例如，前三天的总时间为 (8,9,9) 时，当前答案是第 (2) 天，总时间为 (9)。加入第 (4) 天后，只需把它的总时间与 (9) 比较：若更大，就选第 (4) 天；若更小或相等，仍选第 (2) 天。前面被淘汰的日期不会因为加入新的一天而变得更优。
由此，只需维护当前选中的日期 ans 和对应的时间门槛 mx。初始令 ans 为 (0)、mx 为 (8)，表示尚无超过八小时的日期。按日期从前往后扫描，只有当天总时间严格大于 mx 时才更新；相等时保留旧答案，它的日期一定更早。
以下假设七天的总时间已经存入 h[1] 至 h[7]。
int ans = 0, mx = 8;
for (int i = 1; i <= 7; ++i)
{
if (h[i] > mx)
{
mx = h[i];
ans = i;
}
}以七天总时间 (8,9,9,7,10,10,8) 为例，变量变化如下。
| 日期 | 1 | 2 | 3 | 4 | 5 | 6 | 7 |
|---|---|---|---|---|---|---|---|
| 当天总时间 | 8 | 9 | 9 | 7 | 10 | 10 | 8 |
处理后 mx | 8 | 9 | 9 | 9 | 10 | 10 | 10 |
处理后 ans | 0 | 2 | 2 | 2 | 5 | 5 | 5 |
4.2 用循环不变量说明正确性
处理完前 (i) 天后，mx 等于 (8,h_1,h_2,\ldots,h_i) 中的最大值；如果没有一天超过八小时，ans 为 (0)，否则 ans 是其中总时间最大且最早的日期。这个关于已处理部分和程序状态的结论，在每轮结束后都成立，称为循环不变量。
证明可以分为三个阶段：
- 开始前，还没有处理任何一天。
mx为 (8)、ans为 (0)，符合初始含义。 - 加入新的一天时，若它的总时间严格超过当前门槛，就更新答案；否则保留旧答案。前一种情况选中了更大的总时间，后一种情况保留了此前的最大值，相等时也保留了更早的日期，因此结论继续成立。
- 循环结束后，已经处理全部七天，
ans就是整周中符合题意的日期。
严格比较同时保证了门槛和并列规则。如果改成 h[i] >= mx，总时间恰好为八小时的日期可能被错误选入，后出现的并列最大值也会覆盖更早的日期。
本题固定处理七天，时间和额外空间均为 (O(1))。推广到 (n) 天时，比较需要 (O(n)) 时间；若边读入当天时间边更新答案，只需 (O(1)) 额外空间。
4.3 用边界数据检查实现
正确性说明需要落实到具体条件。测试时可以围绕门槛、并列、重复操作和端点分别构造数据，检查实现是否符合已经建立的结论。
| 检查对象 | 数据 | 可能暴露的错误 |
|---|---|---|
| 津津的时间门槛 | 七天总时间都为 (8) | 把“不超过八小时”错误地选入答案 |
| 津津的并列规则 | 第一天和第七天同时取得大于 (8) 的最大值 | 相等时覆盖了更早的日期 |
| 移树的重复操作 | 两次输入完全相同的区间 | 重复扣除了同一棵树 |
| 移树的端点 | 只移走 ([0,0])，或移走整个 ([0,L]) | 遗漏位置 (0) 或 (L) |
| 珠心算的计数对象 | 输入 (1,2,3,4,5) | 把同一个目标的多种表示重复计数 |
| 珠心算的无解情况 | 输入 (5,6,7) | 答案或标记没有正确初始化 |
存在直接做法和优化做法时，还可以在小数据上分别运行两种实现并比较答案，这种检查称为对拍。样例、边界测试和对拍有助于发现错误，但有限次测试不能代替正确性证明。发现错误后，逐步删去无关数据，保留仍能触发错误的小例子，通常更容易定位原因。
5. 特殊性质与部分分
5.1 从乘方的定义建立直接做法
例题：CSP-J 2022·乘方。
简易题面：输入两个正整数 (a,b)。若 (a^b \le 10^9)，输出 (a^b)；否则输出 (-1)。
数据范围：(1 \le a,b \le 10^9)。
根据乘方的定义，可以令累计值初始为 (1)，连续乘 (a) 共 (b) 次，再检查结果是否超过上限。这个做法对小指数有效，但完整数据中 (b) 可能达到十亿，逐次相乘的时间过长，乘积也可能超出整数类型范围。
这两个困难都出现在“计算完整的 (a^b)”这一步。题目的输出要求却只区分两种情况：不超过 (10^9) 时输出准确值，超过时统一输出 (-1)。因此，一旦能够确认结果必然超限，后续的准确数值就不再影响答案。
5.2 利用增长性质提前停止
当 (a\ge 2) 时，累计值每乘一次至少翻倍，且之后不会减小。所以累计值一旦超过 (10^9)，最终结果也一定超过上限，可以立即停止。
又因为 (2^{30}=1073741824>10^9)，至多检查到第 (30) 次乘法，就能确定是否超限。若指数不足 (30)，则完成规定次数即可。原本可能执行十亿次的循环，由结果的增长速度和输出上限限制到了至多 (30) 轮。
还需要单独考虑 (a=1)：此时结果始终为 (1)，不会触发超限停止。如果仍执行 (b) 次循环，就无法解决指数过大的问题。因此，这种情况直接得到答案 (1)，其余情况再逐次相乘。
5.3 在乘法之前判断是否超限
提前停止只能减少乘法次数，仍需保证检查本身不会溢出。设当前累计值为 (s)，上限为 (M)。由于 (s,a) 都是正整数，有
[ sa>M\quad\Longleftrightarrow\quad s>\left\lfloor\frac{M}{a}\right\rfloor. ]
因此，可以先做整数除法和比较，确认乘积不超过上限后再相乘。代码中的 1000000000 / a 对正整数执行向下取整，恰好对应右侧条件。这样每次实际乘法的结果都不超过 (10^9)，累计值使用 int 即可。
以下假设 a、b 已读入，片段结束后的 ans 为应输出的答案。
int ans = 1;
if (a > 1)
{
for (int i = 1; i <= b; ++i)
{
if (ans > 1000000000 / a)
{
ans = -1;
break;
}
ans *= a;
}
}每次成功相乘后，ans 都等于已经完成的那部分幂。若下一次乘法将超限，后续乘法只会使结果继续增大，因此将答案设为 (-1) 并停止是正确的；若完成全部 (b) 次乘法，则得到准确的 (a^b)。
对于固定上限 (10^9)，本题至多进行 (30) 轮检查，时间和额外空间均为 (O(1))。若把上限推广为变量 (M\ge 2)，则 (a\ge 2) 时需要 (O(\min(b,\log M))) 时间。
| 输入 | 输出 | 检查目的 |
|---|---|---|
1 1000000000 | 1 | 底数为 (1) 时不进入循环 |
10 9 | 1000000000 | 恰好等于上限时保留准确值 |
2 30 | -1 | 超限时提前停止 |
1000000000 2 | -1 | 在可能溢出的乘法发生前完成判断 |
5.4 从部分分观察限制的作用
《乘方》的题面还给出了以下分档保证，可以据此分析直接做法在哪些条件下有效。
| 累计数据比例 | 保证条件 | 可行做法 |
|---|---|---|
| 10% | (b=1) | 直接得到 (a) |
| 30% | (b\le 2) | 至多进行两次乘法，使用足够宽的类型 |
| 60% | (b\le 30)，且 (a^b\le 10^{18}) | 使用 long long 逐次相乘，再判断是否超过输出上限 |
| 100% | (a,b\le 10^9) | 利用输出上限提前停止，并处理 (a=1) |
限制从小指数放宽到任意指数后，直接做法的循环次数首先失去保证。重新分析输出要求和乘积的增长性质，才能得到完整算法。类似地，《校门外的树》在区间互不重叠时可以直接相减，允许重叠后则需要记录位置状态。
部分分分析应明确每档的保证条件、对应做法和复杂度。针对特殊条件成立的算法，只能用于满足这些条件的输入；题面中的数据比例也不能仅凭“小数据”“特殊性质”等描述自行估计。若采用子任务整体计分，还需要通过该子任务中的全部测试点。