trick点

1、问题里有取模操作的时候，最后输出(ans+mod)%mod

2、涉及到输出实数0的时候要特判输出的会不是是-0.000000（因为0.00乘一个负的浮点数结果是-0.000000，乘一个正的浮点数结果是0.000000）

3、遇见问题中有|x-c|，min(x,c-x)，max(x,c-x)的时候，考虑分类讨论其贡献，一般一个位置都答案的贡献只会分成两段，这个分界线可能是常数，也有可能是一个式子。如果是式子的时候，要尤其注意：比如k<=f(x)时，贡献是a，k>f(x)时，贡献是b，那么f(x)在变动的时候，要考虑f(x)<0,f(x)>n的情况，这时候一般都是和下界取max，和上界取min，要让k有意义。

4、概率dp的时候，有概率和期望两种，尽可能使用概率去做，用期望做的话，加的权值有可能会出错，期望dp加一个权值时候，不能直接加，要乘上这个权值的发生概率

　　即f[u]表示概率，g[u]表示期望

　　那么f[u]=Σf[v]

　　但g[u]=Σg[v] + value[u] * f[u] (注意千万不能写成g[u]=Σg[v] + value[u] )

　　其实如果要求期望，可以dp它的概率，最后求期望

　　即E=Σf(i)*value[i] = Σg(i)

5、比如求dp[i]=min(dp[j]*a[j]*b[j])，最后结果对mod取模，不能写成dp[i]=min(dp[j]*a[j]%mod*b[j]%mod)，因为中间有个取min操作，取min操作是不支持的取模的

6、Trie树边对应的信息放在下面的点上；Trie树也可以存数字，也是个有序的数据结构，要注意多个数字重复的情况，可能走到叶子节点的路程上对ans没有贡献，要最后判断叠加；Trie树可以支持整体异或，具体的就是询问的时候如果遇到某位是1，那么就swap(lchild,rchild)就行了

7、要注意无意义的清零和无意义的反复求字符串长度，这样可能会带来超时

8、分解质因数最后留下的可能不是1，是个大素数

9、区间筛的时候要注意r-l<=1e6，那么其实中间有1e6+1个数

10、将double类型的数字以int输出时：printf("%d",(int)(number+0.5));

11、遇见多组数据一定要记得检查有没有清空干净（如Trie树自动机什么），有时候甚至会导致MLE！！！

12、数组开小可能会导致TLE

13、cdq分治排序的之后注意坐标一样时，要比较操作类型，一般的修改操作在查询操作前面

14、遇见分组计数的问题记得考虑meet in middle

15、多次FFT、NTT的时候要记得将A[n..len]清0

16、二分分数区间$[\frac {a} {b},\frac {c} {d}]$的时候，$mid=\frac {a+c} {b+d}$

17、当遇到要计算$\frac {p_1+p_2+p_3+...+p_n} {q}$的值的时候，保证结果不超过$2^63$，分母q不超过$2^30$，这样计算就有个问题，就是分子相加的时候会爆long long，有个技巧就是$ans=\lfloor \frac{ans}{q}\rfloor *q+ans \, mod \, q$所以可以记录整除数和余数，这样就不会超过longlong了

18、若干个0和若干个1（1存在）能异或出的2^n个结果中，一定有一半是1，一半是0

19、计算几何一直WA也许不是精度的问题，而是因为小数据边界没有特判

20、==、!=的优先级要高于位运算（包括^），所以位运算要打括号

21、莫队算法的时候记得先移r再移l，否则可能会有的数字出现次数为负数带来数组越界

22、分层图最短路在外面把图先建好，后面直接跑最短路

23、树链剖分处理边权的时候尤其要注意，向上爬到最后，lca的点权不能要

24、处理可撤销并查集时候所用的按秩合并并查集在find的时候不能维护其它信息，其它信息必须另开一个函数get_val()用log(n)的时间求出来

25、当数据量很大的时候注意减少容器和递归的使用

26、当结果对1e9+7取模的时候，一般可以直接用int去做，但是如果数据范围是[-1e9,1e9]那就要小心了，可能会爆掉

27、一个都是整数的数列经过ufwt形成的变化中的数不一定都是整数（因为有/2操作），可以认为并没有一个整数数列对应的fwt的结果是这个数列，要注意。但是如果是fwt(a),fwt(b),a=a*b,ufwt(a)，那样是没问题，因为一定有解。

28、数组开大大容易超时，能滚动数组就滚动数组，比如决策单调性优化dp

29、在区间赋值的线段树里，注意tag=0的意思是给区间全部赋为0，而不是没有标记

30、取整数部分用floor，而不要用(int)

巴特西

trick点

最新文章

热门文章