省选常见模型

数论:

  • 线性筛 1
  • 概率论(期望) 4
  • 组合计数(卡特兰数) 5
  • Lucas定理 1
  • 费马小定理 1
  • 莫比乌斯反演 2
  • 欧拉函数 1
  • 推式子 7
  • 矩阵快速幂 3
  • 矩阵树 2
  • 容斥 3
  • 生成函数 2
  • 斐波那契数列 2
  • 高斯消元 2
  • FWT 1

图论:

  • LCT 2
  • 二分图:
  1. 二分图完备匹配(KM) 4
  2. 二分图匹配(匈牙利算法) 2
  3. 二分图最大独立集(Dinic) 1
  4. DAG最小路径覆盖 1
  • 树链剖分 3
  • 点分治 2
  • 圆方树 3
  • 拓扑排序 2
  • 最短路径生成树 1
  • Dijkstra 1
  • 最小生成树 1
  • 树的直径 1
  • 最小费用流 1
  • 树上差分 5
  • LCA 5
  • 2-SAT 1

数据结构:

  • 分块 3
  • 莫队 2
  • 单调栈 3
  • 并查集维护连通性 3
  • 堆 1
  • 权值线段树 1
  • 主席树 2
  • 线段树 7
  • KD tree 3
  • 平衡树 5
  • 可持久化trie树 3
  • 差分数组 3
  • 启发式合并 2
  • 线段树合并 1

字符串:

  • SAM 4
  • AC自动机 1
  • 后缀自动机 1

搜索:

  • BFS/(预处理) 2
  • 枚举 1
  • DFS 1
  • 对抗搜索 1

分治:

  • 三分 1
  • 二分 2
  • 线段树分治 3

计算几何:

  • 最小圆覆盖问题 3
  • 基本操作 3
  • 半平面交 2

动态规划:

  • 树形DP 7
  • 线性DP 4
  • DP套DP 3
  • 状压DP 4
  • 数位DP 2
  • 动态DP 2
  • 字符串上DP 3
  • 背包DP/思想 6
  • 二进制划分 2
  • 单调队列优化DP 1

模拟:

  • 扫描线 4
  • 2*n的格子 3

STL:

  • set 5

特殊技巧:

  • 模型转换 1
  1. 可行路径距不可行点的最大值 ==》二分不可行点与路径距离+BFS(P2498 拯救小云公主) 1
  2. 多条件 ==》 少条件 ==》 多条件  1
  3. 第k大 ==》 二分+判定性问题
  4. 棋盘/矩阵 ==》 黑白染色 ==》 二分图匹配
  5. 正难则反 2
  6. 复杂条件 ==》 部分简单条件 ==》 逐一求解
  7. 子树查询 ==》 DFS序列 2
  • 推性质 3
  • 相乘计数 1
  • 几何形状转无向图 1
  • 双指针 3
  • 倒序DP 1
  • 多状态DP+0/1表示状态 3
  • 预处理/维护 左/右端点 3
  • 图上缩点 1
  • 拆点 2
  • 线段树维护最大连续子段 1
  • 异或前缀和 1
  • 线段树分治 2
  • 贪心 4
  • 题意 ==》 挖掘性质 2
  • 按时间为轴 2
  • 矩阵快速幂优化递推 3

读题:1.找关键词 2.翻译

教程地址:

SAM:https://ouuan.github.io/%E5%90%8E%E7%BC%80%E8%87%AA%E5%8A%A8%E6%9C%BA%EF%BC%88SAM%EF%BC%89%E5%AD%A6%E4%B9%A0%E7%AC%94%E8%AE%B0/#%E7%A1%AE%E5%AE%9A%E6%9C%89%E9%99%90%E7%8A%B6%E6%80%81%E8%87%AA%E5%8A%A8%E6%9C%BA%EF%BC%88DFA%EF%BC%89

https://blog.csdn.net/weixin_43973966/article/details/85338266

Matrix-Tree 算法

矩阵树定理

生成函数:https://www.luogu.org/blog/ShadowassIIXVIIIIV/sheng-cheng-han-shuo-xia-chui

例题:

线段树分治:https://www.lydsy.com/JudgeOnline/problem.php?id=4025

原文地址:https://www.cnblogs.com/zbsy-wwx/p/11680590.html