犯错集合&个人缺陷&好想法

犯错集合

1. 善用CtrlCV，加快打字速度。

2. 认真训练，不要CB！

3. 调试用代码要注释于旁边 比如/*调试*/

4. 不吝啬于打注释 尤其是思路不清晰时（当然最好还是想得很清楚了再开始）

5. 边集数组2 线段树数组4 etc.
   至少判断每个数组的空间是否够 打代码时也要考虑越界问题
   原因: C++ 本身不可能报数组越界 只知道把指针瞎指

6. 不要随意全开 ll 平时偷个懒问题不大

7. 比赛前一天晚上好好睡觉！ 早起床，吃好早餐，别碰咖啡！

8. Ctime 中的 clock() 可以用于算运行时间 time(0) 用于 srand()

9. (tmp)等价于 (tmp!=0) 而非 (tmp>0)

10. 比赛里的题目顺序不要管！血淋淋的例子GDKOI2018Day1

11. O2要求十分严格 可能导致RE 所以不必要就别开

12. 函数不要作为循环范围(如ve[].size()) 建议记下来再用

13. vector 可能导致空间&时间二倍 也可以通过提前reserve防止其按二进制分配空间

14. 当题目复杂时,确立单一观察对象思考 例:各类hanoi

15. double 不能用memset赋极值(清空海星) 看上去值没问题 比大小时会出锅

16. struct 的 memset 需要使用 memset(&t,value,(sizeof t)或(sizeof(struct_name)));

17. 某种情况计算多次时 记得先考虑情况数是否整除 则考虑算完总数后作除法

18. 搜索顺序对时间影响巨大 不确定时可以对拍寻找较快顺序（反正只用改一点点）

19. 如果搜索题目剪枝编程复杂度较高 建议先打基本版 然后去做其他题 最后当提答题玩一玩差不多了

20. Hall定理：存在从V1到V2的完全匹配 当且仅当V1中任意k个顶点至少与V2中k个顶点是相连的

21. __Int128的输出要判断正负数

22. 对于大部分关于集合{x|x=f(y),y属于S}

23. 三维问题都可以采用 枚举(排序)一维+分治一维+数据结构一维

24. 可以认为T(动态开点)=3*T(离线离散化) 所以不要轻易作死！！！

25. LL比INT慢一倍！！！！

26. cmd的fc是不忽略行末空格&(\r\n)的

27. 打表拆系数是个好方法嘤嘤嘤

28. 如果不知道怎么做就尝试重新描述题目吧！

29. 有时在dfn很难线性实现时 不如改成类记忆化搜索吧！

30. 当复杂度涉及已删除点时 要考虑被删除者是否被扫描 当复杂度涉及已删除点时 要考虑被删除者是否被扫描

31. 不要轻易推翻原有的结论 很可能是极端条件杂糅（某些极端不共存）
    况且脑子还是新鲜的好用[吓]

32. 对拍时 请再三检查随机数据的一般性和暴力的正确性

33. 变元矩阵树定理:
    令A[i,i]=\sum e[i][j],A[i][j]=-e[i][j];注意负号！
    删去第r行第r列(1<=r<=n) 后，det(A’)就是各个生成树的边权积的总和

34. 求行列式的N^3做法：高斯消元（行列加减）成上三角 此时答案就是对角线上(n-1)个量的乘积

35. 稳定的排序算法:（带序号）相同元素结果稳定 而非时间

36. 大部分C++程序数组下标从0开始（记得因为初赛挂过&看标慢）

37. 有这样一类题目：边权=两点点权异或/gcd/… 求最小生成树 一般可以先把一些点（如点权相等）并在一起简化题目

38. 然后！如果需要求方案数，需要算上最开始合并那些点的方案贡献(n^(n-2))

39. 各类DP都可以考虑打成记忆化 好用范围：冗余状态多

40. n个点n条边是环套树！为什么我以前一直不知道[捂脸emoij]

41. 康托展开：一个排列的排名为 \sum [a_i为左的逆序对个数]*((i-1)!)
    逆康托展开 从第一个填什么或者从最小值位置开始考虑

42. 考前三日 辛辣是禁忌 没有为什么！！！

43. sort区间左闭右开

44. 简记tarjan 边双:去掉割边 再给每个联通块染色 割边(x,y)满足low[y]>dfn[x]
    点双:当dfn[x]==low[x]时 当前点为割点 所以 比它dfn大&&没有被其他割点隔开的部分都属于这个点双 具体说来 开一个栈保存当前遍历到的部分 跑完子树后判x是否为最高点 （因为手推出锅太多次所以废话嘤嘤嘤）

45. 多次提醒：请勿在意比赛题目顺序！

46. 注意思维和代码的统一，不要出现多种贪心/博弈/DP/…策略杂糅的情况
    阿我知道只有我才会人格分裂式想题

47. 树状数组：单点修改&前缀查询 套各种差分可以完成各种区间操作

48. 根据期望可加性 可以把期望理解作转移时的权 仅对本次转移产生直接影响

49. 数据范围最好再三看看 养成先检查常量定义和数组大小的习惯

50. 对修改二进制分组：用于处理“(强制在线&)各个修改独立贡献”的一类问题
    原理：把修改按时间顺序分组 询问时在每组分开处理分开贡献 通过合并末尾相邻两组 把每组大小控制为2^i形式

