要补的东西

莫队总结

学习数数

需要完成的题目：

翻修道路
时代的眼泪
Tutte多项式
推式子练习1
推式子练习2

还没看的资料

微积分+泰勒+欧拉
积性函数通用筛法
学习FWT
min_max容斥
EI的多项式

需要学习/复习的算法：

• 轮廓线
• 悬线法dp
• 线性基 （只写了模板）
• 后缀自动机 （复习）
• 状压DP （复习）
• 插头DP
• 替罪羊树
• 笛卡尔树
• 斐波那契堆 （复习+练习）
• 左偏树 （复习+拓展）
• 网络流 （拓展）
• 2-SAT （复习）
• FFT&DFT （模板√）
• 杜教筛
• 莫比乌斯反演（模板√）
• 矩乘 （复习+拓展）
• 计算几何 （复习+拓展）
• exp
• 莫队（复习+二次离线）
• 模拟退火（模板√）（复习+拓展）
• AlphaBeta剪枝算法
• DLX
• DDP（动态DP）
• LCT （复习+拓展）
• 线性规划单纯形
• 点分治（习题）
• 点分树（习题）
• Min-Max容斥

Question

奇数码问题的充分性

关于取模

Notice

1. 写莫队的时候，如果要离散化注意要加原数组和修改，数组要开两倍
2. 异或出来的东西要开两倍
3. 我写过的莫队貌似都是不怎么考虑常数（除非分块大小），TLE了一般就是写炸了……
4. Splay的next查询操作不能返回val，要返回节点编号，否则kth里调用会错
5. SA有多组测试数据的时候不能用CLOCK（后果可想而知）
6. 初始化如果放到init里面，main要记得调用
7. 初始化不要乱移动位子，人家n还没读进来你循环个毛线
8. SegmentTree五问
9. 用了ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);之后就和scanf printf无缘了……切记
10. P1850 读题错误，保留两位（不用特殊处理看成了误差内即可）
11. 普通快乐如果除初始边以外要加边，开数组时要注意
12. 普通快乐Dijkstra用超级原点时不能加双向边，否则边权为0会T
13. 从时间复杂度得到的字符串奇技淫巧 scanf(“%[^\n]”, str)正则用法，读到回车；%*s可以空读字符串不存
14. UVA11019 Matrix Matcher，初始化顺序又犯了（见7）
15. uva1519,while ( scanf( "%d",&n)==1 && n )中 ==1不能删掉否则就T
16. 有些时候要考虑奇怪的建图（多次没想到了啊啊啊啊ONLINE也是） 撤离
17. 以后还是把快读当常规吧 尤其是用了vector的时候 survive
18. 死循环之前的输出，如果不加换行是没有输出的；别问为啥，问就是缓存。（换行作用相当于清缓存，如果你一直存着后面又恰好死循环当然会积压着没有输出）
19. #define lowbit(x) (x)&(-x) 这个东西不能乱用，最好还是自己写；别问为什么，问就是 x-lowbit(x) 优先级炸了woc。以前写树状数组都是 x-=lowbit(x) 所以丝毫没有意识到这个东西的严重性……啊啊啊啊
20. UVA1358有些东西前面处理了最好写一下……不然后面会忘
21. 主席树啊线段树啊啥的空间一定要开够啊……别再给我写错范围了（怒）惨痛教训
22. 关于溢出和取模的问题。gcd
23. 古老的并查集问题……依稀记得初一的时候一直不懂为啥不能这样写（最大团
24. 又被取模卡常了啊啊啊啊……c++取模是个屑 Holy Sequence
25. 组合数里 fac[0]=inv[0]=inv[1]=1 最好还是初始化掉……不然容易出问题
26. Jewel Splitting 要“瞻前顾后”啊……前面的 cons 如果单纯为了定义数组肯定没问题，但是后面还有 &cons .....

一些小trick

unsigned long long 的 hash技巧
ull nxt_rnd(ull a){a^=a<<15;a^=a>>17;a^=a<<19;return a^1923510;}

Save