读题读题再读题，观察观察再观察，手模手模再手模
别怕麻烦，遗漏关键性质会悔恨终生
退一步有时能够更好的进一步
杂项
-
一定按着某一标准划分阶段/部分来讨论，不要怕麻烦否则更容易走弯路
-
只要求部分“格式相同”的信息都可以用例如哈希/离散化的技巧将信息一般化后统一处理
-
注意是“分层”，“分步”还是几个情况并起来
-
括号序列经典套路：异或哈希，单调栈
-
前缀和/差分能够把区间信息转成单点信息，有时用来降维处理
-
冒泡排序轮数为 \(\max \sum \limits_{j = 1}^{i - 1} a_{j} > a_{i}\)，或者转成排列后为 \(\max{(i - p_{i})}\)
-
直接取高次幂相加可以使得哈希能被修改，不过容易冲突
贪心
-
反悔贪心一般考虑删除操作带来的贡献即可
-
考虑形如 \(a + b, a \times b\) 的排序而不是先 \(a\) 后 \(b\)，不过真是贪心可以推柿子得到
-
调整法是个好东西
\(Dp\)
-
据说贪心（不行就） \(\rightarrow\) \(Dp\)（不行就） \(\rightarrow\) （有些时候）网络流
-
考虑改变 \(Dp\) 顺序/换维/换根时是否更简单，有后效性则尝试建反图，正难则反
-
另外在合理条件下分配一个贡献的插入顺序可以让原本不能 \(Dp\) 的东西可以 \(Dp\)
-
看范围认类型，尤其记住状压是很明显的，不然就是折半搜索、
-
博弈论也可以 \(Dp\)，清楚必胜态/必败态即可，效果等价于 \(SG\) 函数
-
拆一个序列时考虑是否可以对其中一个/些集合贪心选择来让另一部分能尽可能范围更大
-
考虑信息能够扩展或合并的形式，多画转移矩阵
计数
-
状态与操作方案的映射很关键，基本上直接决定做法
-
容斥不一定要枚举完子集（\(O(n^{3})\)），也可以从每一层往前减完（\(O(n^{2})\)），或者只需要减去上一段的贡献
-
信息集合形成的“向量”一般提示偏序做法，考虑限制能否转成一些直线
-
从最终形态入手处理（加边 \(\rightarrow\) 删边），从较简单情况入手处理
-
贡献思想，转换对象，一个集合可以通过考虑其成员来映射（点不好处理就考虑边）
-
构造题，计数题一定要特殊考虑边界，时间复杂度一般允许暴力处理
优化
-
过而不及
-
构造矩阵时考虑将两代式子做差
-
\(pre\) 与 \(suf\) 有时是个好东西，统计/去重一定记得考虑
-
可重复贡献/可传递考虑倍增优化
-
错解不优，有时别想太多
-
可以二分的时候就可以考虑能否双指针扫了
-
平衡复杂度（根号分治，不同数据范围跑正确性不不一的做法），调一调参数就过了
-
决策单调性不是一定用在 \(Dp\)，也可以直接分治（类似整体二分）
树
-
基环树有美好的提示性作用，一般环上信息考虑断环为链或者建生成树再考虑非树边，不同的生成树要考虑的非树边种类不同
-
重心，直径端点等和“距离”，“子树大小”的题经常相关
-
考虑对边的两侧来讨论进行证明，可以简化不必要的信息
图及建模
-
支配对连边是个不错的选择，但要考虑是否全是偏序信息
-
最短路不确定当前抵达时刻时钦定当前为 \(0\) 分别往起点/终点跑
-
有特殊数量关系/偏序关系的边权可以尝试先贪心一部分来优化
-
“同色点”可以考虑建虚点或者直接连成环
-
分层图分开的是阶段
-
“地图”题目，不是转成序列或图论近似，就是构造或人类智慧
-
偏序的一些隐藏信息可以通过画示意图只管得到
数学与概期
-
老老实实先按题意列式子，组合意义化简，不要一来就想通过抽象意义或性质写简单柿子
-
打表出奇迹，该水的就不要证明（搜索也行）
-
向量点积、叉积出奇效（算面积）
-
\(lowbit\)，\(highbit\) 都是 \(log\) 级别的约数
-
取模下的答案可能需要 \(crt\) 合并每个简单情况的信息
-
拉插在能够证明递推式的次数上界时可以直接化简掉递推
-
广义的矩阵（\((min/max, +)\)）也符合结合律而不满足交换律，可以考虑维护树上/序列信息
-
概率可以考虑拆方案数，期望一般需要管“数量”
-
高维前缀和与容斥互为反演
-
中位数，平均数，方差仍然有它们的意义
-
带平方的柿子可能只有某些项与答案强相关
-
坐标变化可以转化成数学变化
-
容斥去掉一个边界利于化简柿子
数据结构
-
并查集 + \(+n\) 表示另一情况 = 扩展域并查集， + 到根的距离 \(\% p\) 刻画信息 = 带权并查集， + 按秩合并 = 可撤销并查集
-
扫描线是个好东西，离线一定可以去掉一维限制
-
考虑对于“种类”钦定，然后只有在/不在集合内的分组状态
-
位运算相关大多按位考虑，毕竟复杂度基本上会带 \(log\)，否则考虑 \(Trie\) 树上的合并过程找性质
-
点集较小时最少的能构成奇环的边数时可以线段树 + 并查集维护
-
序列信息不可合并时只能考虑离线之类的处理，实在不行只能随机化混分（指莫队，分块等）
-
\(DDp\) 的本质是利用矩阵简化 \(pushup\) 的过程
-
“区间线段覆盖”可以刻画多种信息（可行性，存在性，\(min/max \dots\)）
-
历史版本线段树的意义在于累计同一位置的贡献
-
按值域插入可以认为是在解决偏序，也可以认为是模拟链表
-
序列无非考虑长度、值域、离散程度、随机等方面，然后才是特殊的题面给出的性质，不要忘了考虑最基本的东西
-
某些特别的处理顺序下会让信息变得无需删除或可以通过删除抵消（指欧拉序，按深度等）
-
凸包就是一堆直线的集合，不一定需要李超树，可以直接分块 + 斜率维护
-
树状数组是把单点修改的影响前缀和到区间上，不是区间到区间