# 蓝桥杯基本路线
## 搜索
- A\*/IDA\*
- IDDFS的重要问题是每层搜索量大，因此使用类似A\*的启发式方法找到剪枝策略（往往是深度相关的）
- 而A\*主要解决搜索路径上的启发式优先级问题，可以是在DFS里根据分支情况的优劣先选择较优分支，也可以是在BFS里把普通队列换成优先队列。
- 双向BFS
```cpp
int st[2], ed[2];
int step1[N][N];
int step2[N][N];
// 先特判起终点一致的情况
if (st[0] == ed[0] && st[1] == ed[1]) {
// ...
}
// 然后初始化队列
queue<node> q1, q2;
step1[st[0]][st[1]] = 0;
q1.push(node(st[0], st[1]));
step2[ed[0]][ed[1]] = 0;
q2.push(node(ed[0], ed[1]));
int result = -1;
while(result == -1 && (!q1.empty() || !q2.empty())) {
if (!q1.empty()) {
// q1上带有step1和step2碰撞检测的一步BFS，以result为结束...
}
if (result != -1) break;
if (!q2.empty()) {
// q2上带有step1和step2碰撞检测的一步BFS，以result为结束...
}
}
```
- 拓扑排序：记录入度，遍历一个节点就把其连接的节点入度-1，循环+深度遍历所有入度为0的节点即可。
## 数据结构
- 并查集
```cpp
int parent[N] = {0};
int find(int x) {
int t = x, p;
while(parent[t] != t) t = parent[t];
while(x != t) {
p = parent[x];
parent[x] = t;
x = p;
}
return t;
}
void merge(int a, int b) {
parent[find(b)] = find(a);
}
```
- 树状数组
- 树状数组维护的是前缀和。如果从时间序列角度来考虑加减法事件的发生，可以形成一个差分前缀和，以此来解决区间加减法更新问题，即只在区间更新开始位置加差分值，在区间结束位置减差分值，只更新两个点而非区间上每个点。最终某位置的差分值就是该位置的前缀和
```cpp
#define lowbit(x) ((x) & (-x))
int n; ll diff[N] = {0};
void add(int x, ll k) {
while (x <= n) {
diff[x] += k;
x += lowbit(x);
}
}
ll prefix(int x) {
ll s = diff[x];
while(x -= lowbit(x))
s += diff[x];
return s;
}
```
- 线段树
- Splay
## 动态规划
- 背包 poj1170
- LCS poj1080
- 状压 poj 1185
- 区间 poj 2955
- 树形 poj 3107
- 数位 hdu 6148
## 图论
- 树链剖分
## 数学
- 手工加减进退位
- GCD/LCM
- 同余/逆元/extgcd
- 快速幂/矩阵快速幂 poj 3070 hdu 6030 hdu 5564
- 进制转换/多进制状压
- 公平组合游戏
- 前提是局面没有角色信息，且局面逐渐收敛
- N/P位置
- P位置：先手必输位置（前一玩家必赢）
- N位置：先手必赢位置（当前玩家必赢）
- 从0状态开始推，每个状态在下一步都可达之前的状态，因此每个状态都可以推出是P位置或N位置，找规律或按动态规划求解
- 一个状态只可达N位置，则该位置为P位置（因为对手会到达N位置）
- 一个状态只可达P位置，则该位置为N位置（同上）
- 一个状态N和P都可达，则该位置为N位置（因为取最优决策会让对手到达P位置）
- 尼姆游戏
- 从n个放置了不同个数{a1..an}物品的堆中，每个玩家每次可以从一个堆拿走任意个数的物品，最后没有物品可拿的输
- 解法：a1连异或到an，得res，如果res=0则先手输，res≠0则先手赢
- 先手如果赢（res不为0），求第一步可行的方案数：对每一堆i，如果res异或ai（等价于从res中去掉ai）后的结果小于ai，则意味着可以通过将ai减小来使得新的res为0即让对手必输，统计满足条件的堆个数
- 组合数/排列数
- P(n, m)是从n递减乘m个
- C(n, m)是从n递减乘m个，再除以m的阶乘
- 母函数
- 各种独立事件的可能选择的母函数乘起来，x的系数就是加起来的，x^n的系数代表了共发生n个事件选择时的情况数
- 编程时可以找到这个乘积，直接用多项式乘法手写，也可以进一步推导：
- 
- 
- 记住$\sum_{i\ge0}x^n=\frac1{1-x}$，如果只需要前k项（含1）就是这个再减去$\sum_{i\ge k}x^i=\frac{x^{k}}{1-x}$
- 卡特兰数
- 若有两种不同事件各可选择无限次，一种事件的发生个数在一个时刻必须比另一个多或者恰好相等，则这样的排列数构成卡特兰数
- 
- 
- 
- 容斥
- 对重复的集合，先加单元素集合再减双元素集合再加三元素集合，一直到全集。
- x 斯特林数
- x 康托展开快速判重
## 字符串
- 字典树
- KMP：直接背：
```cpp
int next[N] = {0};
void getFail(string p) {
for(int i = 0; i < p.length(); i++) {
int j = next[i];
while(p[i] != p[j] && j) j = next[j];
if(p[i] == p[j]) next[i+1] = j+1;
}
}
bool KMP(string s, string p) {
int j = 0;
getFail(p);
for(int i = 0; i < s.length(); i++) {
while(s[i] != p[j]) j = next[j];
if (s[i] == p[j]) j++;
if (j == p.length()) return true;
}
return false;
}
```
- x AC自动机
- x 后缀数组
![]()