错误集合

发表于2021-04-10更新于2023-09-20阅读次数

  • 线段树四倍

  • 马拉车开两倍！（需要插入通配符）

  • 有时候随手写个暴力很快，不用对拍，就在原代码里写，然后把输出比较，这样有时会让效率提高很多

  • 二分图建网络图，如果 s = n + m + 1 那么判断右边的点就不能用 i > n

而是要 i > n && i < s

  • BSGS 注意，p 是质数不一定能直接上 BSGS，因为 底数可能是 p 的倍数

  • BSGS 注意了，两边的东西要先对 p 取下模

忘记对右边的数取模，可能导致找不到解，忘记左边取模可能忽略底数是 p 的倍数的情况

  • 同下条，如果可能的话尽量测测答案为负数的数据

  • 注意数组初值不一定是 0 ，常见于要取 max 的 ans 数组或 ans 变量

如果真实答案是负数，那给变量赋 0 初值就死了

  • 写封装的时候一定注意了，一般的写法不会用 oop（数组模拟），那么下面这种写法就很笨比
1
void cpn(cmnd x,cmnd y){ x.l=y.l; x.r=y.r; x.v=y.v;}

这种写法只对形参进行了修改！影响不到外边

需要用索引找到真数据的位置改

1
2
3
void cpn(int x,int y){
nds[x].l=nds[y].l; nds[x].r=nds[y].r; nds[x].v=nds[y].v;
}
  • 如果你企图用这种方法：printf("%d.%d",ans/100,ans%100)来以小数形式输出百分数，那就要自闭啦

问：102/100 = ? 102%100 = ? 102.0/100 = ?

  • 张帆（主席）犯过的 DP 错误：dp[0][0][0] = 0 ，其他都是 -inf

第一维表示直到第 i 个物品，dp[i][j][k] 从 dp[i-1][j-1][k-1] 和 dp[i-1][j-1][k-3] 转移

那么这样就会导致从第 2 个物品开始，(0, 0) 的状态不为 0 ，相当于强制后面的物品上前面的车，不能从头选

应该给所有物品的 (0, 0) 都初始化为 0

为什么背包没有这个问题呢？

因为背包所有物品都 dp 在一个维度上呀，dp 的时候一定要注意了

  • 网格图的点数要特别注意

你以为是 n 个点？其实是 n*m 个点哒

这个在开数组，判断爆 int 等步骤都容易出错

  • 一个 dfs 时复杂度分析的错误

我枚举 n^2 条边，对于每条边都花 O(n) 检查是不是树边，如果这条边是树边（ n - 1 条），那么就枚举选或不选并搜下一层

这样其实并不是 2^n*n 的复杂度，因为 n^2 的枚举和 2^n 的枚举是相互交织的，n^2 并不能被 2^n 覆盖掉，总复杂度差不多还是 2n*n3 量级

所以还是别偷懒用 O(n) 检查，先用并查集预处理出树边再搜吧。。

  • 当通过返回 oo 来控制二分中贪心的无解的时候

注意是否会爆 int（很可能会的，所以还是慎用 oo 啊，用了尽量开 longlong 吧）

  • 当你在递归或 dfs 中使用队列或栈的时候一定要小心了！

大多数时候所有的递归层数共用一个队列，如果不退栈将导致可怕的后果

事实上，即使保证每个点至多只入队一次，如果多层递归同时用一个栈的话，还是必须记录当前层的栈顶位置

所以还是尽量避免多层共用吧，先预处理好，再一次性做完队列该做的事

  • 用阶乘预处理法求组合数时一定注意，注意检查阶乘预处理的范围

尤其是方格里求组合数，阶乘的范围是 [0, n + m - 2] 而不是 [0, n] ，也不是 [1, n] ，注意求 0

如果只预处理了 0 到 n 交上去必 WA ，肯定又要怀疑结论错了，损失惨重，切记啊！

这个易错点再次说明手测最大数据的必要性

  • id 函数初始化和统计答案的时一定注意！

统计的不是 1 到 n ，而是 0 到 id(n, m)（或者别的范围）

id 函数易错点，只要出现 id 函数必须列入常规项检查

  • 多维 id 函数解压易错点：如果 id = x*m*4 + y*4 + z ，那么 y = id/4%m 而不是 id%m/4 ，注意顺序

  • 使用 id 函数压缩状态的时候一定注意最小的 id 是不是 0 ，以及会不会造成影响！！！

例如 last[t] != 0 这个判断，就可能在 id 为 0 的状态前停下，而不是一条链的开始停下

再比如初始化的时候，容易写成从 1 到 idmax 初始化，把 0 漏掉导致错误

  • 一个剪枝中的贪心错误

左边有 n 个点有一个权值 a[i] ，如果这个点总共被选 d 次，那么它对答案的贡献就是 a[i]^d

右边有 n 个点，每个点必须选择一个左边的和这个点连边的点

思考：启发式函数中，右边的某个点对答案的启发式函数 h 是否能设置为与它连边的所有点中 a 最小的那个？

不是！

当 a = 1 时，如果某个点第二次被选，它对答案的贡献是 0 而不是至少是 1

  • 如果数据不是特别大，不妨先写一个简单的启发式函数，TLE 了再尝试优化，不要一上来就写很复杂的启发式函数，导致出错就得不偿失了

  • 读入字符串时字符串的数组一定不要开成刚好的大小！！！

因为 scanf 读入后会添一个 \0 ，如果数组大小刚好就越界了。。。

所以还是不要省什么内存了，每个数组都尽量有点冗余，免得又有什么奇奇怪怪的错误

  • 判断所有的点能否到达 T 一定不能偷懒原图 bfs 或 dfs ！

