分享
NOI 系列赛事：爆零、踩坑、溢出与实现错误排查手册
Hydro SU @ 2026-8-18 22:53:26

适用范围：CSP-J/S、NOIP、省选、NOI、WC/CTSC 等以 C/C++ 为主的算法竞赛。
目标不是补充算法知识，而是减少“思路正确、实现爆炸”“样例全过、提交全错”“只因为一个边界丢掉整题”的情况。

1. 先建立一个意识：很多爆零并不是算法不会

竞赛中的错误大致可以分成四类：

模型错误：题意理解错、性质判断错、算法本身不成立。
复杂度错误：理论正确，但时间或空间无法通过。
实现错误：边界、下标、初始化、状态转移、数据结构维护出错。
语言与运行时错误：整数溢出、未定义行为、栈溢出、数组越界、比较器非法等。

后两类最可惜，因为它们经常导致：

样例正确，大数据错误；
小数据正确，大数据 RE/TLE；
本地正确，评测机错误；
一部分测试点正确，另一部分出现完全无法解释的结果；
极端情况下整题从预期高分变成 $0$ 分。

因此，写完一道题之后不要只问：

算法对不对？

还要问：

这个算法在题目允许的最大数据、最极端结构和 C++ 的真实执行规则下，是否仍然正确？

2. 整数溢出：NOI 系列最常见的隐形杀手

2.1 `int` 到底能装多大？

通常：

int

是 32 位有符号整数，范围约为：

-2^{31} \le x \le 2^{31}-1

即大约：

-2.147\times10^9 \le x \le 2.147\times10^9

而：

long long

通常是 64 位有符号整数，范围约为：

-9.22\times10^{18} \le x \le 9.22\times10^{18}

因此，只要中间计算可能超过 $2\times10^9$ ，就必须开始警惕 int。

2.2 最经典错误：结果用 `long long`，乘法却先按 `int` 算

错误：

int a = 100000;
int b = 100000;

long long c = a * b;

很多人会认为 c 是 long long，所以没有问题。

实际上：

a * b

会先按照 int 计算。

真实结果：

100000\times100000=10^{10}

已经远超 int。

乘法在赋值给 long long 之前就已经溢出了。

正确：

long long c = 1LL * a * b;

或者：

long long a, b;

高频场景

ans += a[i] * i;
dist + weight;
x * x;
n * (n - 1) / 2;
a * b % mod;

看到乘法时，要条件反射地估算中间值。

2.3 公式本身可能先溢出

例如：

long long ans = n * (n - 1) / 2;

如果 n 是 int，则：

n * (n - 1)

仍然首先按照 int 计算。

正确：

long long ans = 1LL * n * (n - 1) / 2;

2.4 加法也会溢出

例如最短路：

if (dist[v] > dist[u] + w)

如果：

dist[u] = INF;

而 INF 已经接近类型上界，则：

dist[u] + w

可能溢出。

更安全：

if (dist[u] != INF && dist[v] > dist[u] + w)

或者让 INF 与最大可能答案之间保留足够空间。

常用：

const long long INF = 4e18;

但使用之前仍然要确认所有真实计算不会接近它。

2.5 `1 << k` 也是整数运算

错误：

long long x = 1 << 40;

左侧虽然是 long long，但：

是 int。

应写：

long long x = 1LL << 40;

同理：

(1 << n)

如果 $n\ge31$ 就要高度警惕。

2.6 `abs` 也存在极值陷阱

对于有符号整数最小值，例如：

-2^{31}

它的绝对值是：

2^{31}

但这个值无法被 32 位 int 表示。

因此不要想当然认为：

abs(x)

永远安全。

如果数据范围可能碰到类型最小值，应扩大类型后再处理。

2.7 `unsigned` 不是“大一点的 int”

非常危险：

unsigned int x = 0;
x--;

结果不会变成 -1，而会绕回一个很大的正数。

尤其危险：

for (size_t i = n - 1; i >= 0; --i)

size_t 通常是无符号类型，因此：

i >= 0

永远成立。

最终可能形成死循环。

更推荐：

for (int i = n - 1; i >= 0; --i)

或者：

for (size_t i = n; i-- > 0; )

后者必须真正理解语义后再使用。

3. 数值范围检查：写代码前先算上界

对于任何计数、距离、权值、DP 值、答案，都应该先估计最大可能值。

例如：

$n\le10^5$
每条边权最大 $10^9$
最长路径最多经过 $10^5$ 条边

距离理论上可能达到：

10^5\times10^9=10^{14}

显然不能使用 int。

再例如：

$n\le2\times10^5$
每个值最大 $10^9$

前缀和可能达到：

2\times10^5\times10^9=2\times10^{14}

应使用 long long。

建议形成固定习惯

看到数据范围之后先写：

