警示后人

Shellchen · 2025-10-25 15:39:25 · 算法·理论

CSP-J/S 要来了，考前警示一下后人！

综合

多测记得清空。
开 long long。
注意开了 long long 时，printf 的格式符要用 %lld。同理，double 也要 %lf。
用 cin/cout 时一定要 ios::sync_with_stdio(0)，否则很慢！调代码的时候建议删掉，但最终代码一定要有。注意加了之后输入输出只能用 cin 和 cout。
好好检查 freopen 是否写错。
ios::sync_with_stdio(0) 时不要写 fclose。
不要出现拼写错误。如 itn main()，int mian()。
万能头是 bits/stdc++.h！不要打成 bits\stdc++.h！Windows 下这样没有问题，但是 Linux 下会 CE。最好把所有代码放 Linux 下跑一下样例。
同理，有一些其它变量名也是只有 Linux 下会 CE，如 kill。
引用了 cmath 头文件时不能定义全局变量 j0，j1，y0，y1！特别是 y1，每年都有无数人中枪！
还有，next，time，pipe，log，pow10 也不能做全局变量名！一个很好的解决方法：只用英文单词的辅音字母，或者干脆中文拼音。
#define 一定要加括号！如 #define f(x) x*x 之后，f(2)+f(2) 会展开成 2*2+2*2，f(1+1) 会展开成 1+1*1+1。正确的写法是 #define f(x) ((x)*(x))。
不要 abs(__int128)。
int 左移超过 31，long long 左移超过 63 都是 UB。
最后，算清复杂度，别瞎写超时了。

DP
转移时记得取模，模数不要写错。
如果需要，记得 memset 整个数组为正无穷或负无穷。不要漏写或写错边界条件。memset 成负无穷时注意不要 0xcf，建议 -0x3f（当然 0xc0 也是对的）。
想清楚转移方程是否正确，最好证出来，证不出来也要拍出来。
如果想到了复杂度并不正确的 DP，不要放弃这个思路，也许可以优化。
树形 DP 有时要特判叶子节点。
算好空间。一般来说，滚动数组能开就开，压维能压就压。
记得特判无解。

数据结构
空间要开够。线段树 4 倍空间，主席树 Q \log N。
注意不要 pushup 或者 pushdown 叶子节点。
标记下传记得处理多个标记叠加。
max 和 min 不要 #define。

为什么我要选择在这里说这个？因为数据结构里面这个错误被坑的最惨。在 #define 时，如果传入的两个参数是函数，那么会发现，所有函数都被调用了两次。

比如下面的代码你会发现被卡到了 O(n)。
```
#define max(x,y) ((x)>(y)?(x):(y))
int query(int u,int l,int r)
{
if(l>tr[u].l||r<tr[u].r) return -2147483647;
if(tr[u].l>=l&&tr[u].r<=r) return tr[u].sum;
int m=(tr[u].l+tr[u].r)/2;
pushdown(u);
return max(query(u*2,l,r),query(u*2+1,l,r));
}
```
事实上，max 和 min 你都不需要手写，自带的已经可以了，手写卡常效果也并不明显。
ST 表要预处理 log。
还有并查集要注意合并的是祖先而不是结点本身。

错误：
```
fa[x]=y;
```
正确：
```
fa[find(x)]=find(y);
```
图论
看清有向图无向图。
无向图空间要开够。
建虚点的话，点权数组空间也要开够。
最短路注意有没有负边权，有的话要用 SPFA。记得判负环。
注意最短路初始化距离数组为正无穷。
欧拉路要特判回路。
Floyd 三层循环顺序是 k，i，j。
拓扑排序需要满足是有向无环图。
网络流记得建反边，正反边要挨在一起建，反边边权为 0。最小割不能割掉的边边权为正无穷。
树上 DFS 记得不要从儿子 DFS 回父亲。
树剖链修改或链查询记得是 if(dep[top[x]]<dep[top[y]]) swap(x,y); 而不是 if(dep[x]<dep[y]) swap(x,y)。

字符串
Trie 空间要开够。
KMP 求 border 时要注意，border 降到 0 的时候就不要再向后找了，否则会死循环。
后缀排序注意不要数组越界。

数学
组合数学中求 C^m_n 要特判 n<m 返回 0。
预处理阶乘算组合数时要注意 0!=1。
矩阵乘法要检查好递推式再写。
中国剩余定理要求所有模数互质。如果不互质请使用扩展中国剩余定理。
快速幂如果模数平方爆 long long 要写快速乘法。注意此时快速幂复杂度为 O(\log^2 n)。

STL
定义超过 3 \times 10^5 个 queue/stack/deque 基本上一定会爆空间。
map 常数很大，一般来说数据规模到 10^6 就可以放弃了。
bitset 在卡常时建议手写。
vector 的 insert 和 erase 可能会被卡到 O(n)。
map 系列和 set 系列是 O(\log n) 的。特别地，别用 unordered_map，会被卡。
map 判断是否存了一个数的时候要用 mp.count(x)，而不是 mp[x]（因为可能存了 0 你却当没有）。
set 中 lower_bound 要用 s.lower_bound(x)。upper_bound 同理。

还有 set 重载小于号的时候要写上所有关键字。去重的标准是 !(a<b||b<a)。

错误：

struct node
{
int fi,se;
};
bool operator<(node x,node y)
{
return x.fi<y.fi;
}

正确：

struct node
{
int fi,se;
};
bool operator<(node x,node y)
{
return x.fi!=y.fi?x.fi<y.fi:x.se<y.se;
}

multiset 删一个用 s.erase(s.find(x))，删全部用 s.erase(x)。
还有：打暴力时不要测大样例时让 STL 容器里面太多东西，否则电脑极有可能会蓝屏。~~别问我怎么知道的。~~

还有最后一项很重要的：

别冒险打暴戾语言，小心禁赛。

最后，祝大家 CSP-J/S 2025 RP+=INF！

警示后人

综合

DP

数据结构

图论

字符串

数学

STL