目录
笔记整理
计划
要学的东西
缺省源
要做的题
搜索
高斯消元
矩阵
排列组合
2019.7.9
2019.7.10 kmp ac自动机
2019.7.11
2019.7.15
省选知识点（by千年之狐_天才）
笔记整理
1.同余and乘法逆元学习笔记
2.排列组合学习笔记
3.字符串Hash学习笔记
4.树状数组学习笔记
5.线段树学习笔记
6.ST表学习笔记
7.树形DP学习笔记
8.位运算学习笔记
9.二分答案学习笔记 还没写 ,咕咕咕
10.区间dp学习笔记 待更新例题
11.背包问题
12.STL学习笔记
13.字典树(Trie)学习笔记
14.浅谈LCA
15.前缀和/差分笔记未完...
16.简单数学
17.数据结构
18.出题用的奇怪的东西
19.浅谈扩展中国剩余定理
计划
待更新
要学的东西
待更新
缺省源
#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cmath>
#include<queue>
#include<stack>
#include<vector>
#include<map>
#include<string>
#include<cstring>
using namespace std;
inline int read() {
char c = getchar();
int x = 0, f = 1;
while(c < '0' || c > '9') {
if(c == '-') f = -1;
c = getchar();
}
while(c >= '0' && c <= '9') x = x * 10 + c - '0', c = getchar();
return x * f;
}
int main()
{
return 0;
}
要做的题
搜索
简单搜索：
Codevs 1018 单词接龙
Codevs 1049 棋盘染色
Codevs 1976 Queen数列
Codevs 1099 字串变换
Codevs 1569 最佳绿草
洛谷P2534 [AHOI2012]铁盘整理
中等搜索：
洛谷P1031 均分纸牌
洛谷P1556 幸福的路
锻炼代码能力的搜索：
洛谷P2243 电路维修
洛谷P2730 魔板 Magic Squares
洛谷P1312 Mayan游戏
洛谷P1092 虫食算
记忆化搜索：
洛谷P2921 [USACO08DEC]在农场万圣节Trick or Treat on the Farm
洛谷P2530 [SHOI2001]化工厂装箱员
剪枝：
洛谷P1120 小木棍 ［数据加强版］
Codevs 2144 砝码称重 2
迭代加深：
洛谷P2534 [AHOI2012]铁盘整理
Codevs 1049 棋盘染色
双向宽搜：
仍然是八数码难题
高斯消元
POJ 1222 EXTENDED LIGHTS OUT
POJ 1681 Painter's Problem
POJ 1753 Flip Game
POJ 1830 开关问题
POJ 3185 The Water Bowls
POJ 2947 Widget Factory
POJ 1166 The Clocks
POJ 2065 SETI
POJ 1487 Single-Player Games
hdu 2449 Gauss Elimination
FZU 1704 Turn off the light
Sgu 275 To xor or not to xor
矩阵
1281 Xn数列
2314 数学作业
bzoj /luogu 1875: [SDOI2009]HH去散步
bzoj 2161: 布娃娃
排列组合
各种放球问题
BZOJ 4403 序列统计
P2606 [ZJOI2010]排列计数
poj1850
codevs 3693
2019.7.9
青蛙的约会
P2158 [SDOI2008]仪仗队
poj 1845
BZOJ 2386
bzoj 4517
codevs1141
uva11357
洛谷3197
luogu P1072 Hankson 的趣味题
2019.7.10 kmp ac自动机
上午的题没统计等做到的时候在写吧
loj 103 子串查找
HDU 2594 Simpsons' Hidden Talents
POJ 2185 Milking Grid
luogu P2353 背单词
luogu P3808 【模板】AC自动机（简单版）
luogu AC自动机加强版
2019.7.11
P2353 背单词
HDU 2594
P4052 [JSOI2007]文本生成器
bzoj 1787
[JSOI2010]Group 部落划分 Group
2019.7.15
loj507
省选知识点（by千年之狐_天才）
### 为冲刺省队的人准备的知识清点。（同一板块按顺序进行，但不一定要严格按顺序，毕竟我好久没摸OI了，顺序仅供参考。不同板块根据个人喜好进行学习？）
注：基础知识点大部分仍在列表中。部分重点单独拿出来了。
注2：有部分知识点没列出来可能因为我太懒了，所以没列。
未完待续...
## 1. 数据结构
- 树状数组
- 线段树
- 主席树
- 并查集
- 重链剖分（树剖）
- 堆
- 左偏树（可并堆）
- 单调队列
- 栈
- 替罪羊树
- FHQ-treap
- splay
- 线段树合并
- splay启发式合并
- LCT
- lca(LCT求lca,其余还有哪些以后补充)
- 长链剖分
- 树套树（各种基本都要会）
- K-D Tree
- 莫队:
(1)普通莫队
(2)回滚莫队
(3)树上莫队
(4)带修莫队
(5)带修树上莫队
- 李超树
- 吉司林线段树
- Leafy_Tree(不推荐吧)
- 各种可持久化(fhq-treap,leafy-treap,tire树)
- ETT?(不建议学)
## 2.字符串：
- hash
- tire树
- KMP
- AC自动机
- Manacher
- 后缀数组SA
- 后缀自动机SAM
- 后缀树
- 回文自动机PAM
- 序列自动机
- 后缀平衡树(作用不大吧？)
## 3.图论：
- 强联通
- 树上差分
- 拓扑排序
- 最小生成树
- kruskal重构树
- 最短路算法
(1)dijkstra(双向优化不做要求)
(2)floyd
(3)spfa(最好是会一种到两种优化,有时可以用来网络流卡时)
- 最短路树
- 差分约束
- A*算法(实际上可以放前面)
- 分层图
- 割点和桥
- 记忆化搜索
- 剪枝碾标算
- 欧拉回路
- 树上倍增优化建图
- 线段树优化建图
- 一些我忘了的优化建图？
- 基环树
- 2-SAT
- 斯坦纳树
- 网络流
(0)一堆性质定理(我只记得个Dilworth定理了)
(1)最大流:Dinic,ISAP
(2)最小割
(3)费用流(zkw费用流有时跑得很快，但一般都用Dinic的费用流)
(4)上下界网络流
(5)最小割树
(6)HLPP（很强的话再学，反正基本用不上）
- 圆方树
- 虚树(重头戏，可以有很多变形。如：虚树+SAM,虚树+边分治，虚树+线段树分治，虚树+dp+边分治+...)
## 3.数论
- 反演单独拿出来
- 需要一定数学基础
- χ函数(简要了解？跳过也行)
- 乘法逆元
- 斐蜀定理
- 欧拉定理，函数
- 费马大定理（有必要了解）
- 高斯消元
- 矩阵树
- 卡特兰数
- BSGS
- 扩展中国剩余定理
- 博弈论
- 拉格朗日插值法
- 各种各样的容斥
- 生成函数（重点！）
- 泰勒公式
- 自适应性Simpson（好玩用）
- 组合计数（Lucas,Polya,Burnside,错拍等）
- 质因数分解+质数判定（Pollard's rho,Miller-Rabin）（不推荐学吧）
- 傅里叶级数(高数，不建议在NOI前学习)
## 4.分治
- CDQ分治
- 线段树分治
- 点分治
- 边分治
- 点分树
- 启发式分治（貌似我也忘了干嘛的）
- 根号分治
- 多限制分块
## 5.多项式
- 学了总比不学好，就算可能不考
- FFT
- NTT
- 多项式全家桶(乘法，除法，求逆，指数，求导，求原，求ln,等等)
- 常系数齐次线性递推（两种，一种写起来很麻烦但是快，另一种写起来挺简单而且也较快,比矩阵乘法快多了，推荐后者，前者可用于卡时）
- MTT
- 分治NTT
- FWT（最好学）
- FST（最好学）
- FMT（最好学）
- 斯特林数第一类、第二类用多项式的求法。（不学没影响吧，建议不学吧）
## 6.反演
- 二项式反演
- 狄利克雷卷积
- 莫比乌斯反演（重头戏）
- 杜教筛
- Min_25筛（划重点）
- 斯特林反演（用处不太大，没碰到多少题）
## 7.动态规划
- 背包
- 静态DP
状压DP、贪心+DP、区间DP、插头DP、期望DP、字符串DP、斜率优化、线段树优化、决策单调性优化、单调队列优化、矩阵优化、四边形不等式优化（懒得按照顺序来）
- 动态DP
LCT维护即可
## 8.分块
- 最好请教lxl qwq
- 我太蔡了，没学多少分块（学的时候忘了分类，现在AFO了也不好写出知识点了qwq）
## 9.计算几何
- 凸包
- 旋转卡壳
- 半平面交
- 最小圆覆盖
- 闵科夫斯基和
## 10.矩阵乘法
- 矩阵优化做题（可用多项式炒鸡优化）
- 预处理矩阵
- 矩阵求逆
## 11.线性基
- 与其他数据结构混用，如某某分治+线性基等
- 可撤销线性基（也许没记错名字吧）
## 12.压位
- 混分必备
## 13.树上凸包
## 14.扫描线
## 15.并查集
- 普通并查集
- 带权并查集
- 可撤销并查集
## 16.二分
- 二分答案（题目是真的多）
- 0/1分数规划
- 二分套一堆数据结构
- 整体二分（同样可以套一堆数据结构）
## 17.Berlekamp-Massey算法
- 暴力找递推关系。（可学可不学）
## 18.随机化
- 随机化贪心
- 爬山算法
- 模拟退火
- 本人自创随机化算法，暂不外泄