51. 树的哈希：对于无根树 取其重心为根;有两个重心时 规定hash值小的为根;
    (点有序)有根树和括号序一一对应 计算其括号序的哈希值即可
    具体说来 记f(x)为x的子树的hash 那么f(x)=v(x)+(f(son)异或和) 异或是为了防止子树遍历顺序影响哈希值
    重点注意：不要对中途异或值取模！不要对中途异或值取模！
    至于v(x) 我是随便取了 dep_x*du_x 反正只要是有根树上点的稳定性质应该都是可以的

52. 如果想到的可优化部分既不是瓶颈又很难实现的话…那就别实现了呗[吐舌]

53. 求环时一般是点双 因为边双的八字形特例 一个点可以存在于多个点双

54. 慢慢地你会发现 一些经典问题的推法只需要看思路 因为别人的推法可能绕很多圈子

55. 其实多个splay是可以共用 0 为根的 仅当你不需要0的son信息

56. 齐肯多夫定理:任意正整数n都可以被唯一表示为若干个不连续的斐波那契数的和
    证明：考虑贪心构造解 注意到f_i+1=前i-1项不连续的斐波那契数的最大和 每次取p使得 f_p≤n<f_{p+1} 若不取f_p 前p-
    项显然无法出解

57. 斐波那契博弈:先手必败当且仅当石子数n属于斐波那契数列
    证明：设n为第一个不满足结论的数
    当n=f_p
    ①考虑先手第一次取x，则x<n/3<f_{p-2} 故石子可以看作两堆f_{p-2}和f_{p-1} (因为先手无法一次取完第一堆) 由设可知后手总有方案取得第一堆最后一个石子
    ②又设此时后手最后一次取了q个石子 显然q≤f_{p-2}/3 又易证f_{p-2}/3<f_{p-1}/2 可知在第二堆先手也无法一次取完
    当n≠f_p 根据齐肯多夫定理 设n=\sum f_{a_i} a为有序数列，且不连续
    自此断言 先手可以取完f_{a_1} 此时剩下的f_{a_i}可视为互相独立的子游戏 每个都是后手必胜局面 得证

58. bitset 是个好东西 对空间也有Ω(一般考虑为1/32)的优化 e.g.JZOJ5932 所以有些空间好像爆炸的做法也可以考虑

59. O(n)求1~n逆元 inv_i=(-mo/i) * inv_{mo%i} 证明:设$mo=i*p+q$mo=i∗p+q 则 模意义下$i*p=-q$i∗p=−q 同时除以iq得证

60. 可以给予参数默认值(e.g:max(int a, int b=10))由于实参和形参是从左到右对应匹配的，所以带默认值的参数必须要在所有参数列表的右边

61. 竞赛是中学生活的附加，是一份bouns，所以没有所谓辛苦！

62. 伯努利数求自然数幂和
    

63. 神秘滑稽小质数(cc)1109 (infleaking)727 (ilnil)311 神秘滑稽小质数(cc)1109 (infleaking)727 (ilnil)311

64. 考场Debuff很正常，如果出现了 不要慌张。对自己要有自信！场上用平时双倍时间写出代码和对拍。参考PION7102和JZOJ5938两次经历 本以为需要一个小时实现的东西20min就打完了

65. 时间复杂度如果比较卡最好测测极限数据，出题人常常在此设置30左右的区分点

66. 竞赛图中，胜者向败者连边，将出度排序后得到序列s，其为合法比分序列当且仅当\forall k<=n,\sum_{i=1}^{k} s_i >= C(k,2)

67. 图上应用根号思想：m*sqrt n求(无向图)三元环 考虑按度数将点分类 将边定向作度数大连向度数小 此时枚举点x每条出边 打上标记 再枚举(x,y)中y的每条出边(y,z) 若z被标记 则(x,y,z)合法 根据构图 一条边作为度数大点时出边被枚举一次 作为度数小点出边时被枚举至多sqrt n次 而度数大的点至多sqrt n个 最坏情况总复杂度O((m+n)*sqrt n)

68. 对于可以离线的撤销操作 可以理解为把一个操作作用于一个时间区间

69. 别太自信了…有时候你调试了一个小时只是因为某一次你手抖把L打成R之类的 所以半小时时候就可以静态查错

70. 能不用实数就不用实数！@SjJ 100p->0p

71. 猜到了结论一定要证明，如果没有证明头绪就拍！有些看上去很假的结论实际是真的QAQ 参见JZOJ5950

72. 点积=投影模长=a.xb.x+a.yb.y，叉积=a顺时针扫到b的有向面积=a.xb.y-a.y*b.x

73. 负数取模不稳定！所以如果需要取模要转绝对值

74. 你以为你的树套树真的答案正确么？！比赛打树套树我就是狗！！

75. 两个组合数式子的本质都是从一个C(m,n)=C(m-1,n-1)+C(m-1,n)起点 考虑两种情况 C(m-1,n)空缺或者C(m-1,n-1)空缺

个人缺陷

74. 数据结构，字符串练习少
75. 容易开小差
76. 脑子里汪洋大海
77. 代码调试不熟悉 几乎没有技巧性可言
78. 对睡眠和食物需求量极大

好想法

50. 非递归求 dfs 序（$sz_i$szi​和根已知）

考虑每个点x
{
   找重儿子s
   dfn[s]=dfn[x]+1;
   求剩下儿子dfn（和sz有关）
}

51. 二分答案求前k大 (例3329树上的路径)