单值最大：
累加多少次：
乘法最大：
最终答案最大：
数组大小：
时间复杂度：
空间复杂度：

这几十秒通常比 Debug 半小时划算得多。

4. 数组越界：最容易 RE，也可能悄悄 WA

4.1 `1...n` 和 `0...n-1` 混用

例如：

int a[N];

for (int i = 1; i <= n; ++i)
    cin >> a[i];

如果：

N == n

则 a[n] 已经越界。

竞赛中如果使用 1-based 下标，通常预留：

const int N = 200000 + 5;

不要刚刚好开到最大值。

4.2 图论数组尤其容易少开

如果有：

$n$ 个点；
$m$ 条无向边；

链式前向星需要存储约：

2m

条有向边。

错误：

Edge e[M];

正确应考虑：

Edge e[2 * M];

并额外预留常数空间。

4.3 状态编号可能比 `n` 大得多

例如：

Trie：节点数可能接近所有字符串总长度；
AC 自动机：同样按字符总数开；
线段树：通常至少 4 * n；
可持久化线段树：节点数量可能达到 $O(n\log n)$ ；
SAM：状态数最多接近 $2n$ ；
Dinic：边通常需要存正反两条；
虚树：节点数不是原树节点数的简单一半，要考虑加入 LCA 后的规模。

不要看到题目有 n 就所有数组都开成 N。

5. 未初始化变量与清空不彻底

5.1 局部变量不会自动清零

int x;
cout << x;

x 的值未定义。

全局数组：

int a[N];

会被初始化为 $0$ 。

局部数组：

void solve() {
    int a[N];
}

则不会自动初始化为 $0$ 。

5.2 多组数据时尤其危险

典型：

while (T--) {
    solve();
}

如果全局结构在 solve() 之间没有完整清空：

vector 残留；
图的边残留；
vis 残留；
indegree 残留；
Trie 节点残留；
DSU 父节点残留；
DP 残留；
线段树 lazy 标记残留。

可能第一组正确，后面全错。

5.3 `memset` 不是万能初始化

安全常见：

memset(a, 0, sizeof a);
memset(a, -1, sizeof a);

但不要想当然：

memset(a, 1, sizeof a);

并不会把每个 int 设为 $1$ 。

它是按字节填充。

对于 32 位 int，得到的通常是：

0x01010101

而不是：

0x00000001

对于复杂对象：

vector
string
map
set

更不能使用 memset 暴力清空内部状态。

6. C++ 未定义行为：本地能跑不代表代码合法

这是竞赛中非常值得重视的一类问题。

6.1 有符号整数溢出属于未定义行为

不要认为：

int x = INT_MAX;
x++;

一定会稳定地变成负数。

从 C++ 语言规则看，这属于未定义行为。

编译器优化时可能基于“有符号整数不会溢出”的前提进行推导，因此不同优化等级可能得到不同结果。

6.2 数组越界同样可能产生诡异结果

a[n] = 1;

哪怕程序没有立即崩溃，也不代表安全。

它可能：

修改另一个数组；
修改循环变量；
修改对象内部状态；
破坏栈；
在某组数据上突然 RE；
开启优化后行为完全改变。

6.3 `vector` 扩容后迭代器、引用、指针可能失效

例如：

vector<int> a;
a.push_back(1);

int &x = a[0];
a.push_back(2);

cout << x;

第二次 push_back 可能导致重新分配内存，使 x 失效。

同样要警惕：

auto it = v.begin();
v.push_back(...);

之后继续使用 it。

7. 循环边界：典型的“一位之差”

7.1 `< n` 还是 `<= n`

高频错误：

for (int i = 1; i < n; ++i)

实际需要遍历：

1,2,\dots,n

少处理最后一个元素。

反过来也一样：

for (int i = 0; i <= n; ++i)

如果数组有效下标是：

0,1,\dots,n-1

就会越界。

7.2 区间到底是闭区间还是半开区间

必须统一：

[l, r]

还是：

[l, r)

特别是在：

二分；
前缀和；
线段树；
STL iterator；
差分；
字符串子串。

如果同一个程序中两种体系混在一起，非常容易出现边界 Bug。

8. 二分查找：不是会写模板就不会错

二分最容易错的不是代码，而是：

究竟在找什么？

常见目标：

第一个满足条件的位置；
最后一个满足条件的位置；
最小可行答案；
最大可行答案。

必须先明确判定函数的单调性。

例如：

false false false true true true

找的是第一个 true。

而：

true true true false false false

找的是最后一个 true。

8.1 `mid = (l + r) / 2` 也可能溢出

更稳妥：

int mid = l + (r - l) / 2;

虽然竞赛中很多下标不会接近 INT_MAX，但养成习惯更好。

8.2 实数二分不要死磕相等

不要：

while (l != r)

浮点数几乎不适合这样判断。

常见做法：

