毫无疑问的是,我现在的智商处于直线下滑阶段……这里一些犯过的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、不要在错误的复杂度下被常数优化浪费掉大量时间。