最后的诗篇。

做题的套路

多读题多读题多读题！！一道题至少连带样例读三遍
注意形如 a_i \bmod a_{i + 1} = 0,a_{i+1} > a_i 这样的条件转化，往往把大问题缩小成小问题
注意特殊性质！！不要过度抽象问题从而挑战 NPC
二分别写挂。。。。
二分一个值判断是否合法，经常把 >x 设为 1，< x 设为 -1。
倍增能处理很多事情！很重要。
ST 表不一定是区间最值，通过一些魔改也可以处理其他问题，猫树这种东西就算了（
中位数 \leq x 这个限制相当于 >x 的数不超过 \frac{len}{2} 个.
约数问题如果数太大，考虑从唯一分解定理的角度的 p_i 考虑问题，\gcd 就变成求交，\operatorname{lcm} 就变成求并
考察题目如果有很强的两边可以分开考虑的性质，就优先分开考虑。
如果是字符串相关问题，优先考虑这个问题是不是和 LCP 有一定关系。如果有是好事，可以二分+Hash来解决。
区间问题观察值域，如果值域不大可以考虑在值域上 DP 之类的来解决。

图论

经典套路

对于一些特殊的建图（e.g. 若 a_x | a_y 则有边 (x,y,val)）这种边数起飞的情况，我们通常两种考虑思路：
- 一个等效建边的思想，即如果 (x,z) 与 (y,z) 同时建出，但是实际上与只建 (x,z) 效果是一样的，那么我们可以通过只建具有“代表性”的边来优化建边条数。通常在一些连通性问题中这么考虑
- 建虚点，通过对边权转化来达到相同的效果。比如这个题ZR#2455
  
  n 个点 m 条边的有向图，每个点 x 都有一个权值 v_x，每条边的长度均为 1。
  
  如果顶点 x 和 y 满足 v_x\operatorname{and} v_y=v_y ，则增加一条从 x 到 y 的有向边。
  
  现在想知道从 1 号顶点出发，到其他所有顶点的最短路径的长度。
  
  1\le n\le 200000,1\le m\le 300000
  
  这个题暴力做最坏就是一个完全图，可以新增 2^{20} 个点，这些点中所有点向它所有的子集连一条长度为 0 的有向边。
  
  对于原来的所有点 x，向 v_x 连一条长度为 1 的边，然后 v_x 向这个点连 0 的边。由于边权只有 0 和 1，所以仍然可以 BFS，每次要把用 0 的边连接的所有点都加入队尾，以保证距离不降。
  
  这样的时间复杂度是 \mathcal{O}(3^{20} + n + m)。但是可以发现对于新增的 2^{20} 个点 x，只需要向 x 去掉某一位的 1 的点连边。这样的话，时间复杂度就可以变成 \mathcal{O}(20 · 2^{20} + n + m)。
矩阵转移

例如像 NOI2020 美食家以及 NOI Online #3魔法值这种题，一般是 n 可以支持 n^3，而且询问的次数特别大的时候。挺套路的一个东西，证明一下题目中所求的东西是否满足结合律就可以了。

要注意这种题的快速幂往往是先把转移矩阵 F 的幂求出来，然后再用向量乘矩阵的 n^2 来保证复杂度正确。
分层图

也是套路化的东西，不再赘述。

最小生成树

关于 MST 有一些非常经典的性质与推论，可以启发思考。

性质 1：对于一条非树边 (x,y)，树上 x\to y 上边的最大值的权值小于等于非树边的权值

证明：反证法。考虑 (x,y) 加进去会和 x\to y 路径构成一个环，那么如果 w_{(x,y)} < 环上任意一条边的权值，根据定义 (x,y) 必须在最小生成树上，与定义不符，故得证。

做这类题的时候不要拘泥于 Kruskal，有时候 Prim 和 Boruvka 有奇效。

Kruskal 重构树

这个东西解决的问题比较抽象一点，和生成树本身没啥关系了，具体可以看之前我写的 blog.

最短路

就是几种算法：SPFA，Dijkstra,Floyd

注意如果只是求传递闭包的话 Floyd 记得用 bitset:

// std::bitset<SIZE> f[SIZE];
for (k = 1; k <= n; k++)
  for (i = 1; i <= n; i++)
    if (f[i][k]) f[i] = f[i] | f[k];

然后如果边权特殊的图注意能不能 01 bfs，也就是队头 push 0,队尾 push 1。

连通性问题

咕咕，赌他不考

欧拉回路类问题

首先板子要记住，用一个类似当前弧优化的东西才能保证复杂度不退化到 \mathcal{O}(nm).

vector <pii> G[N];
vector <int> ans;
int n,m,tot,d1[N],d2[N],cur[N];
bool vis[N];

void dfs(int x) {
    for (int &i = cur[x];i < G[x].size();++i) {
        pii &e = G[x][i];
        int y = e.first;
        if (!e.second) {
            e.second = 1;
            dfs(y);
        }
    }
    ans.push_back(x);
}

signed main() {
    read(n,m);
    for (int i = 1;i <= m;++i) {
        int x,y;read(x,y);
        G[x].push_back(mp(y,0));
        d1[x]++,d2[y]++;
    }
    for (int i = 1;i <= n;++i) sort(G[i].begin(),G[i].end());
    bool flag = 1;
    int cnt1 = 0,cnt2 = 0,s = 1;
    for (int i = 1;i <= n;++i) {
        if (d1[i] != d2[i]) flag = 0;
        if (d1[i] - d2[i] == 1)++cnt1,s = i;
        if (d2[i] - d1[i] == 1)++cnt2;
    }
    if (!flag && !(cnt1 == 1 && cnt2 == 1)) {
        puts("No");
        return 0;
    }
    dfs(s);
    reverse(ans.begin(),ans.end());
    for (auto x : ans) printf("%d ",x);
    return 0;
}

