细节

Posted by Songtoy on 2018-04-17
#Personal

  1. 注意有取模时要注意模数的大小，有可能两倍会爆int导致答案错误. 同时答案之间如果是加减可以if (ans >= P) ans-=P; 否则要 ans=1LL*ans*X%P

  2. 如果读入数据里有负数不能直接用读入挂，要判负号.

  3. 使用位运算时要注意可能会溢出(如$1<<35$和$1>>35$ 均会溢出).(实例可见 Topcoder SRM 613 Div2 Level three)

  4. 三目运算符（？：）的优先级很低，甚至低于+、-，尽量少用或加括号.

  5. 部分位运算的优先级较高，如！、~，相当高，然后是*、/，再是+、-，最后是>>、<<，更低的有&、^、|.

  6. 涉及到LCA的问题要注意可能在同一个子树内计算.(CF715E)

  7. 结构体排序的operator一定要这样打:

    1
    2
    bool operator <(const node &A)const{
    }

    ​注意两个const不能掉.

  8. 处理割点时注意根节点的处理，当且仅当获得的搜索树中根节点的儿子不止一个时才算上.

  9. 文件名、longlong、mod

  10. 想题目要由浅入深，从暴力开始想,

    枚举往往最容易被忽略。–XiaoC

    其实这话不对，暴力还是经常被人想到的。只是应该选小的数枚举这一点经常被人忘记。

  11. 有时候满足单调性的问题可以构造前缀和(苹果落地COCI2014/2015 Contest#5 E)

  12. 枚举一个数的非空子集

    1
    for(int j=num;j;j=(j-1)&num)...

  13. 对于dp过程中尤其是区间型的，一定要注意边界处理，例如调用到了 n+1的dp值之类的（eg：CodeM初赛A轮B题）

  14. 选择排序并不稳定，反例:5,5,2

  15. 二进制优化：快速幂，倍增，矩阵

  16. 对于树上两点间路径的信息维护需要注意的点是：如果可以支持前缀和处理(如加减)就用前缀和处理，否则(如取min，取max等)就用区间处理（倍增）。eg:$dis(i,j)=dis[i]+dis[j]-2*dis[lca(i,j)]$

  17. 数组版的正向表需要注意的是内存，往往需要开两倍

  18. set/multiset 删除操作中一定要用迭代器删，千万不能直接删除值，特别是multiset，会把所有重复元素都删掉(见圣杯战争[USACO 2017 Open Platinum]，由multiset引发的惨案)

  19. 最小费用流和最小费用最大流的区别：最小费用流的目标是从S流到T使得费用最小，而最小费用最大流的目标是从S流到T在流量最大的前提下使费用最小。实现方面：前者return dis[t]<=0后者return dis[t]!=INF

  20. 树状数组是可以求后缀和的，as long as 将update中的x+=lowbit(x)改为x-=lowbit(x)，查询中的x-=lowbit(x)改为x+=lowbit(x)（可以看成是反向建树）

  21. 树上dfs的过程中dep的两种写法，dep[v]=dep[u]+1或dep[u]=dep[fa[u]]+1，两者都暗藏杀机：前者若由于根节点的dep不会被更新(清空)，在多次换根的dfs中会导致错误；而后者若由于根节点的父亲未被清空，在多次换根的dfs中也会导致错误.

  22. 图上问题的简化版=树上问题，树上问题的简化版=链上问题.

  23. 遍历一张图，无论是$dfs$还是$bfs$都是$O(m)$，即边数.

  24. 状压dp里需要注意范围，比如对于一个$1\sim N$ 的排列状压，$dp[i][mask\;xor\;2^{j-1}]$，否则数组需要开两倍.

    很重要，要么$2^n$对应$2^{A[i]-1}$，要么$2^{n+1}$对应$2^{A[i]}$

  25. 遇到结构体嵌套的情况时(尽量避免这种情况)，子结构体的函数是不能调用上一层结构体的变量的.

  26. 1
    只有一类数据成员可以在类中初始化：静态整型成员常量（整型并不只有int，char等也是）

    换句话说，如果在一个结构体里面，就算用static const double eps=1e-9;也会编译错误.

    ​

    • 比赛前一定要把Warning开起来(-Wall)！
    • 进入一道题的情境的最好办法是模拟小数据
    • 永远不要忘记贪心，贪心是个好朋友
    • 一定要再最后测一遍文件输入输出，并注意用fc，因为可能有鬼畜题要求输出只在一行(见某场比赛的爆零血案)
    • 想题目需要由浅入深，先从暴力着手
    • double 在做加法和乘法的时候误差会比较小，但是做减法和除法时误差会异常大，因此要尽量避免减法和除法
    • 涉及到double问题其实可以考虑枚举答案或其中一个变量，即使是非整数情况下也可以，一般会用到eps，可以考虑推出该变量的精度范围，如果范围可行那么就可以采用暴力枚举的形式(每次加上一个很小的值，或者直接转化成整形枚举)
    • 注意使用Lucas定理的时候，有可能$n\lt m$，则$\binom nm=0$，但是要注意如果采用$p$进制处理的话，每次要选取两者长度中的较大值为准
    • ​慎用static ,特别是递归调用的函数中，一不小心就挂了！
    • 负数判断奇偶性时不能用x&1，因为负数的补码不等于原码，举个例子：(-1)&1的结果是0
    • 使用树状数组时还是传入上界比较好，否则 容易出错，思维定式导致while(x<M)C[x]+=v,x+=x&-x;，但是如果$M$并不是树状数组的范围，要么可能会越界，要么可能会WA(没更新到)；因此，最好的写法还是while(x<=n)C[x]+=v,x+=x&-x;

  27. 修改和查询完全独立的线段树可以用分治替换；(大大减少复杂度)

  28. 棋盘图网络流前先黑白染色

  29. 无论什么类型的题目(甚至是通信题、交互题)，能对拍(造数据测试)总是好的，就算是自带的assert验证一个猜想也好；

  30. 内存什么的，说爆就爆了，还是不能小觑！特别是10^6级别的数据，随便开几个线性的，就超内存了；

  31. 所有特殊要求的最短路径都可以在最短路径图(DAG)上完成；比如求字典序最小的最短路径；

  32. 遇到非常大数的比较时，取对数是一个非常有用的办法；