我的错题集-updating

输入输出类:

* : 本人并不是太喜欢cin,所以此类错题一般针对于scanf&printf的语法错误.

1.明确变量类型对应的占位符

类型WindowsLinux备注
long long %I64d %lld 有时Windows也兼容%lld,但使用要谨慎
unsigned xxx %xxxu %xxxu xxx为原类型占位符
double %lf %lf 注意和long double,float的区别
long double %Lf %Lf 这里要大写..真的…(Luogu P2393)
float %f %f 这种类型并不常用…

(此处罗列的是易错类型,详细类型请见 我的另一篇博客 )

2.多组数据时易错点

1.当给你数据组数时注意读入那组数…
2.当不给你组数时观察结束条件,比如while(scanf("%xx %xx",&xx,&xx)!=EOF)EOF不加的话就会导致玄学错误…再比如以0 0 为结束要谨写while(scanf() && x && y),因为有些坑题会只让x或y等于0..
3.当你发现你WA了,或多拍一组数据全对,那想必你并没有clear掉一些该清掉的东西…
4.注意复杂度的计算乘上数据组数

比赛智障类:

1.文操不要打错
2.提交文件注意选最新版的
3.注意文件夹建在哪

基础错误类:

*:虽然基础但却很难避免…
1.注意for循环的边界条件,以及莫名RE or TLE 时看一看i++有没有写成i--
2.二分时注意条件是 l<=r 还是 l<r 还是 l<r-1.
3.写了一个函数时要记得调用它…
4.n,m的类型是int,在做字符串题时不要想当然char

算法错误类:

复杂度分析类:

1.注意一些隐蔽的复杂度,比如循环里的求逆(Inv),快速幂(Pow),这些一般都是可以预处理的..

模拟类:

1.如果涉及地图模拟的话注意方向和边界问题,还有是mn列还是nm列.

2.一般模拟问题都会涉及字符/字符串,建议采用scanf(“%s%d%d”)的格式读,即使读的是字符也不例外.(特此吐槽一道叫银河英雄传说的无良卡C/C++的题,那玩意的输入只能用” %c%d%d”,不知道出题人脑袋是不是进水了..)

3.loading…

并查集:

1.注意fa数组的初始化..

2.复杂并查集的问题注意多种类的循环关系

3.根据题目分析并查集是否要压缩路径

4.带权并查集注意路径压缩时$val$的改变

5.带$Merge$,$Split$的并查集记得弹出时按栈的顺序

6.$Split$后注意$fat$的还原,不是0

7.种类并查集记得合并完全

一点疑问:关于find函数的写法,三元运算符快还是if&else快.

最短路:

1.用SPFA时注意是否有可能用菊花图或网格图卡你,在此建议使用Dij.(然而我都用SPFA的)

2.要看清求的是最短路还是最长路.

3.SPFA判负环时注意一点要进队n次才能被认为属于负环.(雾..至少我是这样的)

4.模意义最短路时明确dis[i][k]存的是到点i,最短路模意义下为k的最短路,也就是dis[i][k]%P=k

5.loading…

平衡树:

Splay:

splay的核心操作就是splay和rotate,为了增加这两个操作的正确率,我们应选取更加简洁的书写方式
在发现Splay错的时候优先看这两个函数.
1.splay: 注意边界条件,即当前点和目标点距离为1or2时的处理
2.rotate:注意当前点的孩子与父亲的语句顺序
3.find:注意lc和rc的走向
4.reverse 由于要增加两个哨兵节点,注意原序列的pos与平衡树中pos的转化
注意在reverse标记的pushdown中,要保证当前位的信息正确(同线段树),
也就意味着在pushdown的时候是交换他左右儿子的左右儿子
5.总之所有操作最好都尽量通过Splay完成,这样才能最完全的避免标记所带来的问题

fhq-treap:

这太好写了…

点分治:

(一般采用子树合并的方法)
1.注意处理某子树到点分中心的单独路径,即只上不下

线段树:

首先无论什么题都要分析线段树的空间消耗
其次一定要注意laz标记的合并和下传设计

主席树

1.这个空间根据新版对老版的改动程度而定,一般是(原数组+n*log(n))(修改一次加log个点)

后缀自动机:

1.数组记得开两倍(因为有nq)
2.构造多串时记得及时重置las,ind等信息
3.与AC自动机不同,这里的root设置为1(个人喜好)

AC自动机

1.fail指针与fail树边方向相反
2.将rt设置为0,方便压缩fail时失配的情况,同时注意线段树的值域问题

3.注意在上面做DP时,一个点的信息包含所有它的fail的信息

LCA

1.ST表LCA时建的是欧拉序的。。括号序会十分难写。。

其它:

1.无向图的dfs树没有横插边

2.矩阵快速幂时注意矩阵的大小,要不然在传参时会爆RE

3.哈希时注意乘以pw 

**4.状压DP位运算时千万不要用1左移后判断关系,最好不要左移**

原文地址:https://www.cnblogs.com/functionendless/p/9439366.html