必须建反向图

  • 倍增求 lca 的注意事项：

注意如果要同时维护区间和，区间最大值的时候（边权），最后 x 和 y 往 lca 合并的时候，由于二者是从同深度共同向上，因此两人的（边的）值都要考虑到

1
2
3
if(x==y)  return mx;

else return max(mx,max(mst[y][0],mst[x][0]));
  • 计算几何检查点：跟 eps 比的东西有没有 abs

没加 abs 就傻 b 了哈哈

  • 不管是手写堆还是用 STL ，比较优先级的时候切忌进行 dis[x] > dis[y]（dis是全局数组）这种比较

因为 dis 会变，堆里用来比较的 dis 不是入堆时的值，修改 dis 会导致堆结构混乱

  • 大坑！python 读入字符串的时候会去掉 \n 但是不会去掉 \r ，所以 python 尽量避免全句匹配！

\r 一般是 windows 在记事本里手打数据造成的

  • 幂取模的时候注意指数要对 (mod - 1) 取模

检查的时候注意有些计算函数可能放在指数上面，函数里的模数也要是 mod - 1

  • 一种错误的 DP 写法：
1
2
3
4
//f[x][0]=max(f[x][0],f[x][0]+f[e[i].y][1]);
//f[x][0]=max(f[x][0],f[x][0]+f[e[i].y][0]);
//注意不能这么写，会重复增加答案
f[x][0]=max(f[x][0],f[x][0]+max(f[e[i].y][1],f[e[i].y][0]));

  • dfs 回溯的时候注意检查完全，不要光盯着循环里看，函数开头 dfn 类似的可能也要回溯

  • 给你一个区间的左端点和长度，范围 1e9 ，那么坐标的范围是 2e9 而不是 1e9 ，因为 1e9 + 1e9 = 2e9

  • 要求你统计字符串中出现的字符中出现的次数并升序输出，注意没出现的字符可是不输出的哦。。。

  • 10 点 40 的时候时针不在 10 上！涉及到钟表的几何问题可能掉坑

  • 如果把 2 位小数转整数，(long long)(b * 100) 不可取，b = 0.57 时得到 0.56 ，应该 + eps

  • double 的有效位数大概到 16 位，一个 1e15 的整数乘一个两位小数，再转成 longlong 就可能丢精度了，应该给小数乘 100 再除回去

  • double 强转 int 的时候注意可能要加括号，例如 (int)a*b ，如果 a 是整数 b 是浮点数，而想让 a*b 变成浮点数就傻了，应该 (int)(a*b)

  • 如果要输出整数部分，注意算清数据范围，有时候不能用 (int)a 而是 (long long)a

  • 两个值为 1e10 的 long long 相乘结果大于 0

  • 用 multiset 的时候，注意 erase 是删除所有相等元素，并返回删除元素的个数

  • 注意别把 2e5 的数组开成 1e5

  • 鸡兔同笼问题中，有 a 个头，b 只脚，判断数据是否可能的条件不是 2a <= b <= 4b，而是 b%2 == 0 && 2a <= b <= 4b！

  • 强连通分量缩点 + 拓扑排序千万不能偷懒不缩点！！

不缩点而用标号代替的后果不仅是 WA（拓扑 DP 的最优值有滞后性），还会 RE（不缩点是假 dag ，还是有环的）

  • 用余弦定理时注意判断是否构成三角型，3 中情况都必须判断到，很容易漏

  • 直角坐标转极坐标的时候注意 α 不是 arccos(Δx/l) ，arccos 的范围是 [0, pi] ，还需要判定 Δy

  • 长度为 0 的序列错位排序方案数是 1 不是 0

  • 如果对 dp 的 f 数组做前缀和，注意 f 的初始状态如果不为 0 ，那么前缀和中，对应一层的初值都不为 0

  • 有些 dp 使用滚动数组可以直接赋值，无需清空数组，但是注意有一些赋值不到的地方（比如 f[i][0] ）可能需要清空

  • 出现灵异错误时可以注意一下局部变量是不是没初值，尽管这个错误在初学者里很常见，但熟练者一旦出现实际更为棘手

  • 线段树区间赋值注意 delta 的空值是否能为 0 ，因为区间赋值很多时候都存在把区间赋值为 0 的情况，这时 delta 空值不能是 0

  • 检查数组大小时要注意某些值的范围可能变化，例如缩点 + 背包，那么包的容量可能就会增大

  • SPFA（包括费用流）队列长度应该比点数多，因为可能重复进队

  • 用字符数组的时候不要把下标为 0 的当做长度，char 可以装数字但是只能装很小的数

  • 浮点数比较相等的时候，注意是 abs(a - b) < eps，而不是 a - b < eps

  • 有时候 sort 会巨慢，如果次数比较多就很难受

这时如果结构体排序，可以在比较函数前加 ‘&’ ，即参数取地址，防止每次函数调用都把结构体复制一遍，可以跑得飞快

当然也可以手写堆排序，难度不大

  • 如果 main 函数里 ans 没有初值，而 ans 相关的语句只有 ans = min(ans, …) 和 cout ，编译器是不会报错的（可能是把 min 那句当成赋值了）

这个时候会一定概率输出正确答案，当 ans 初值随到比答案大的时候就正确，否则 WA 233

  • 用 printf 四舍五入时需要 + eps，防止丢精度

  • 当 n 顶到 int 上限的时候，数论分块会爆 int。由此可见测大数据还是很重要呀，尤其是大数据很容易测的情况下！