for (int i = 0; i < 100; ++i) {
    ...
}

固定迭代次数通常更加稳定。

9. 前缀和、差分与区间边界

如果定义：

s[i] = a[1] + a[2] + ... + a[i];

则：

\operatorname{sum}(l,r)=s[r]-s[l-1]

特别注意：

l = 1

时会访问：

s[0]

因此 s[0] 必须合法并初始化为 $0$ 。

9.1 二维前缀和最容易漏一项

通常：

$$S_{i,j} = A_{i,j} + S_{i-1,j} + S_{i,j-1} - S_{i-1,j-1}$$

矩形查询同样存在四项加减。

建议不要凭感觉写，每次都明确画出“加两块、减重叠”。

10. 模运算：负数和溢出都是坑

10.1 C++ 的负数取模可能仍是负数

例如：

(-1) % 5

结果通常是：

-1

所以：

(a - b) % mod

可能是负数。

常用：

(a - b + mod) % mod

如果差值可能跨越多个 mod，则：

((a - b) % mod + mod) % mod

10.2 乘法取模前也可能溢出

(a * b) % mod

如果 a、b 是 int，乘法可能先溢出。

至少：

1LL * a * b % mod

如果 a、b 本身可达到 $10^{18}$ ，连 long long 乘积都可能溢出，此时需要：

__int128；
快速乘；
Barrett Reduction；
Montgomery Reduction；

具体取决于题目。

11. `__int128`：会用还要会输入输出

GNU C++ 中常见：

__int128 x;

但：

cin >> x;
cout << x;

默认不能直接使用。

通常需要手写输入输出函数。

例如输出：

void print(__int128 x) {
    if (x == 0) {
        cout << 0;
        return;
    }

    if (x < 0) {
        cout << '-';
        x = -x;
    }

    string s;
    while (x) {
        s.push_back('0' + x % 10);
        x /= 10;
    }

    reverse(s.begin(), s.end());
    cout << s;
}

12. 浮点数：不要把 `double` 当精确实数

12.1 不要直接判断相等

错误：

if (a == b)

对于计算所得浮点数通常不可靠。

常见：

if (fabs(a - b) < eps)

但 eps 也不是随便写的，应结合数值规模和题目误差要求。

12.2 大整数不要无缘无故经过 `double`

double 的有效二进制精度约为 53 位。

因此当整数足够大后，不是每个整数都能被精确表示。

如果题目本质是整数运算，就尽量始终使用整数类型。

12.3 几何题不要只写一个 `eps`

几何中：

点重合；
共线；
点在线段上；
圆相交；
叉积符号；

都可能受到误差影响。

建议封装：

int sgn(double x) {
    if (fabs(x) < eps) return 0;
    return x < 0 ? -1 : 1;
}

然后统一使用 sgn() 判断。

13. 排序比较器：写错可能不是 WA，而是未定义行为

错误：

sort(a.begin(), a.end(), [](int x, int y) {
    return x <= y;
});

std::sort 要求比较器满足严格弱序。

至少应保证：

cmp(x, x) == false

因此通常写：

return x < y;

多关键字排序：

if (a.x != b.x) return a.x < b.x;
return a.y < b.y;

不要随意使用 <=。

14. STL 容器的高频踩坑

14.1 `map[key]` 会插入不存在的 key

if (mp[x] == 0)

如果 x 原本不存在，这句话会直接创建：

{x, 0}

只想检查存在性时：

if (mp.find(x) != mp.end())

或者 C++20：

if (mp.contains(x))

14.2 `priority_queue` 默认是大根堆

默认：

priority_queue<int> q;

最大值优先。

Dijkstra 常用小根堆：

priority_queue<
    pair<long long, int>,
    vector<pair<long long, int>>,
    greater<pair<long long, int>>
> q;

14.3 `lower_bound` 与 `upper_bound` 不要混淆

lower_bound

找第一个：

x_i\ge v

的位置。

upper_bound

找第一个：

x_i>v

的位置。

在 LIS、离散化、统计区间中非常容易因为一个等号失分。

14.4 删除容器元素时注意迭代器失效

典型危险：

for (auto it = s.begin(); it != s.end(); ++it) {
    if (...) s.erase(it);
}

删除之后 it 已经失效。

常见正确写法：

for (auto it = s.begin(); it != s.end(); ) {
    if (...) it = s.erase(it);
    else ++it;
}

15. DFS 与递归：算法没问题，栈先炸了

一条长度为 $n$ 的链：

1 - 2 - 3 - ... - n

递归 DFS 深度就是 $n$ 。

如果：

n=5\times10^5

递归很可能栈溢出。

表现通常是：

RE；
Segmentation Fault；
本地能跑，OJ 崩溃。

解决思路：

改成显式栈；
改写迭代 DFS；
对某些允许控制环境的比赛调整栈，但不要依赖这一点；
树 DP 如果递归过深，也应考虑迭代版。

