错误记录

这里用来记录自己做题的一些错误
这里包括了静态查错查出来的和调试、交题之后找出来的错误

程序细节问题

1、滚动数组没有清除上一层状态
2、有改动记得整个代码核查
3、复制的一段代码要改完相关部分,最好重复部分代码不要复制,重新打一遍
9、访问标记记得打
10、变量名不要打重复
11、要清空数组
12、初始化范围不要出错,不要赋错值
13、相乘超过long long,中间乘强制转换long long,以及快速乘的运用
16、输出浮点数不保留小数要写作%.0f而不是%d
21、一个点连其他点,要判断当前点是不是障碍
23、有0点不要从1开始循环
25、$eps=1e-7$不要误写作为$eps=1e7$。
27、有部分数字忘记开ll
29、尽量避免ceilfloor,尽量避免使用浮点数
30、DFS 要注意当前状态合法性,不合法return
31、不要忘记模数/输出无解
33、写完程序要核对时间复杂度是否是预期的
34、写完程序要核对空间复杂度是否是预期的
37、已经覆盖的指针/值不要用,在前面用 tmp 存
39、邻接矩阵重边记得取要的边 (都要的话就不能用邻接矩阵)
40、
a == b 等价于 fabs(a - b) < eps
a != b 等价于 fabs(a - b) > eps
a > b 等价于 a - b > eps
a >= b 等价于 a - b > -eps
42、预处理能带入n就用n,防止 TLE
43、对于复杂度、数字等要认真算避免出错
44、暴力不要想当然写,要把思路写纸上
45、要依赖静态查错、分段查错而不是动态查错,时间要安排好
46、样例数据用最朴素方法验证
47、部分分花多时间想
48、极限数据特殊数据过不了也尝试一下
49、TLE、WA微调一下思路代码
50、不清空可回收利用的
51、递归不要出现多次递归,否则会退化 (线段树如果用宏的问题、分治等)
52、有重复元素都要用要改成mutiset

//4、位运算优先级问题,要适当加括号
//5、改过的东西要记得改回来 (%lld->%I64d)
//8、中间变量开long long
//15、DFS要退出最好用exit(0)
//17、INF太大溢出了(没处理INF相加的情况)
//19、记忆化搜索的区间有$(l+1,r-1)$,而边界没有判断$l>r$的情况,结果栈溢出
//20、sort的cmp要加const如果加了&
//22、边界判断的时候$x>0$不要写作$x$,因为$-1$也是$true$。
//24、DFS判断边界的时候不要放在处理答案的前面
//26、64位整数都加ll后缀
//28、访问过的不要再访问
//32、用了 stl (map, set)被卡换另一个可能能过
//41、草稿好好打,特别是几何/解析几何/坐标系不要画歪

//1、一道题一时调试不出来可以放一下,然后之后来调估计就马上调出来了
//2、考虑问题要周全,如果有特殊情况考虑一下性质(例如造数据无法造出期望数据,可能这个数据就是无法被造出),可能有结论(只有部分情况有解)

DP

1、DP方程考虑欠缺:多出数据卡
2、计算概率DP的时候+=写作了=最好以后都写=,因为反正初始化都是$0$。
3、判是不是叶子最好用度数deg来判

算法数据结构问题

通用

1、缩点、树剖、单调队列注意前后序号的不同,一个字符一个字符得查
2、扫描求段(末尾要处理)的题目中间用值小心,最好后面再用
3 、提前退出把所有标记标好,处理完 (NOIPDay1T2, Bzoj1791),CF 某场eduC

AC自动机

1、AC自动机要传val
2、AC自动机danger的传递不要出错
3、统计答案不要统计danger点

Trie树

1、Trie树是前缀树,可以倒过来插入字符然后变成后缀,可以当做正常树处理

倍增

