警钟撅烂

· · 个人记录

latest upd at 2025/11/15

（哪天重构一下……分个类，咕咕）

某些【】错误真的一犯再犯，我真的服了我自己了

（括号表示犯错的次数）

  1. （*n？）不看数据范围瞎写 N 变量！！！！！！！经常 10^6 爆我的初始值 N=514514！！
  2. （*3）数论、排列组合什么的两个 int 相乘不乘 1ll！！！！！！！！
for(int i=2;i<n;i++)printf("%lld\n",**1ll** *inv(i)*(i-1)%n);
--------------------------------------------------------------------------------------
(ans+=**1ll** *j*C(n,j)%mod*qpow(i-1,n-j))%=mod;
//ans 是 ll 类型但前面那个1ll仍然有必要加上，因为前面两个相乘的数都是int。
  1. （*n）运算符优先级，位运算优先级低于比较运算！打括号！！！
if(j&1==0)//... //(j&1)==0
--------------------------------------------------------------------------------------
int cdiv(int a,int b){return a/b+(a^**b>0**&&a%b);}//(a^b)>0
  1. （*n + 2）复制代码一定要多看几遍！！！！！！！！
if(T[cur].modi){
    T[T[cur].lc].modify(T[cur].mody);
    T[T[cur].**l**c].modify(T[cur].mody);
    T[cur].modi=0;
}
--------------------------------------------------------------------------------------
void **reverse**(int cur){
    //...
    if(mid>=l)**modify**(T[cur].lc);
    if(mid<r)**modify**(T[cur].rc);
    return pushup(cur);
}
--------------------------------------------------------------------------------------
void dfs2(...){
    //...
    dfs1(...), dfs1(...);
}

注：线段树等类似操作可以复制，但是一定要看有没有递归，递归的函数名对不对！（如上两个教训）

  1. （*2？）bitset 从 0 开始枚举下标！！！！！！！！
for(int k=/*1*/0;k<32;k++)if(s[k])//...
  1. bool major() 不要返回一个非布尔值答案，不然就会像这样：
while(T--)ans+=major(4-T-1);

**bool** major(int T){
    //...
    return max(dp[n][mid],sum-dp[n][mid]);
}
  1. 纯属脑瘫
if(chk(mid))r=mid;
else r=mid;
  1. （*2）线段树不要想着尾递归。不然就会这样。
void modify(itn cur,int tar,int v){
    //...
    if(mid>=tar)/*return */modify(T[cur].lc,tar,v);
    else /*return */modify(T[cur].rc,tar,v);
    pushup(cur);
}
  1. （*3）01 背包如果体积是负数那么枚举转移时不要用 M+v[i]，应该从 M 枚举然后里面加个判断。就像这样：