16. 图论最常见的实现错误

16.1 无向边忘记加两次

add(u, v);
add(v, u);

16.2 DFS 无向图只判断 `vis` 不一定够

某些问题需要区分：

父边；
已访问节点；
返祖边；
重边。

例如桥、割点算法中，仅使用：

if (v == parent)

在存在重边时可能错误。

更稳妥的是记录：

parent_edge

并跳过对应反向边。

16.3 Dijkstra 不能处理负权边

存在负权边时，经典 Dijkstra 正确性不成立。

不要因为样例过了就继续使用。

16.4 Dijkstra 的旧状态需要跳过

常见：

auto [d, u] = q.top();
q.pop();

if (d != dist[u]) continue;

否则虽然很多情况下仍正确，但可能造成大量冗余处理，复杂度恶化。

16.5 Floyd 的 INF 相加

错误：

dis[i][j] = min(dis[i][j], dis[i][k] + dis[k][j]);

如果两项之一是 INF，可能出现溢出或者无意义运算。

可以先判断可达性。

16.6 拓扑排序别忘记检查是否真的处理了全部节点

若处理节点数：

cnt < n

则图中存在环。

只输出队列弹出的结果并不一定是完整拓扑序。

17. 树题最容易错的地方

17.1 根节点的父亲是谁？

常见：

dfs(1, 0);

那么所有与 fa = 0 相关的数组都必须合法。

例如：

depth[u] = depth[fa] + 1;

要求：

depth[0] = 0;

17.2 LCA 倍增层数要够

如果：

n\le10^5

需要大约：

\log_2 10^5 \approx 16.6

至少开到 17 左右，实际一般留余量。

例如：

const int LOG = 20;

如果 $n$ 更大，要重新计算。

17.3 树不一定长得平衡

任何基于“树高大约是 $\log n$ ”的假设都危险。

题目没有保证时，最坏情况完全可能是一条链。

18. 并查集的坑

18.1 初始化范围别少一个

for (int i = 1; i <= n; ++i)
    fa[i] = i;

18.2 `find()` 是否需要路径压缩

int find(int x) {
    return fa[x] == x ? x : fa[x] = find(fa[x]);
}

如果没有路径压缩或按秩合并，某些构造数据可能退化。

18.3 带权并查集方向很容易写反

如果维护：

d[x]

表示 x 到父节点的关系，那么路径压缩时必须同步更新关系量。

这类题建议明确写出不变量，例如：

d[x] 表示 x 相对于 fa[x] 的偏移量

不要只靠记模板。

19. 动态规划：大多数 Bug 都来自状态定义不清

写 DP 前强制写一句：

dp[i][j] 表示什么？

必须精确到：

已经处理了哪些元素；
当前状态包含还是不包含第 $i$ 个元素；
j 是容量、数量、状态还是最后位置；
值表示方案数、最大值、最小值还是可行性。

如果这句话写不清，代码大概率也不稳。

19.1 `-INF` 的选择也可能溢出

例如：

dp[x] = -INF;
dp[y] = max(dp[y], dp[x] + value);

如果 dp[x] 本来就是极小哨兵，再加 value 可能溢出。

常见做法：

if (dp[x] != -INF)
    ...

19.2 滚动数组覆盖顺序

01 背包：

for (int j = V; j >= w; --j)

完全背包：

for (int j = w; j <= V; ++j)

方向写反，解决的就是另一类问题。

不要只背循环方向，要理解：

倒序：本轮状态不能重复使用当前物品；
正序：本轮更新后的状态可以继续使用当前物品。

20. 状态压缩与位运算

20.1 运算符优先级

非常危险：

if (mask & 1 << i == 0)

人脑可能理解为：

(mask & (1 << i)) == 0

但复杂位运算中不要赌优先级。

直接加括号：

if ((mask & (1 << i)) == 0)

20.2 `~mask` 会把高位全部翻转

如果只想对低 n 位取反：

(~mask) & ((1 << n) - 1)

否则高位也会变成 $1$ 。

20.3 位数与类型要匹配

如果状态可能使用第 40 位：

1LL << 40

不要写：

1 << 40

21. 线段树常见爆炸点

21.1 数组至少预留约 `4*n`

典型：

Node tr[N * 4];

21.2 区间长度一定写对

如果节点区间是：

[l,r]

长度为：

r-l+1

不是：

r-l

lazy propagation 中：

sum += value * (r - l + 1);

非常容易漏掉 +1。

21.3 `pushdown` 时不要忘记清除父标记

例如：

tag[left] += tag[p];
tag[right] += tag[p];
tag[p] = 0;

否则标记可能重复下传。

21.4 区间赋值与区间加法不能简单共用一个 lazy

如果同时支持：

区间赋值；
区间加法；

