VEXOBEN
Vexoben
Aug 16, 2100
It takes 2 minutes to read this article.

毫无疑问的是,我现在的智商处于直线下滑阶段……这里一些犯过的sb错误。至少看上去不要那么傻……

算法方面

1、DAG求单源最短路的时候不能直接拓扑排序,因为有多个入度为0的点。

2、数位dp的数组中不用存有无高位限制。不然多组数据复杂度非常爆炸。

3、倍增LCA的时候,根的dep被赋值成0。

4、AC自动机root编号是0,后缀自动机root编号是1。(存疑,可能是写法问题)

5、线段树能下放标记就下放标记,空间能开4倍就开4倍。

6、大力分讨的时候忘记 return 0。

7、打快读不打读入负数的情况。

8、KDtree询问复杂度是O(n^(1-1/d)),不要幻想100000的数据四维KDtree打了就能过。

9、Qpow函数要打返回值!!!

10、出现了奇怪的编译错误时,先看一下数组大小。

11、高维数组的一个维度溢出,但没有越过整个数组的范围,-fsanitize=address不会检测出来。

12、windows下iostream用scanf本地不会CE,函数名只打inline不打函数类型本地不会CE。

13、for(int i : ×××)不开C++11只会报Warning(但是运行会挂),for(auto i : ×××)不开C++11会报CE。

14、可撤销的并查集要倒着撤销。

15、计算复杂度时小心log在指数上的情况……

16、考前背好KMP的板子。

17、vector的size是 unsigned 类型的,在判断 i < vec.size() - 1 时要留意。

18、 DAG要特殊考虑关键点的入度不是0的情况,一些无用点的处理。

19、在 linux 下可以用 size tmp 来查看可执行程序 tmp 占用的静态空间。可以在程序关键点加 while(1) 后用资源管理器看可执行程序的动态空间。

20、一个空 vector 的内存占用是 24byte, 在均摊下vector占用的空间是正常使用的两倍,卡空间的正确做法应该是开静态数组+少量指针辅助寻址。

策略方面

1、比赛前一小时还在 打(推)隔膜/看番。

2、在剩余时间不少于30min的情况下弃疗去hack。

3、大考前不要听音乐。

4、即使可以保证算法的正确性,也应造极限数据测试算法效率。

5、感觉当前想的算法没有优化余地但是不想放弃的时候,先去码好写的暴力再回来换思路想。

6、不要在错误的复杂度下被常数优化浪费掉大量时间。