7.Hash表哈希表的作用：把一个比较大的空间，通过一个函数映射到一个比较小的空间。 一般做哈希运算时，取一个质数作为模，会使得冲突的概率降低 哈希表的冲突解决方法： 拉链法 开放寻址法 AcWing 840.模拟散列表（1）拉链法创建一个数...

（一）数论1.质数 对所有的大于1的自然数字，定义了【质数/合数】这一概念。对于所有小于等于1的自然数，没有这个概念，它们既不是质数也不是合数。 质数的定义：对于大于1的自然数，如果这个数的约数只包含1和它本身，则这个数被称为质数，或者素数...

（四）容斥原理先不考虑重叠的情况，把包含于某内容中的所有对象的数目先计算出来，然后再把计数时重复计算的数目排斥出去，使得计算的结果既无遗漏又无重复，这种计数的方法称为容斥原理。 以S1,S2,S3三个集合为例，求出三个集合中包含的元素个数，可以通过韦...

（五）简单博弈论公平组合游戏ICG 若一个游戏满足： 由两名玩家交替行动； 在游戏进程的任意时刻； 可以执行的合法行动与轮到哪名玩家无关； 不能行动的玩家判负； 则称该游戏为一个公平组合游戏。 NIM博弈属于公平组合游戏，但城建的棋类游戏，比如围...

3.区间DPAcWing 282. 石子合并实现思路： f(i,j)表示将第i堆到第j堆石子合并为一堆时的最小代价 状态划分：选一个分割点k，将ik，k+1j这两个堆（两个区间）的石子合并，然后加上两个区间堆的总合并代价（采用前缀和计算区间i到j...

2.线性DP状态转移方程呈现出一种线性的递推形式的DP，我们将其称为线性DP。 （一）数字三角形AcWing 898. 数字三角形实现思路： 对这个三角形中的数字进行编号，状态表示依然可以用二维表示，即f(i,j)，i表示横坐标（横线），j表示纵坐...

4.计数类DPAcWing 900. 整数划分实现思路：本题求的是方案个数，而不要求方案顺序，即4=1+1+2 和4=1+2+1是一样的 （1）方案一：转化为完全背包做法。将正整数n看做是背包容量，而1~n之间的数看做是物品，且各...

5.数位统计DPAcWing 338. 计数问题实现思路： 定义函数：count(n,x)，其表示在1到n中，x出现的次数（x是0-9） 那么，可以用类似前缀和的思想，来求解a到b中，x出现的次数：count(b,x) - count(a-1,x)...

6.状态压缩DP将一个十进制的整数转化为二进制数，每一位表示一种状态 AcWing 291. 蒙德里安的梦想实现思路：先放横着的，再放竖着的。 总方案数，等于只放横着的小方块的合法方案数。（放完横着的方块之后，竖着的只能被动填充进去，不需要额外进行竖...

7.树形DPAcWing 285. 没有上司的舞会实现思路：所求即为从一棵中选出一个结点集合其各结点的值之和最大，且这个结点集合中都没有这些结点的父节点存在（没有父亲，只有同辈或者隔辈） 状态表示：利用递归 f(u, 0)：从所有以u为根结点的子树...