两个标记之间存在组合顺序。

需要明确：

先赋值再加

和：

先加再赋值

如何合成。

这类题最好写出 lazy tag 的代数规则再编码。

22. 树状数组常见错误

BIT 通常使用：

for (int i = x; i <= n; i += i & -i)

如果：

x == 0

则：

i & -i == 0

循环永远无法前进。

因此树状数组通常要求下标从 $1$ 开始。

离散化之后也应映射到：

1,2,\dots,k

而不是从 $0$ 开始。

23. 哈希与字符串

23.1 字符串下标混用

C++ 字符串：

s[0]

是第一个字符。

如果其他算法习惯 1-based，可以：

s = " " + s;

但之后必须全程保持一致。

23.2 Rolling Hash 存在碰撞

单 Hash 本质上不是数学意义上的绝对正确。

高要求题目可能需要：

双 Hash；
更大的模数；
64 位自然溢出 Hash；
直接使用确定性算法，如 KMP、Z、SA 等。

如果题目要求严格正确，不要把概率正确当成必然正确。

23.3 `char` 的符号性与平台有关

char 可能是：

signed；
unsigned。

做字符数值运算时，不要依赖超出普通 ASCII 范围后的具体符号表现。

24. 输入输出：算法没超时，I/O 先超时

数据量大时：

ios::sync_with_stdio(false);
cin.tie(nullptr);

通常值得加。

如果使用了：

ios::sync_with_stdio(false);

就不要随意混用：

cin/cout

和：

scanf/printf

避免不可预期的缓冲顺序问题。

24.1 不要用 `endl` 当普通换行

endl

除了换行还会刷新缓冲区。

大量输出时可能显著拖慢程序。

普通换行优先：

'\n'

25. 读入字符和整行文本的坑

int n;
cin >> n;

string s;
getline(cin, s);

此时 getline 很可能读到前面残留的换行。

常见：

cin.ignore();
getline(cin, s);

如果输入格式更复杂，可使用：

cin.ignore(numeric_limits<streamsize>::max(), '\n');

26. 时间复杂度：不要只看最外层循环

26.1 两层循环不一定是 $O(n^2)$

例如双指针：

for (int r = 0; r < n; ++r) {
    while (...) ++l;
}

如果 l 总共只移动 $n$ 次，总复杂度可能是：

O(n)

26.2 一层循环也不一定是 $O(n)$

循环内部如果：

set
map
priority_queue

操作是：

O(\log n)

总复杂度可能是：

O(n\log n)

如果内部重新 DFS、排序、复制大数组，复杂度还可能更高。

26.3 `vector` 复制可能偷偷制造高复杂度

危险：

void dfs(int u, vector<int> path)

每次递归都复制整个 path。

如果只读：

const vector<int>& path

如果需要回溯，则通常传引用后：

push_back
dfs
pop_back

27. 空间复杂度：内存限制同样会爆零

例如：

int dp[10000][10000];

元素数量：

10^8

如果 int 为 4 字节，约占：

400\text{ MB}

还没算程序其他内存。

常见估算：

int：约 4 字节；
long long：约 8 字节；
double：约 8 字节；
char：约 1 字节。

注意：

vector<vector<int>>

还存在每个 vector 对象本身的额外开销和多次动态分配。

28. 大数组放哪里？

巨大的局部数组：

void solve() {
    int a[10000000];
}

通常放在栈上，很容易栈溢出。

更适合：

全局数组；
静态数组；
动态内存。

例如：

static int a[N];

或者：

vector<int> a(n);

29. 多测题最危险的不是算法，而是状态污染

每组数据结束之后重点检查：

head[] 是否重置；
edge counter 是否归零；
vector 是否 clear()；
vis[] 是否清空；
degree[] 是否清空；
DSU 是否重新初始化；
Trie/SAM 节点计数是否重置；
priority queue 是否为空；
DP 是否重新初始化；
答案变量是否归零；
时间戳技巧是否可能溢出；
静态局部变量是否残留。

30. 重边、自环、孤立点：出题人最喜欢的边界

图题提交前至少问一遍：

是否允许重边？

如果允许：

最短路通常可以自然处理；
邻接矩阵要取最小边；
桥算法必须正确区分边；
DSU 统计边数时要考虑重复；
MST 一般可以自然处理，但实现不能自行去重出错。

是否允许自环？

自环可能影响：

SCC；
环判断；
indegree；
二分图；
最短路；
拓扑排序。

是否存在孤立点？

不要只从：

号节点开始处理后就默认访问了整张图。

很多图算法需要：

for (int i = 1; i <= n; ++i)
    if (!vis[i])
        dfs(i);

31. 极端树形必须主动测试

树题至少自己构造：

一条链

1-2-3-4-5-...

测试：

递归深度；
最大树高；
LCA；
树 DP；
重链剖分。

