一、知识点回顾
数学
1.如果题目里强调了数据的随机性，可以考虑算时间复杂度的期望值或算法正确的概率（NOI2021day2T1）
2.容斥原理分两种：子集容斥与代表元容斥（P2595多米诺骨牌）；代表元容斥实际上就是考虑最小的不满足条件的元素，令它前面是满足条件的，后面是任意放的，因为考虑的是最小的，所以不重不漏；还有一些题目是对某一条件容斥，对另一个条件\(DP\)。
3.二项式反演：看到恰好可以考虑二项式反演（钦定与恰好）
4.期望的线性性：考虑每一对可以产生贡献的概率，总和就是期望
5.拉格朗日插值：快速计算自然数幂和；优化DP，通常是通过观察DP数组的特殊性，考虑其差分是一个\(K-1\)次多项式，所以本身是一个\(K\)次多项式
6.逆元：若\(P\)是质数直接用费马小定理，若只满足\(a,P\)互质，要用欧拉定理
动态规划
1.状态设计：拆分数可以作为状态来得到一个亚指数级算法；树上选链问题考虑度数为状态；
2.转移：决策单调性的两种写法（分治法，二分队列法）；
图论
1.最小生成树建模：与连通性有关的（模拟赛题），与区间相关的（luogu，CF各有1题）；一个图的最小生成树等价于将图划分成若干个不交的边集，分别做最小生成树，最后将所有最小生成树上的边全拉出来再做一次最小生成树；
2.建虚点：在一些最短路、二分图、网络流模型中考虑
3.DFS树：在某些问题中考虑树的部分分后，DFS树对正解会有帮助
4.2-SAT：如果图是无向图直接用扩展域并查集即可
5.差分约束：很多题都是考虑前缀和数组满足的约束条件；如果求最小跑最长路，如果求最大跑最短路
6.三元环计数：可以用这个乱搞
数据结构
1.线段树可以维护的信息：树的直径；矩阵；最大子段和；
2.势能线段树：实际上就是某些不好维护的信息去暴力修改，同时要证明每一个数不会被修改太多次，常见的应用是区间开根，区间取\(\varphi\)，区间变成一个数的次幂（相逢是问候）
3.动态开点李超线段树的空间复杂度是线性的
4.并查集：启发式合并（图上启发式合并可以按边数合并）；删边困难就考虑加边
贪心
1.线段覆盖模型（最近刚做的一道CF，三种模型）
2.邻相交换（国王游戏）
3.合并法（Coloring the tree）
4.模拟费用流/反悔贪心：直接反悔当前最大值；每次考虑有哪些操作可以使总数+1，可以是直接操作，也可以是反悔（CF436E）；考虑建出费用流模型并模拟费用流，常见有线段树和堆；
构造
1.先考虑上界或下界，然后再构造相应的方案
2.先考虑简单的充分或必要条件，然后思考充要条件
3.分奇偶性考虑
4.利用异或的性质构造（多为三元组构造）
5.归纳构造
6.先考虑局部简单操作，再用类似的操作完成整体构造
7.欧拉回路、2-SAT、网络流等图论模型也可以解决一些构造
8.如果操作可逆，可以先考虑找出简单中间状态构造，再将操作逆回来
9.观察用题中所给操作时有哪些量是不变的
10.维护当前可能成为答案的量，最后再比较答案
11.二进制分组，组合数分组
12.逆序对有时会成为判无解的条件
13.考虑当前状态的一些特殊点构造（11.17模拟T2）
其它
1.二进制进位复杂度分析：令第\(i\)位进位次数为\(f_i\)，有\(a_i\)次执行在\(i\)位的\(+1\)操作，则\(f_i = \lfloor \frac{f_{i-1}\ +a_i}{2} \rfloor\)，所以每个\(a_i\)的贡献是\(O(a_i)\)的，复杂度就是\(O(\text{操作次数})\)
错误反思
模拟赛
1.要仔细读题，手玩样例是理解题意的好方式；否则可能会做不出来或浪费时间（1018模拟T3，CSPT3，1020模拟T2）
2.基本题一定不能失分，尤其如果第一题自己想了一个非常复杂的解法，一定要想一想有无更简便解法，因为一定是自己想烦了（1030模拟T1，1104模拟T1）
3.如果前面的题实在不会也不能死磕，要给每题（尤其前三题）留下充足思考时间（1030模拟）
4.想到一个做法一定要想清楚了再开始写，（分类讨论题可以先写），否则调代码会非常浪费时间（1030模拟T2）
5.每题至少留30min打部分分，否则可能会导致想好了很多部分分，最后却没拿到几个（1106模拟）
思考点
1.打表
2.分类讨论
3.交换求和顺序
4.DP覆盖模型
5.手玩样例
6.多个量转换
7.DP括号模型