最后的诗篇。

做题的套路

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

图论

经典套路

  1. 对于一些特殊的建图(e.g. 若 a_x | a_y 则有边 (x,y,val))这种边数起飞的情况,我们通常两种考虑思路:

    • 一个等效建边的思想,即如果 (x,z)(y,z) 同时建出,但是实际上与只建 (x,z) 效果是一样的,那么我们可以通过只建具有“代表性”的边来优化建边条数。通常在一些连通性问题中这么考虑

    • 建虚点,通过对边权转化来达到相同的效果。比如这个题ZR#2455

      n 个点 m 条边的有向图,每个点 x 都有一个权值 v_x,每条边的长度均为 1

      如果顶点 xy 满足 v_x\operatorname{and} v_y=v_y ,则增加一条从 xy 的有向边。

      现在想知道从 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)

  2. 矩阵转移

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

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

  3. 分层图

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

最小生成树

关于 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<nA_{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;
}

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

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

常用有两种套路:

  1. 断环

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

  2. 分类讨论

    例如 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

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

  1. 状态能否优化?

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

    或者我们另一个角度考虑,我们能否把一些比较好求的东西求出来,换一个方式 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)

  2. 转移能否优化?

    这类的方法和 1D 类似。

区间 DP

咕咕。

树形 DP

树上背包

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

DS

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

ST 表

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

文章目录