一个菊花图

测试：

高度很小但度数很大；
邻接表；
子树统计；
DSU on tree；
合并逻辑。

单节点

n = 1

很多树算法会在这里暴露边界错误。

32. 极端数组也必须主动测试

至少考虑：

n = 1
全部相同
严格递增
严格递减
全 $0$
全负数
正负交替
一个巨大值，其余很小
最大值恰好在第一位
最大值恰好在最后一位

这些数据可以快速攻击：

双指针；
单调栈；
单调队列；
LIS；
前缀和；
贪心；
二分。

33. 答案初始化错误

求最大值：

long long ans = 0;

如果所有答案都可能是负数，就错了。

更合理：

long long ans = -INF;

求最小值同理。

不要根据“感觉答案应该非负”初始化，除非题意已经严格证明。

34. 贪心题：局部看起来合理不等于正确

贪心最危险的情况是：

样例和大量随机数据都能过，但没有证明。

写完贪心至少问：

贪心选择为什么不会破坏最优解？
能否通过交换论证证明？
能否构造一个局部选择正确、全局却失败的反例？
排序依据为什么是这个字段？
相等情况下 tie-break 是否影响答案？

特别注意：

sort

使用错误的第二关键字，可能只在少数数据上出错。

35. 二分答案：`check()` 必须真的单调

假设要找最小可行值：

不可行 不可行 不可行 可行 可行 可行

那么 check(x) 必须满足：

一旦某个 $x$ 可行，更大的 $x$ 全部可行。

如果这个性质无法证明，就不能二分答案。

这是“代码完全正确但算法整体错误”的高频来源。

36. 离散化：排序去重之后别忘了真正使用压缩值

标准：

sort(v.begin(), v.end());
v.erase(unique(v.begin(), v.end()), v.end());

int id = lower_bound(v.begin(), v.end(), x) - v.begin() + 1;

常见坑：

忘记 unique 后 erase；
BIT 需要从 $1$ 开始却忘了 +1；
压缩之后仍然拿原值当数组下标；
离散化只保留已有点，但题目还需要处理相邻区间长度。

37. 坐标压缩不等于把距离压成 1

例如真实坐标：

1, 100, 1000000

压缩成：

1, 2, 3

只能保证顺序关系。

如果题目涉及：

实际距离；
区间长度；
面积；
覆盖长度；

不能直接把坐标差理解为压缩后编号差。

38. 随机化算法：随机种子和碰撞风险

如果使用：

随机哈希；
Treap；
随机打乱；
Pollard Rho；
随机采样；

要注意：

固定种子是否可能被卡；
rand() 随机质量较差；
模运算是否溢出；
概率算法是否允许极小失败概率。

常见：

mt19937 rng(
    chrono::steady_clock::now().time_since_epoch().count()
);

但如果题目需要可复现 Debug，可以暂时固定 seed。

39. 文件输入输出：NOI 场景尤其要检查

某些传统赛制要求：

freopen("xxx.in", "r", stdin);
freopen("xxx.out", "w", stdout);

最大风险不是不会写，而是：

文件名写错；
大小写错误；
题目要求标准输入输出却保留了本地 freopen；
本地调试文件路径被提交；
输出文件名和题目要求不一致。

提交前必须重新核对比赛规则。

40. Debug 输出是经典爆零原因

例如：

cout << "debug " << x << '\n';

算法全部正确，也可以直接因为输出格式错误变成 $0$ 分。

提交前搜索：

debug
cerr
printf
cout

确认所有临时输出都已删除。

cerr 虽然通常不参与标准输出判题，但大量 cerr 仍可能拖慢程序。

41. 输出格式也能让正确答案变 0 分

重点检查：

是否多输出解释文字；
是否漏空格；
是否多一个数字；
是否要求每个答案换行；
是否要求固定小数位数；
YES/NO 大小写；
Impossible 等特殊字符串；
浮点误差要求；
多组答案之间是否需要换行。

例如：

cout << fixed << setprecision(10) << ans << '\n';

42. `INF` 不是越大越好

很多人喜欢：

const long long INF = 1e18;

甚至：

LLONG_MAX

但如果后续执行：

INF + w

就可能溢出。

原则：

INF 只需要严格大于所有合法答案，并给后续运算留下空间。

例如合法答案最大约 $10^{15}$ ，使用：

4e18

并不一定更安全。

选择一个与实际范围匹配、又不会在计算中溢出的值。

43. 宏定义可能制造难以发现的问题

例如：

#define int long long

虽然竞赛中有人使用，但它会改变大量代码语义：

main；
STL 模板参数；
函数重载；
内存占用；
与第三方/标准 API 的类型匹配。

更推荐明确使用：

using i64 = long long;

或者：

using ll = long long;

需要 64 位时显式写。

44. `min` / `max` 与类型混用

