易错&问题

不知道放哪里的知识点

一个难忘的夜晚。

1. getchar()若在读入时使用，在之前和之后一定要把多余的空格换行符用while读取完，因为你不知道可爱的出题人会在数据里给你塞一堆你看不见的奇奇怪怪的符号！
2. 类似于八皇后问题，如果网格图中只走对角线的话，如果是左下对角线，那么横纵坐标之和不变，如果是右下对角线，那么横纵坐标之差不变，扩展出去，其实就是奇偶性不变，如果要标记的话，作差要记得加上 $n$ 放置负数下标。
3. \在cpp中属于转义字符，若要使用需要这么写：\\。
4. 无向图不要被题目$m$的范围所迷惑，因为是建双向边，因此要开两倍空间！
5. Tarjan求割边的时候不能在输入时确定父子关系，因为会导致一个点哪也取不了（都是它的父亲怎么走），所以要在遍历的时候再标记它在树上真正的父亲。
6. 对于取模的问题，一定要时时刻刻想着取模，加法要取模，乘法要取模！
7. 如果你在计算时没有加入1ll*的话，那么你的函数传参就要是long long，例如void eval(node &t,ll add,ll mul)
8. 倍增求LCA一定要记得把零号节点的深度初始化为-1，防止跳到0号节点，因为不存在的零号节点的深度和根节点深度一样，默认都是零，或者其它的解决办法就是把根节点深度从1开始算。
9. MLE想想有没有可能是递归爆栈。
10. 最长不上升连续子序列的数量等于该序列最长上升子序列的长度。
11. 树状数组和线段树查询最长上升子序列时初始返回变量要设成0！！！避免进入不了循环而返回-1，或者判断不让0进入查询。
12. 滚动数组优化每次更新之前记得把当前这维memset为初始值！
13. 不一定是左边打不到右边右边就一定打不到左边，注意双向判断。
14. 树形DP时要先合并两子树信息再合并两子树大小，防止枚举过量。
15. 预处理次幂的时候一定不要忘记零次幂！！！！
16. long long 下进行 memset 此时的 0x3f 不再是 0x3f3f3f3f，而是 0x3f3f3f3f3f3f3f3f。
17. 非递归快速幂的临时变量一定要开 long long
18. 递推逆元时，用多少就预处理多少，不然会导致大于 $p$ 的部分阶乘的逆元全都为 0，然后倒着往前推的时候导致所有阶乘的逆元都为 0，导致求出的答案也全是 0.
19. 数组类型一定不要写错！！！！！！为此ＤＥＢＵＧ 了一小时。
20. 求 gcd 的函数返回值一定不要忘了函数名，已经错了两次了。
21. SB UVA 有着极其严格的格式要求，不要被卡格式了哦~
22. 模二意义下的加法相当于异或。
23. 使用 if 时，cpu 会在空闲时间进行分支预测，提前预处理部分指令，当结果为 false 时，预处理结果作废清除，反而会降低效率，所以 if(q[i + 1] != q[i] + 1) tot++; 会比 tot += (q[i + 1] != q[i] + 1); 要慢，尤其是在数量级较大的时候（比如搜索）影响很大，值得注意。
24. 写树的时候尽量不要用单点修改来建树，最好有一个建树的函数，否则可能写可持久化的时候会寄掉。
25. 比赛时，空间复杂度一律为 O(能开多大开多大)
26. 不要把可能用到的变量当作 while 的终止条件，比如 while(n--)，因为后面可能会用到这些变量。
27. 对于线段树的区间加法：修改叶子节点之前一定要下传标记，这样保证了叶子节点的信息始终是正确的，这样再次修改完叶子节点后上传得到的根节点的信息也是正确的，否则根节点就会上传时被覆盖为错误的信息。
28. 线段树区间覆盖最大值问题
29. 树链剖分注意考虑重边以及自环，以及你加的虚拟源点，会影响数据结构的右界。
30. lower_bound 返回的是大于等于某数的最小的下标，那么 lower_bound - 1 就是小于某数的最大下标；同理，upper_bound 返回的是大于某数的最小的下标，那么 upper_bound - 1 就是小于等于某数的最大的下标。
31. while(x--) 后，x 的值为 -1，先判断为 0 退出循环，然后再执行 --。
32. 数位 各种 DP 一定不要忘了初始化 f 数组为 -1.
33. 0b 前缀表示二进制，0x 前缀表示十六进制。
34. string 不要用 'L' + s 拼接，这样复杂度是 $O(n)$ 的，如果要在前面插入，可以用 s += 'L'，然后 reverse 一下。
35. 有符号变量溢出属于未定义行为，而无符号变量溢出不属于，它自然溢出相当于对上界取模。

问题

1. 01BFS 为什么可以优化复杂度啊。 没有这种说法，01BFS是只有边权0和1的情况下对堆的一个优化，双端队列优化SPFA属于是玄学优化，任何SPFA都可以被卡成$O(nm)$。
2. SPFA 什么情况下一个点会进队两次，出现了环吗？个人认为至少有弱连通环，比如一个点先被一条短点的路径遍历到了，然后又被一条长一点的路径遍历到了，这样就更新了两次。
3. Tarjan什么时候要判断自环和重边啊。
4. 为什么线性筛法时某个数一定是被它最小的质因子筛掉的。
5. 通过 search: #Q 看一些问题。