常规检查项

非完全原创。

调试方法😎😎

在编译选项中添加 -Wall -Wextra 可以避免大部分 UB。
在写之前先在纸上/代码结束后的注释里写好思路，在出现错误时先检查思路是否有误再检查代码逻辑是否与思路不同。
用 assert(...) 来判定一些不应该出现的情况。
如果只是在小样例卡住了，可以手玩一些关键信息然后二分出现错误的位置。
- 找到出现错误的变量/表达式后，追踪它的变化，找出使得它错误的表达式，然后分析这个表达式的问题。
- 如果发现这个表达式错误是因为其他变量错误，继续追踪它的变化，直到找到基层错误。
如果大样例卡住了，先不要急着对拍，先进行例行检查，确定没有明显的脑车错误再写对拍。
- 调试用对拍的数据范围以可以手玩为佳。与检查正确性对拍不同，后者是往暴力的最大数据范围怼。
对拍之前手搓一些极限数据/Corner Case，这些极限数据往往能说明问题。
即使已经发现了问题也只需要把调试代码注释不要删掉，因为您不知道还需不需要用。

File Error🤡🤡🤡🤡🤬🤬🤬🤬😭😭😭😭➡️💀💀💀💀

您的题目名称/freopen真的拼对了吗？我的意思是，真的按照 pdf 上的拼了吗？（考试的题目名称是故意拼错的常用英文单词）
//freopen
请在考试结束前至少 5mins 删除收取目录内的其他所有文件与子目录。
- 但是不要在 Linux 下删文件，一不小心误删代码 Windows 还能从回收站救回来
不要告诉我建了新的子目录然后在里面写代码。代码必须存在 D:\<考试名称> 下。
special trick：一般而言下发文件中每个样例的题目名称是不会拼错的，可以用它们的名称复制过去。

Presentation Error 🤡🤡🤡😅😅😅

有些题要求两个数字之间用逗号分隔，但是最后那个元素后面没有。
有些题要求多组测试点之间输出一个空行。
CF 上很多题可以用各种奇怪的姿势输出 Yes，但是正式考试不行
如果您是快输选手，请务必记得输出数字之间的空格/空行。（鞭尸 @constexpr）

CE 🤣👉🤡😅😅😅

请学会在 NOI Linux 下生活。
对着编译信息一条一条看。
- 弹出来一大堆奇怪的东西不要慌，多半是用 STL 出锅了
-std=c++14？
- 题目里没有 -std=c++14 则默认 -std=c++17 不必惊慌
您是不是变量重名了？
y1,time,size,count
int a[1e5];
int a[100005][100005];
- 这种情况一般会报错。
一些 STL 容器需要重载运算符才能使用。unordered_map 需要手写哈希函数。
std::max/min 的两个参数类型应当相同。
main 的返回值是 int。
如果要把题目里所有的 int 替换成 long long，且直接使用了 Ctrl+F 的“替换所有匹配项”，小心您的 printf 等函数。
freopeb,scnaf
所有代码一旦有改动就必须再次编译。

RE😡

general

scanf("%d",a);
(...)/0,(...)%0
vector<int> a(10);for(int i=1;i<=10;++i)printf("%d\n",a[i]);

不同数组有不同的大小

// Limits:n<=1e5,a[i]<=1e6
const int M=1e5+5;
int buc[M],a[M],n;

int main(){
    scanf("%d",&n);
    for(int i=1;i<=n;++i)scanf("%d",&a[i]),buc[a[i]]++;
    (...)
}
/*
input:
3
114514 191981 233333
output:
(RE)
*/

您内外层循环变量混了吗。

for(int i=1;i<=n;++i){
    for(int j=1;j<=n;++i/*<-😅*/){
        (...)
    }
}
for(int i=1;i<=n;++i){
    for(int j=1;i<=n/*<-😅*/;++j){
        (...)
    }
}

宏运算顺序。

#define M 100000+5

int a[M*20];  // 100000+5*20 <-😅

/*
expected:a[2000100]
actually:a[100100] 
*/

您递归判边界了吗。
vector 扩容会导致引用与迭代器失效

data structure

您的线段树开四倍了吗。
您的线段树/平衡树访问到结点了吗。
您输出树的时候判了吗。
您的 ST 表边界写错了吗。
您的 ST 表两维写反了吗。
您的分块判最后那个不完整块了吗。

graph&tree

您无向图判回边了吗。
您无向图数组开两倍了吗。
您 LCA 的数组没开够/写反了吗。
您的 vis 用过吗。

math

您线性筛过嘛。
您线性筛判 j<=ptot&&i*prime[j]<M 了嘛。

