错误记录

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

程序细节问题

1、滚动数组没有清除上一层状态
2、有改动记得整个代码核查
3、复制的一段代码要改完相关部分
4、位运算优先级问题,要适当加括号
5、改过的东西要记得改回来
6、部分分数组尽量开大,避免数据不严谨
7、传数组要指定大小
8、中间变量开long long
9、访问标记记得打
10、变量名不要打重复
11、要清空数组
12、初始化范围不要出错,不要赋错值
13、相乘超过long long,中间乘强制转换long long
14、变量不要打反
15、DFS要退出最好用exit(0)
16、输出浮点数不保留小数要写作%.0f而不是%d
17、INF太大溢出了(没处理INF相加的情况)
18、不要忘记模数
19、记忆化搜索的区间有$(l+1,r-1)$,而边界没有判断$l>r$的情况,结果栈溢出
20、sort的cmp要加const
21、一个点连其他点,要判断当前点是不是障碍
22、边界判断的时候$x>0$不要写作$x$,因为$-1$也是$true$。
23、有0点不要从1开始循环
24、DFS判断边界的时候不要放在处理答案的前面
25、$eps=1e-7$不要误写作为$eps=1e7$。
26、64位整数都加ll后缀

思考方法问题

考试

1、思维要完全正确再写,多出几个样例老老实实模拟卡一卡
2、写好思路再编程,对于复杂程序很好用,而且最好分段查错
3、不要在一题上花太多时间,要依赖静态查错而不是动态查错,要检查思路是否正确再写,不然既浪费时间又影响心态,时间要安排好
4、暴力不要想当然写,要把思路写纸上
5、考虑问题要周全,如果有特殊情况考虑一下性质(例如造数据无法造出期望数据,可能这个数据就是无法被造出),可能有结论
6、要看清题目再做题
7、dfs过程先打草稿,不然浪费时间调试
8、对于复杂度、数字等要认真算避免出错
9、正常题不要老想着Trick做法
10、不要把问题想复杂了

Trick

1、数组开不下但是总量很小可以考虑$vector$
2、n \leq 10^9$不一定不能枚举,可能可以缩小范围枚举,不要思维定向
3、对于DP/序列,要多往单调方面想
4、后序遍历等于DFS序
5、注意边界的处理(0, 1, 负数,特殊情况)
6、long long范围$[-2^{63}, 2^{63}-1]$,大约有19位

DP

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

算法数据结构问题

AC自动机

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

Trie树

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

倍增

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

树剖

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

线段树

1、线段树一定要仔细打
2、树的初始化要放进build里,不然重建线段树标记都会影响结果
3、不要忘写$build$
4、$build$里不要忘$pushup$
5、置$lazy$后要处理当前区间
6、$query$合并时区间没有同时访问左右区间,而处理了左右区间的中间颜色
7、$pushdown$ 不要忘忘记传 $lazy$
8、主程序里要调用$build$。
9、线段树数组要开到四倍。

二分图

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

SPFA

1、DFS的SPFA不要忘写递归

Tarjan

1、处理完没$vis[e]=1, vis[u]=-1$。

并查集

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

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