for(int i=1;i<=n;i++){
    // for(int S=M-1-d[i].x;S>-M;S--)//d[i].x可以是负数，这样会越界
    for(int S=M-1;S>-M;S--)
        if(S+d[i].x<M&&S+d[i].x>-M)
            //...

  1. （*2）cout 一个过大的浮点数导致输出保留 7 位有效数字（科学计数法输出）从而精度不够 经典例子

  2. 见祖宗的非常规方式

    ll dis[N];//long long
priority_queue<pii,vpii,greater<pii>> Q;//int
void dijkstra();

    全开 ll 有时候也会见祖宗。比如下例，只需要判断符号的话写一个 sgn 函数，直接乘可能会爆！

    ll fn = n * 2 - ln + 1, fm = m * 2 - lm + 1;
if((fn > 0 ? 1 : (fn == 0 ? 0 : -1)) * fm /*>=*/<= 0) break;
//tm我是说为什么一到long long范围就wa，原来这里乘起来爆ll了
//（原来写的是 if(fn * fm <= 0)）

  3. lower_bound 等函数先判是否存在元素再判断！错误示例：（CF1747D）

    if(*(mp[][].lower_bound(l)) <= r) return 2;

  4. （*2）inv[]数组不要直接拿来用！这可是阶乘的逆元而不是简简单单的你所想的逆元！！！

  5. 多测中途 return puts("-1") 结果忘了清空某些东西（本来应该在程序末尾清空）。比如P8471。

  6. 迷宫 bfs 最开始的点忘了把 best 设成 0。（

  8. 日常sb：

    for(int j = 1; j <= cnt[i]; /*i++*/j++)

    关键这里 i 的改变让 j 的约束发生了变化所以没有死循环，更难发现了 qwq

  9. （*2）不要看到 T[u].lc 总想在前面加个 ~ 号。动态开点的条件是 if(T[u].lc == -1) 而不是 if(~T[u].lc)。

  10. （*3）浮点误差（精度）\epsilon 最好设为 10^{-6}\sim10^{-12}（推荐 10^{-8}），设置过大（比如 10^{-5}）可能会 wa。（设置过小如 10^{-10} 可能也会因为精度问题挂掉或者造成浮点二分死循环）

  11. dfs 要用临时数组时记得每个深度分开放，否则可能会出现深度大覆盖深度小的数组的情况/kel 例子。

  12. 多测未清空的神作：scanf 一个字符串，但是在这个 scanf 进来的字符串末尾添加了几个字符时忘了及时添加 \0 导致和后面 scanf 没有覆盖的部分的字符串连了起来。例子。

  13. 线段树懒标记一定要记得初始化！！！没有 warning 给你的！

  14. 不要 dx[i] 写习惯了！有时候 (i, j) 是坐标用 k 循环还写 dx[i]！（调了一下午）

    for(int k = 0; k < 4; k++) {
int px = i + dx[/*i*/k], py = j + dy[/*i*/k];
//...
}

  15. （*2）线段树维护一个区间的最大最小值的时候，遇到区间变相反数的操作，除了 mx *= -1, mn *= -1 以外 还要 swap(mx, mn)！！！

  16. 有时候单点修改也要更新懒标记！因为有时候双标记更新，一个标记会影响另一个标记或者是维护的值

  17. 担心浮点数比较的浮点精度的话，如果输入是整数，可以考虑化除为乘。

  18. (*0) p << 1ll，如果 p 是 int，那么结果还是 int！

  19. 质因数分解不要忘了最后 if(n != 1)！！！1

  20. 特判特殊情况的时候不要忘了在最后面加 return！！e.g.

  21. （*2）看 warning！！！ 不要因为是 shadow 就不看了，就有 baka 把主函数里写个 int 导致全局变量没赋值导致答案少了一部分

  22. n行m列方格，每个方格可以填l到r的数，每个方格相互独立，问有多少种填法？

    我：(nm)^(r-l+1)

    然后光荣收获 wa on 3/cf

    （应该是 (r-l+1)^(nm)）

  23. 0xbf 初始化 int 是 -1077952577，两个加在一起会爆。下次记得用 0xcf 或者啥的/fn

  24. 多测不清空：dsu 或者什么数据结构维护一个东西的时候 init 不写全导致的。e.g.（点 compare）。

  25. （*3）不要忘记在主函数里建线段树、dfs1 dfs2 啥的。

  26. 5 >> 32 是 ub。见 https://www.luogu.com.cn/discuss/694259。

    任何情况下，如果右操作数的值为负或大于等于提升后左操作数中的位数，那么行为未定义。

同时注意，对于负 a，尽量不要使用 a << b 和 a >> b（前者在 c++20 前为 ub）。

  1. 01bfs 不能像平时写 bfs 那样搜到一个点就直接标记 vis，应该像 dijkstra 一样记录最优解，否则 1 边可能会 ban 掉 0 边。

  2. 01bfs 不要写成全在队尾 push 了/cf。

  3. 线段树 build 有时需要 pushup。

  4. memset(head + 1, -1, n << 2);
n = read();

  5. （*2）memset 或 dp 转移的时候的 memcpy 使用过程中注意类型，如果是 long long 那么 size 需要写 len << 3。

  6. 线段树直接开 4 倍空间得了！！！别写 131072 << 1 了，很容易忘记改然后直接写 N << 1 然后寄掉的。

  7. 线段树多测， build 的时候记得清空标记！！！

  8. （*2）线段树的 T 要开 N << 2， tag 也要开 N << 2！

  9. while(a / i == 0) a %= i, c++;

  10. 离散化不要忘了 +1：val[i] = lower_bound(...) - b.begin()/**/+ 1;

  11. while(/**/ql <= qr && que[ql] < l) ql++; 没判序列为空就弹队列，wssb

  12. sqrt 的返回值 double 只保证在 int 范围内不会掉精度，需要更多精度自然需要更精确的浮点类型，所以需要使用 sqrtl

  13. 有些时候传 const char* 参，想想需不需要 +1。如果 rep(i, 1, n) 了那当然不要传 s+1，错误示例。

  14. 数位 dp 里 if(!limit && !lead) 再给 dp 数组赋值。 错误示例。

  15. (*2) 滚动数组优化 dp 不要忘记清空（否则 dp 数组里还残存着 i-2 行的信息）。

（以上为2023.11退役前内容。）

  1. 不要想着单调就能 lower_bound，必须单调递增！！
  2. 多测清空不要只想着清空数组。有时候答案什么的也需要清空！ 
    bool negative_loop = 0;
void SPFA() {
/**/negative_loop = 0;//最难绷的多测未清空
...
}
  3. std::min(int*, int*) 是对地址取 \min，应使用 std::min_element！！
  4. 怎么又是多测不清空？？ 
    rep(i, 0, n - 1) x[i] = s[i] ^ 48;
x[n] = 0;//多测清空 因为下面算 l[n-1] 要用到
l[n] = -2;
for(int i = n - 1; ~i; i--)
if(!x[i + 1]) l[i] = i + 1;
else l[i] = l[i + 1];
  5. 清空时想想到底用到的是不是 n！比如图论拆点 rep(i, 1, /*n*/n << 1) to[i] = vis[i] = 0;
  6. for(int i = n; i >= 2; i++)
  7. 怎么又双叒叕是多测未清空？？？\\scanf("%d", a + i); a 数组类型是 long long，虽然读入范围是 1e9 但是操作后可能会比较大，这时按照 %d 读入不会覆盖 long long 的前 32 位导致悲剧。
  8. （*4）分解质因数最后一个要特判！if(m != 1) p[++idx1] = m, c[idx1] = 1;
  9. 建图的时候想想图的点数是不是 n。说不定是 k 呢。
  10. 写 set 的时候一定要想有没有重复元素，有的话要写成 multiset！！
  11. 二分的时候注意如果 r 可以大于 1e9，开 long long，或者写成 mid = l + ((r - l) >> 1)，因为 l+r 可能爆 int！！！
  12. qp(5, (mod - 2ll) * (n - 1)) 会爆 ll，先算逆元再算 n 次方会比较好。
  13. 注意暴力的时候开的变量可能不符合数据范围！比如 n\leqslant 10^{18}，暴力只能跑 O(n) 就开的 int n，套板子优化的时候忘记改成 ll 了，结果样例也没有 n 爆 int 的！
  14. 计数题或者其他需要取模的题，注意负数！！！很小的负数也可能带来天大的错误！（如果随处取模的话，这个负数可能造成的唯一问题就是输出是负数而判错）
  15. 像这种 cf div2C 风格的找规律题，注意找第一个 0 的时候考虑没有 0 的情况！
int p0 = /*0*/ /*n - 1*/n;//这个初始值是给没0的时候用的！
rep(i, 0, n - 1) if(s[i] == '0') {
    p0 = i;
    break;
}

  1. 手模输到 CPEditor 的时候答案要把手模的答案手动输入，防止看一遍程序输出然后就想当然了！

  2. struct 变量初始化是好习惯，特别是线段树，除非你实现的是 tuple 这种东西。

  3. 尽量少特判，特判的时候要仔细核对题目。e.g. 多校 hdu#2 1012“给出一个长度为 n 的非负整数序列 a，你可以在这些数中选取任意个数（可以是零个），但不能选取相邻的数，求选出来的数的异或和最大值。”然后特判：

    if(n == 1) return writeln(val[1]);
if(n == 2) return writeln(max(val[1], val[2])/*, val[1] ^ val[2])*/);//baka 相邻的不能同时选

    特判的时候只记得关键词“异或”了。

  4. 传参时注意传参顺序！！

    int jump(int d, int u);// u点的d级祖先
u = jump(/*u, d*/ /*d*/d - (tr - tl + 1), u);

  5. 复制代码的时候看清楚，里层 break 的代码复制到外层循环要改成 continue！

  6. 用 std::cout/cerr 输出 __int8 或 uint8_t 等时注意要先转 int！不能直接输出否则输出很奇怪！

  7. main 函数直接写 return puts("-1"); 然后 exit code 3 一直以为是哪个 assert 挂了/oh/oh/oh。

  8. 分块，for(; bel(l) == bel(l - 1); l++) a[l] += c;，后来改写法变成 rep(i, l, blkl[bel(l)]) ，循环变量变成了 i，但是后面依旧是 a[l] += c/wx。

  9. if(d[i] > k) sp += d[i] - k;
else if(d[i] < -k) sn += /*k*/-k - d[i];

  10. 注意 rep(i, 1, x) 即使 x 是 ll，循环变量也是 int。如果有需要 i += ... 的情况，直接写成一般 for 就好了。（同时如果 rep 里面 i 范围是 auto，dill 都救不了）

  11. 带权并查集不能直接启发式合并（需要 swap(u, v), swap(r1, r2), w *= -1），也不能写 u = find(u), v = find(v)。

  12. 虽然 ll ans，但是 int b[]（范围正确），ans -= b[] * (i - 1) 炸 int 见祖宗！

  13. inf 尽量开大点，防止出现数据范围 [0, 1e9] 导致答案 1e9+1 的情况炸二分边界啥的。

  14. 差分不能写成 rep(i, 1, n) d[i] = read() - d[i - 1]，老老实实两个数组！

  15. 差分注意第一个元素可能是没有意义的，从 2 开始判！