DP

您能确保不会访问到极大/负下标吗。

TLE😒

卡死形🤡

小数据都完全跑不了的类型。

general

getchar 很蠢，读到 EOF 的时候会卡死。
您是不是又把循环变量搞混了。
您是不是又分不清二分的两种形式了。
const int /*<-😅*/ EPS=1e-5;
如果有 while(1)，那您写 break; 或者 return 了吗。
for(int i=n;i>0;++i /*<-😅*/);
您是不是改了些不该改的东西
交互题清缓冲区了吗？

data structure

有些非递归写法的数据结构也可能出现访问的情况。
BIT 绝对不能用这个下标。

graph

for(int i=head[u];i;i=next[u/*<-😅*/]);

不是卡死形😅

这种一般数据大的时候才会出事。

general

您关 cin/cout 同步流了吗。
不限多少组数据只限，但是每次都 memset 清空
检查一下代码会不会在某些极端情况下被卡到很高的复杂度。（典例：菊花图）
某些库函数/容器效率堪忧。（如：std::list）
__int128 和 long double 很慢。
您的 unordered_map 是不是被卡了。
除法与取模的运算时间是乘法的 10 到 20 倍，因此尽量以加减乘代替除模。
- 不得已不要在排序的 cmp 函数里写除号（典例：莫队）

data structure

同等数据规模运行时间比较，如果常数卡的紧请不要使用后面的数据结构/算法：
- 并查集（满优化） < 堆（std::priority_queue） < BIT < 堆式线段树（无标记下传）< 堆式线段树（有标记下传） < 动态线段树 < 红黑树（std::set/map/__gnu_pbds::tree）< 旋转 Treap < Splay < FHQ-Treap < （LCT）
  - 因此以后比不带标记下传线段树复杂的数据结构都别用了。
  - 以后平衡树也别用了。
  - 以及：std::priority_queue 真的不慢，都跑不了的，可能比您手写的快
- 不带修时：ST 表 < 猫树 < 线段树
  - 不带修的 RMQ，别再写线段树了，写 ST 表吧，你的 ST 表水平已经不像原来那样糟糕了！———— 某 cdqz 国集爷
说到并查集，您并查集/左偏树路径压缩了吗。

graph&tree

vector 存图在点数很多的菊花图上很慢。
您的 vis 真的用过吗。
您的 Dijkstra 是大根堆吗。
您的 SPFA 被卡了吗，老老实实写 Dijkstra 吧。
稠密图上很多算法不见得比暴力快。
网络流和欧拉回路记得加当前弧优化（for(int &i=cur[u];i;i=next[i]);），但是不要忘了 cur 的初值。
费用流是伪多项式算法，值域大慎用；zkw 费用流在有零环时约等于爆搜，不要用。
网络流的时间复杂度是玄学没必要按照硬算，但是请不要在的时候跑除了二分图匹配以外的任何网络流
- 复杂的流模型一般只会开
LCA 实际运行时间比较：树链剖分 < DFS 序 LCA < 欧拉序 LCA（四毛子） < 倍增 LCA
- 树剖跑得最快，DFS 序折中，倍增 LCA 最短
树链剖分 < LCT
- 相信我，您考场上写不出 LCT 的

DP

您确定您写的不是爆搜。您的记忆化真的用过吗。
某些 DP 对于不同的第一维，第二维长度不定但是和一定，同上不能 memset/memcpy。

MLE🤯

general

-ulimit -m 524288 限制空间为 512MB
请注意某些题的（逆天）空间限制再想用什么算法
在空间非常紧时，#include<bits/stdc++.h> 占用约 5MB 空间。
慎用 #define int long long。
你说得对，但是我们这个 deque 码量小方便写，写一个放内存池里变答辩糕，怎么用都用不坏，用来写 NOI2022 D1T1 都是很好用的。
- 双向队列请使用 list 喵。
有时候 MLE 是因为 RE。

data structure

可持久化数据结构和动态线段树的空间都是的。
线段树合并有两种，在空间紧的时候请使用不那么耗空间的那一种。
可持久化线段树/平衡树要定期重构。

graph

您 BFS 队列里的点会不会过多？

WA🤔

UB🤬

如果代码多次运行结果不同或者加了/不加 -O2 运行结果不同请立即检查孩子代码里有没有这些东西，如果有立即删除并下载原神

数组越界可能不 RE🤬🤬🤬🤬🤬
有符号数据类型的溢出
++x++;
一句话里出现多于一个 read（如 G[read()].push_back(read());）
变量未初始化就用

typical😅