这类问题难点在于抽象出欧拉回路的模型。例如这个题

你有 n 个二元组，第 i 个二元组的值为 (a,b) 。任意两个二元组都不相同。

求是否存在一个二元组的排列，使得这些二元组满足对于任意 1≤i<n ，有 A_i=A_{i+1} 或 B_i=B_{i+1} 。且对于任意 2≤i<n ，A_{i−1}=A_i=A_{i+1} 和 B_{i−1}=B_i=B_{i+1} 都不成立。

如果有解，你还需要找到字典序最小的解。我们认为一个二元组的字典序更小，当且仅当这个二元组在输入中更早出现。

n \leq 5\times 10^5

这个题最厉害的在于，把 (a,b) 看作边，然后把 A,B 当作点建图，这样建出来是一张二分图。而我们要找的就是这张二分图的一条欧拉路径。欧拉路径和欧拉通路的差距就在于起点不同，所以直接找就行。

基环树

NOIP 考过的东西……感觉找环很重要！Mark 一个

int to[N<<1],nxt[N<<1],hd[N],tot = 1;
inline void add(int x,int y) {to[++tot] = y;nxt[tot] = hd[x];hd[x] = tot;}
inline void addedge(int x,int y) {add(x,y);add(y,x);}
ll a[N],n,l,r,f[N][2],ans,e;
void findcir(int x,int f) {
    vis[x] = 1;
    for (int i = hd[x];i;i = nxt[i]){
        int y = to[i];
        if (y != f) {
            if (!vis[y]) findcir(y,x);
            else {
                l = x,r = y;e = i;
            }
        }
    }
}
ll DP(int x,int fa) {
    for (int i = hd[x];i;i = nxt[i]) {
        int y = to[i];
        if (y != fa && i != e && (i ^ 1) != e) {
            DP(y,x);
        }
    }
    return 0；
}

大概只需要找出环中间的那条边，然后就可以开搞啦！如果有必要的话可以记录一下每个点的父亲，然后递归回去。

基环树的问题大部分都是先想一颗树上要怎么做，然后再把这个问题放到环上来考虑。

常用有两种套路：

断环

例如 ZJOI2008 骑士这个题就是枚举环上的每条边，然后断开这条边进行 DP。我实现的比较暴力就直接每次都断开来思考了。
分类讨论

例如 IOI2008 Island，暴力找环，树上 DP，环上拆链 DP。

二分图网络流

不做额外复习，参考NOI 一轮复习 I：二分图网络流 - ix35

动态规划

DP 三要素

状态，决策和转移。其中 “状态” 又最为关键，决策最为复杂。这三点直接决定了一个 DP 的好坏。

“状态” 的优化可以从很多角度出发，思维难度及其高，有时候状态选择的好坏会直接导致出现暴零和满分的分化。

“决策” 优化则有着大量模板化的东西，相对考察选手码力。

线性 DP

如果某个维度（例如读入顺序）上 DP 特别难做，考虑换一个角度（例如在值域上）进行 DP。

一定要注意把 DP 的式子写出来！然后再考虑怎么上优化。

1D 的 DP

因为状态一般简化，所以我们从决策的角度来考虑如何优化

f_x = \max\limits_{l_x\leq y\leq r_x} \{f_y\} + val_x
- 如果相邻状态的段的左右区间满足非降的关系，那么可以直接上单调队列做到均摊 \mathcal{O}(1)，总时间复杂度 \mathcal{O}(n) 的东西
- 如果区间没有特别的关系，但是满足 r_x \leq x 那么可以把 f 拍到线段树上来进行转移，这样就做到单次 \mathcal{O}(\log n) 总时间复杂度 \mathcal{O}(n\log n)
f_x = \sum\limits_{y = l_x}^{r_x} f_y
- 一般考虑维护一个 g_x = \sum\limits_{y = 1}^x f_y 来进行前缀和优化。

2D 的DP

这类题目就复杂很多，通常两个方面入手。

状态能否优化？

这主要考虑的是我们状态有没有表示出正确的东西，如果换一个角度来表示就会好很多。这个东西好像很智商（

或者我们另一个角度考虑，我们能否把一些比较好求的东西求出来，换一个方式 DP？
一道题：

我们定义一个整数序列是好的当且仅当
- \forall 1 \leq i \leq n,1 \leq a_i \leq m
- \forall 1 \leq i < n 有以下两个条件至少成立一个：
  - a_i \le a_{i+1}
  - (a_i \bmod a_{i+1}) > 0
求有多少个序列是好的。 n,m\leq 10^5
我们很容易设计出暴力 DP，即 f_{i,j} 表示第 i 位选 j 的方案数，暴力转移是 \mathcal{O}(nm\log m) 的。

发现转移基本上没啥可以优化的点了，但是我们发现，我们从反面考察，两个都不成立的就是：a_i > a_{i + 1},a_i\bmod a_{i+1} = 0 。我们考虑这个序列的长度实际上很短，最长只有 \log n 级别的。所以我们考虑容斥，预处理出 g_i 表示长度为 i 的不合法子串，然后转移就变成了
f_i = \sum (-1)^{len} g_{len}\times f_{i - len}
这样做到了 \mathcal{O}(n\log^2 m)。
转移能否优化？

这类的方法和 1D 类似。

区间 DP

咕咕。

树形 DP

树上背包

不再赘述，本质上看成一个 (\min,+) 卷积转移就可以做到 \mathcal{O}(n^2)

DS

讲道理，感觉 NOIP 并没有很显式的考察某种 DS。最多就是扫描线之类的问题（奶）。

ST 表

需要注意的大概是建表的时候第二层循环的写法：

NOIP 复习