例如：

long long x;
int y;

auto z = max(x, y);

模板类型可能无法直接推导一致。

最好显式统一类型：

max(x, 1LL * y)

同理：

min
clamp
accumulate

都要留意类型。

45. `accumulate` 的初始值决定计算类型

非常经典：

vector<long long> a;
long long sum = accumulate(a.begin(), a.end(), 0);

初始值 0 是 int，因此累加过程可能按 int 进行。

正确：

long long sum = accumulate(a.begin(), a.end(), 0LL);

46. `std::gcd`、除法和符号

整数除法：

a / b

是向 $0$ 截断。

它不一定等于数学上的 floor。

例如：

-3 / 2

在 C++ 中结果为：

-1

数学下取整却是：

\left\lfloor-\frac32\right\rfloor=-2

如果题目涉及带负数的整除、floor division、ceil division，必须单独处理。

47. 上取整除法不要无脑写 `(a+b-1)/b`

对于正整数：

\left\lceil\frac ab\right\rceil = \frac{a+b-1}{b}

是常见写法。

但：

a + b - 1

本身可能溢出。

可以根据范围考虑：

a / b + (a % b != 0)

前提仍然是 $a,b>0$ 。

带负数时需要重新定义和实现。

48. 乘法比较时不要先乘

例如判断：

\frac ab < \frac cd

直接：

a * d < c * b

可能溢出。

如果数据达到 $10^{18}$ ，可以考虑：

(__int128)a * d < (__int128)c * b

同理，比较平方：

x * x < y

也要检查乘法范围。

49. `sqrt`、平方数与精度

判断一个 64 位整数是否为完全平方数，不要仅仅：

long long x = sqrt(n);
return x * x == n;

因为浮点舍入可能使结果偏差 $1$ 。

更稳妥：

long long x = sqrtl((long double)n);

while ((__int128)x * x < n) ++x;
while ((__int128)x * x > n) --x;

return (__int128)x * x == n;

50. 时间戳优化：快，但可能留下隐藏状态

为了避免每组测试清空大数组，常使用：

vis[x] = timer;

表示当前轮访问。

这种方法很好，但要注意：

timer 是否可能溢出；
某个数组是否忘记换成时间戳判断；
不同逻辑是否错误共用同一个时间戳。

51. 对拍：防止“我觉得算法对了”

对于可以写暴力的小规模问题，最强的 Debug 手段之一就是对拍。

准备：

brute.cpp：保证正确的暴力；
std.cpp：待验证算法；
gen.cpp：随机生成小数据；
循环运行并比较输出。

重点不是生成大数据，而是：

大量生成能够被暴力验证的小数据。

随机数据之外，还应主动加入：

全相等；
极端值；
链；
星形图；
重边；
自环；
单元素；
最大/最小边界。

52. Sanitizer：本地抓越界和 UB 的利器

本地调试时可以考虑：

-fsanitize=address,undefined

例如：

g++ main.cpp -std=c++17 -O1 -g \
    -fsanitize=address,undefined \
    -fno-omit-frame-pointer

它可以帮助发现：

数组越界；
use-after-free；
部分整数 UB；
非法移位；
空指针访问等。

但正式提交前一般应按照比赛要求恢复正常编译选项。

53. Debug 模式和提交模式最好分开

可以使用：

#ifdef LOCAL
#define debug(x) cerr << #x << " = " << x << '\n'
#else
#define debug(x)
#endif

本地：

g++ main.cpp -DLOCAL

评测时不定义 LOCAL。

这样比手工删除大量 Debug 输出可靠。

54. 样例通过之后，至少再测这几类数据

最小数据

例如：

n = 1
m = 0

最大数据

测试：

时间；
内存；
递归栈；
整数范围。

极端结构

链；
星形；
全相同；
单调；
完全图；
空图。

极端数值

$0$ ；
$1$ ；
最大允许值；
负数；
long long 临界量级。

特殊关系

重边；
自环；
相等元素；
重复查询；
区间长度为 $1$ ；
查询整个范围；
查询最左/最右边界。

55. 一眼看到就应该警觉的代码

看到：

a * b

问：

会不会溢出？

看到：

1 << k

问：

k 会不会超过 30？是不是应该 1LL？

看到：

dfs(...)

问：

最大递归深度是多少？

看到：

int ans

问：

答案最大是多少？

看到：

a[i]

问：

i 的合法范围究竟是什么？

看到：

memset

问：

我到底是在按字节填什么？

看到：

sort(..., cmp)

问：

cmp(x,x) 是否一定为 false？

看到：

while (...)

问：

每次循环是否保证状态向终止条件推进？

看到：

map[x]

问：

我真的想插入这个 key 吗？

看到：

INF + x

问：

会不会溢出？

看到：

