错误记录

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

程序细节问题

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、要依赖静态查错、分段查错而不是动态查错,时间要安排好

//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$。

算法数据结构问题

通用

缩点、树剖、单调队列注意前后序号的不同,一个字符一个字符得查

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、拆点后数组开足够来

Tarjan

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

并查集

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

斜率优化

1、que[l]l区别
2、原点是决策点 初始化r必须为1
3、单调队列中要有两个元素才能算斜率,所以l < r

莫队

1、while不要写成if

数论

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

记忆化搜索

1、要记得如果当前是算完的值要直接返回

差分序列

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

BFS

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

DFS

1、DFS 环问题注意时间轴

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