1、LCA方程不要打错(方向,媒介)
2、DFS序中一条路径最后出现的节点是LCA
3、求LCA的时候不要忘记先判断$a,b$深度
4、边权放点权不要加到 LCA 的点权

树剖

1、树剖复杂度为$log^2n$
2、树剖注意新编号和旧编号

线段树

1、线段树一定要仔细打
2、树的初始化要放进build里,不然重建线段树标记都会影响结果
3、不要忘写$build$
4、$build$里不要忘$pushup$
5、置$lazy$后要处理当前区间
6、$query$合并时区间没有同时访问左右区间,而处理了左右区间的中间颜色
7、$pushdown$ 不要忘记传 $lazy$
8、主程序里要调用$build$。
9、线段树数组要开到四倍。
10、动态开点线段树赋值空点不要用-1用0,否则要做很多特判
11、能修改原数组的值就修改回去
12、如果有查询$i-1, i+1$的,维护区间要开到$[0,n+1]$

二分图

1、$lk, vis$数组不是左边的个数,$G$才是左边的个数
2、匈牙利算法时间戳优化不要忘记了给时间戳赋值

最短路

1、求最短路树长度相等时不要再入队, 否则计数会有重边
2、枚举最短路要考虑 2 或 4 种情况,因为有不对应的情况
3、拆点后数组开足够来
4、负权图注意判 != INF

Tarjan

1、处理完没vis[e]=1, vis[u]=-1
2、处理完后新图不要用到旧图去了。

并查集

1、并查集$find$函数中路径压缩忘记赋值给$fa[x]$,直接导致并查集深度变深,TLE。

斜率优化

1、que[l]l区别
2、原点是决策点 初始化r必须为1
3、单调队列中要有两个元素才能算斜率,所以l < r
4、斜率优化实数会被卡精度,用叉积来判

莫队

1、while不要写成if

数论

1、分解质因数、求欧拉函数不要忘记加最后一个质因数,判断超限:$i*i \leq x$,$x$是当前那个一直在除的

记忆化搜索

1、要记得如果当前是算完的值要直接返回
2、记忆化搜索返回值比较大不要用,用其他方法,否则会 MLE

差分序列

1、不是cf[i]=1, cf[i]=-1而是++cf[i], --cf[i]

BFS

1、求最短路树长度相等时不要再入队, 否则计数会有重边
2、BFS 的状态如果不止一个那么vis数组要加维

DFS

1、DFS 环问题注意时间轴

最小表示法

1、不要忘了清空$k$
2、不要忘在$i, j$相同时将$j$移动

矩阵

1、矩阵快速幂的矩阵大小不要太大,尽可能离散化
2、矩阵乘法修改后单位矩阵记得改
3、初始矩阵选取值

链表

1、链表判合法要同时判表头表尾
2、链表的 ins 位置是前一个
3、链表 0,1,2 位置是不可达位置,赋值赋$INF$要考虑这三点

Splay

1、splay中不要忘记写换根 if (gl == 0) rt = x;
2、splay中最后一个rotate(x)写在判断外面
3、rotaterel(x)一定要预处理,因为之后会被改变
4、insert中不要忘记转到根,remove中不要忘记转到根+更新信息
5、insertfindwhile注意判断中的 $val$ 怎么写
6、kthif (k <= siz[ch[cur][0]])<=
7、检查每个函数是否 pushuppushdown
8、对维护值进行修改等时,对照变量数组列表先数有没有漏,再看标记维护有没有错

高斯消元

1、自由元最后统计

快速幂

1、$BS$的自乘不要放在if里了,特别是矩阵的

CDQ 分治

1、根据题目偏序要求定flw[t1].y <= flw[t2].y的比较符
2、排序要$n​$维都单调

组合数

1、阶乘算 $C$ 要注意 $C$ 中参数取值范围,切忌直接用 $N, M$ 的范围!

费用流

1、Spfa 记得取消 vis的标记
2、反向弧的价值相反,否则死循环

------ 本文结束 ------