vector` 的引用或 iterator

问：

中间有没有可能发生扩容或 erase？

56. 提交前 2 分钟爆零检查清单

A. 数据范围

[ ] 所有乘法都检查过中间值范围
[ ] 前缀和、距离、DP、答案是否需要 long long
[ ] 1 << k 是否应该写成 1LL << k
[ ] INF 参与加减时不会溢出
[ ] 需要时使用 __int128
[ ] accumulate 初始值是否用了正确类型

B. 下标与数组

[ ] 0-based / 1-based 全程一致
[ ] 所有数组大小都覆盖最大合法下标
[ ] 线段树是否至少按 4*n 量级预留
[ ] 无向图是否按 $2m$ 存边
[ ] Trie / SAM / 可持久化数据结构按最大节点数开空间
[ ] 是否存在 i <= n 导致访问 a[n] 的问题

C. 初始化

[ ] 局部变量都初始化
[ ] 多组数据的所有状态都清空
[ ] vis / head / degree / dp / tag 无残留
[ ] memset 没有被当成普通整数赋值使用
[ ] 最大值答案没有错误初始化为 $0$

D. 图与树

[ ] 无向边添加双向
[ ] 是否允许重边
[ ] 是否允许自环
[ ] 是否存在孤立点
[ ] DFS 是否可能栈溢出
[ ] Dijkstra 中不存在负权
[ ] LCA 的 LOG 足够
[ ] 桥/割点是否正确处理父边和重边

E. DP / 数据结构

[ ] DP 状态定义明确
[ ] 初始状态与不可达状态正确
[ ] 01 背包 / 完全背包循环方向正确
[ ] 线段树区间长度是 r-l+1
[ ] lazy 标记组合顺序正确
[ ] BIT 下标不会出现 $0$
[ ] 离散化完成排序、去重和正确映射

F. STL / C++

[ ] sort 比较器没有使用非法的 <=
[ ] map[x] 不会无意插入元素
[ ] priority_queue 大根堆/小根堆方向正确
[ ] lower_bound / upper_bound 使用正确
[ ] erase / push_back 后没有继续使用失效 iterator/reference
[ ] 没有危险的 signed/unsigned 混算

G. 输入输出

[ ] 删除全部 Debug 输出
[ ] freopen 与比赛要求一致
[ ] 文件名完全正确
[ ] 输出格式、换行、大小写正确
[ ] 大量输出没有滥用 endl
[ ] getline 前没有残留换行问题

H. 极端测试

[ ] $n=1$
[ ] 最大 $n$
[ ] 全相同
[ ] 严格递增
[ ] 严格递减
[ ] 全 $0$
[ ] 最大权值
[ ] 链
[ ] 星形图
[ ] 重边
[ ] 自环
[ ] 查询最左/最右边界
[ ] 区间长度为 $1$

57. 比赛中的错误排查顺序

当程序出现 WA 时，不要漫无目的看代码。

推荐按照下面顺序排查。

第一步：重新检查题意

问：

是否漏掉隐藏条件？
是否错误认为元素互异？
是否错误认为图连通？
是否错误认为没有重边/自环？
是否错误认为所有数都是正数？
是否错误理解“至多”“恰好”“至少”？

第二步：验证算法性质

检查：

贪心是否有证明；
二分条件是否单调；
DP 状态是否覆盖全部情况；
图算法的适用条件是否满足；
数据结构维护的不变量是否成立。

第三步：检查范围

重点搜索：

int
*
+
<<
INF
abs
accumulate

重新估计中间值上界。

第四步：检查边界

重点测试：

n = 1
l = r
l = 1
r = n
空集合
只有一条边
只有一个节点

第五步：检查初始化与多测污染

特别是：

vis
dp
head
cnt
tag
vector
queue
priority_queue

第六步：对拍

如果仍然找不到：

写暴力，让电脑帮你构造反例。

对于大量算法题，这比继续肉眼检查高效得多。

58. RE 的排查顺序

如果出现 Runtime Error，优先怀疑：

数组越界；
递归栈溢出；
空指针 / 非法 iterator；
除以 $0$ ；
BIT 中 x = 0 导致死循环；
图或 Trie 节点数量超过预估；
vector 引用失效；
内存超限导致异常；
非法移位；
未定义行为。

本地优先开启 AddressSanitizer / UBSan。

59. TLE 的排查顺序

不要第一反应就是：

换快读。

先检查：

算法复杂度是否正确；
某个循环是否退化；
map/set 是否被放进高频核心循环；
是否重复排序；
DFS 是否重复访问；
Dijkstra 是否存在大量过期状态；
是否频繁复制 vector/string；
是否使用 endl；
是否无意构造 $O(n^2)$ 数据；
最后再考虑 I/O 常数优化。

60. MLE 的排查顺序

估算：

\text{内存} \approx \text{元素数量}\times\text{单元素字节数}