下面是所有人 99% 会犯的一些错误。

多测交换两组数据后结果不同：多测不清空，爆零两行泪。
好端端的正数运算出现了负数：十年 OI 一场空，不开 long long 见祖宗。
- 在对乘法取模运算时必须在前面乘上 1ll 再乘法取模，对负数取模时要先加模数。
- 请务必算好每个变量要开什么类型。
您删调试了吗？
您删调试的时候是不是顺便又把输出答案删了？
对取模/无解输出 No Solotion。
1<<40
您的最小值初值是否够大？最大值初值是否够小？
- 对一些负数取最大值时给我来了个 int maxn=0。
您的 inf 是否够大？是否加起来会溢出？
- 好的最大值：0x3f3f3f3f,1e18(for long long)
- 不好的最大值：2147483647
您真的了解位运算的运算顺序吗？
您变量重名了吗？
您判无解了吗？
您的 double 精度真的够吗？
您真的改了 Ctrl+C 的部分吗？
您定义了一个函数/变量，然后从来没调用过（如：预处理，建树，dfs）

general

您定义了两个类似的函数，然后您把它们的用处搞混了（典例：树剖的两个 dfs，然后在 dfs2 调用了 dfs1）
强制在线时，只有第一行错误的地方才是有用的。
该传引用的地方传了吗？
two-pointer 分清楚维护的是最后合法的一项还是第一个不合法的项。

data structure

BIT

您维护的是前缀还是后缀？
如果拿来做区间问题，您维护的信息可减吗？

SGT/BBST

您维护的东西有结合律和分配律吗？
您建树了吗？
您访问结点之前 pushdown 了吗？
您进行修改操作之后 pushup 了吗？
tag 是可叠加的。
您下放 tag 的顺序正确吗？
您下放完 tag 之后清空了吗？
如果做区间推平，您的 tag 是不是一个保证不会出现的值吗？
如果做子串问题，题目允不允许有空串？
（对于 FHQ-Treap）您 split 的时候递归到右子树改左子树大小没有？

Sparse Table

您维护的信息是可重的吗？题目真的不带修吗？
lg[1]=1 <- 😅😅😅
extra：__lg 远优于预处理

单调数组

题目要求的是严格大小关系还是非严格大小关系？
您判空数组了吗？

分块

您重构块的时候下放标记了吗？
您算答案的时候把标记也算上了吗？

Other

扫描线：您对询问排序了吗？

graph

生成树

您对边权排序了吗？
您的并查集用了吗？

最短路

Dijkstra 判没判已经确定最短路的点不能继续拿去更新？
SPFA 有没有及时更新 vis 数组？
Floyd 的转移顺序？
Johnson 是怎么重新赋权的？

Tarjan

请注意三种 Tarjan 的细微差别。
边双 Tarjan 如果可以走回边最后判新的边双不能用 dfn[u]==low[u]，改为 dfn[u]>=low[u]
访问过 和 在栈里 不是同一个东西，前者可以用 dfn 兼一下，后者要单独开

flow

您 Dinic 加当前弧优化了吗。
您的边是从 2 开始存的吗。

tree

general

请不要把 DFS 序和编号搞混喵。
请不要把中心和重心搞混喵。
请搞清楚是边权还是点权。

LCA

倍增 LCA 判跳到同一深度后结点相同了吗。
DFS 序求 LCA ST 表里存的是父亲。

树上差分

您维护的信息有可减性吗？
搞清楚是在向上差分还是向下差分。

树链剖分

请不要把两次 DFS 搞混喵。

树上滴塑

统计重儿子的答案不清空。

math

exgcd 交换了吗。
搞清楚在解同余方程还是二元一次不定方程。
不会有人在模数不是质数的时候用费马小定理求逆元吧。
不是质数喵。

有人的线性筛 be like：

void gpr(int n){
    vis[1]=1;
    for(int i=2;i<=n;++i){
        if(!vis[i])pr[++pt]=i;
        for(int j=1;j<=pt&&i*pr[j]<=n;++j){
            vis[i*pr[j]]=1;
            if(i%pr[j]==0)return;//<-😅😅
        }
    }
}

counting

模数小吗？如果小，用 Lucas 定理了吗？
不会有人在取模的情况下进行除法吧。
求组合数判 if(n<0||m<0||n<m)return 0; 了吗？
容斥系数？

DP

是否设置了初始 DP 值和边界值？
- 如果条件允许，要多设置边界值。
如果滚动数组/树形背包，是否保证两个数组中只有一个会被修改？最后有没有把答案粘回去？
状压 DP 左移右移几位？