一、解题思路
1
需求：最大化最小值、最小化最大值
做法：二分答案
举例：一抓一大把
2
有些题可以从简单情况着手
然后拓展到复杂情况（数学归纳法或者总结经验、模仿）
或者先考虑普通情况，再考虑改进来解决特殊情况
举例：
noi2015 荷马史诗
poj2442 Sequence
平面几何，先研究三角形
3
研究原问题较复杂时，可能取补会让问题简单化
举例：
Ch6401 创世纪
各种组合数学题
4
各种拆点姿势：
按照时间等递增坐标
按照出度和入度
5
对于比较陌生的题目操作形式，可以多造几组数据来模拟，
找到一些性质，用这些性质转化题目为简单问题
6
对于某些有后效性的操作
把时间倒流或许会有帮助
举例：
【bzoj5040】航线规划【bzoj4229】选择
7
平方形式，可以转为为数点对，或者用二次项定理拆开来（内部有东西的时候）
举例：
NOI2009 管道取珠
蔬菜
8
目前碰到处理棘手的删除问题的方法主要有两个，基本都需要离线
一个是倒着做，这个对题目的要求较高
另一个是贪心，离线后按出现时间处理，然后按结束时间贪心
举例：
【bzoj4644】经典傻逼题【集训队互测2015】最大异或和
9
某些dp柿子等，含有组合数的变换时
可以利用组合数的性质优化、转移，例如组合数的递推式
举例：重返现世，有题解
关于动态点分治
点分树上，点对的LCA一定也在原树两点路径上
二、枚举方法
1
有关区间问题并用到区间最值，
求出l[i]和r[i]表示第一个比a[i]大的位置，
则l[i]+1~r[i]-1中间，用到的最大值都是a[i]
不过要小心最大值相等而重复的情况，可以强行把左边界改严格来限制
洛谷18年7月月赛T4
2
按照akc说的，碰到搜索，无脑倒序
举例：
poj1190 生日蛋糕
虫食算
3
当出现连续的$\lfloor \frac{n}{i} \rfloor$时，
值一定是单调不递增的，同值的区间可以合起来计算
复杂度：
$O(\sqrt n)$
① 当$i \leq \sqrt n$,分母只有$\sqrt n$种
② 当$i > \sqrt n$,$\lfloor \frac{n}{i} \rfloor < \sqrt n$
$last=\lfloor \frac{n}{ \lfloor \frac{n}{i} \rfloor } \rfloor$
举例：
CQOI2007 余数求和
大部分莫比乌斯题，如gdoi2018d2t1
4
对于许多计数类问题，如果有多个段可分，
可以分成1+(n-1)，这样子能保证不会重复计数
举例：
noi2001 陨石的秘密
5
很多计数问题要求排列
可以时刻保证排列性，然后插入一个数，将比它大的数+1
51nod1296 有限制的排列
6
设cnt(x)为x二进制下1的数量
$cnt(a \oplus b)$ 为奇，当且仅当一个cnt为奇，另一个是偶
因为两个1在一起是偶，不在一起也是偶
三、决策类
1
需求：维护前k个（方案）
做法：堆维护，堆顶为最差元素
举例：
K远点对
树上的路径
Supermarket
2
3
找前k优的区间，固定一个点后，左边的优秀情况是极值问题
可以用堆维护左边，取出一个位置后把左边区间拆成两半放回去
举例：
超级钢琴
树上的路径
四、搜索类
1
搜索去掉次序性的套路：强行限制大小关系
举例：
poj1011 Sticks
2
搜索的复杂度：
把每次决策量也就是分支数量计算出来
3
其他优化：
优化搜索顺序
排除等效的决策和物体
可行性
最优性
记忆化
4
对于一个序列，拆分成多个序列的问题
有两种不同的方向：
- 给每个元素分配组（通常这个更快）
- 通过组，找元素
最好能仔细根据题目斟酌一下策略
本人多次无脑用2各种剪枝，也比不过裸的1……
举例：
Sticks
Missile Defence System
Zebras5
50的整数拆分约为1e6，挺有用的
举例：[JLOI2012]时间流逝，有题解
五、数论技巧
1
面对gcd、lcm的限制条件，可以从质因数上考虑，
从而变成min、max，省去log暴力判断的复杂度
举例：
Hankson的趣味题
2
由调和级数
1+1/2+1/3…1/n=logn
3
如果要在中途，用一个简单的状态去尝试满足“成为某个数的倍数”
或者需要以此简便地转移
可以考虑只保留余数
举例：
Ahoi2009 同类分布
4
小定理：对于一个素数P，任何P以内的x，
其倍数在模P意义下可以表示出所有P以内的数
ps：原来这东西就是原根啊……
六、树
1
在一课树上，与该点最远的一定是直径的某个端点
2
两棵树合并起来，新的直径端点一定在两边直径端点中产生
3
一棵树上部分点的联通块个数=点-边
4
很多问题可以转化为树上问题，即不会有环，某一方向的结果唯一
举例：跳跳棋
七、字符串
1
后缀数组+离线+并查集
八、感觉很假的结论
1
直径的中心唯一
每个点的最远点，都一定经过直径的中心
2
1到n的集合，选若干个不互质的数，要求和最大
结论：每个数最多两个不同的质因子，且一个在根号内，一个在根号n外
九、完全不会证明的结论
1 树上路径，覆盖所有边
需要数量：$\lceil \frac{度=1的点数量}{2} \rceil$
十、自己容易犯的sb错误
1
cmp函数不能在结构体内部
2
对于一道题意不裸的题，都应该用样例检验没有看错题、想出来算法的基本正确性，再去code
3
标准差是方差的算术平方根，所以说所谓方差是不需要开根的
4
不等式的移项一定要分析正负性
5
stl的比较重载不能随便搞，一定要满足传递性和大小情况单一性（stl用<和>推导出=）
6
fft等，得答案时要round
7
带取模计数dp，判无解不能用答案=0，因为答案可能是模数的倍数
8
曾经对拍几小时，以为超稳……
后来挂惨才发现没有srand
