1. Collecting Numbers

给定一个 $(1, 2, \cdots, n)$ 的排列，你的任务是按递增顺序收集数字。

每一回合，你可以从左到右收集尽可能多的数字。问将所有数字收集完至少需要多少回合？

限制：

• $1 \leqslant n \leqslant 2 \times 10^5$

算法分析

首先，至少需要一个回合，所以答案初始值为 $1$
然后可以维护每个数的位置，对于每个 $i \in [1, n-1]$，若 $pos[i+1] > pos[i]$， 则答案 +1

C++ 代码

#include <bits/stdc++.h>
#define rep(i, n) for (int i = 1; i <= (n); ++i)

using namespace std;

int main() {
    int n;
    cin >> n;

    vector<int> x(n+1);
    rep(i, n) cin >> x[i];

    vector<int> pos(n+1);
    rep(i, n) pos[x[i]] = i;

    int ans = 1;
    rep(i, n-1) {
        ans += pos[i] > pos[i+1];
    }

    cout << ans << '\n';

    return 0;
}

2. Collecting Numbers II

给定一个 $(1, 2, \cdots, n)$ 的排列，你的任务是按递增顺序收集数字。

每一回合，你可以从左到右收集尽可能多的数字。

再给定 $m$ 次操作，每次操作给定两个数 $a$ 和 $b$，然后交换 $x_a$ 和 $x_b$，并回答将所有数字收集完至少需要多少回合？

限制：

• $1 \leqslant n, m \leqslant 2 \times 10^5$
• $1 \leqslant a , b \leqslant n$

算法分析

可以先求出原序列的答案
其次，注意到，对于每次操作，受影响的只有 $pos[x_a-1]$ 与 $pos[x_a]$，$pos[x_a]$ 与 $pos[x_a+1]$，$pos[x_b-1]$ 与 $pos[x_b]$，$pos[x_b]$ 与 $pos[x_b+1]$ 这些数的大小关系，所以可以做到 $O(1)$ 维护

C++ 代码

#include <bits/stdc++.h>
#define rep(i, n) for (int i = 1; i <= (n); ++i)

using namespace std;

int main() {
    int n, m;
    cin >> n >> m;

    vector<int> x(n+1);
    rep(i, n) cin >> x[i];

    vector<int> pos(n+2);
    rep(i, n+1) pos[x[i]] = i;

    int ans = 1;
    rep(i, n-1) {
        ans += pos[i] > pos[i+1];
    }

    auto upd = [&](int a, int b) {
        if (pos[x[a]-1] <= pos[x[a]] and b < pos[x[a]-1]) ans++;
        if (pos[x[a]-1] > pos[x[a]] and b >= pos[x[a]-1]) ans--;
        if (pos[x[a]+1] >= pos[x[a]] and b > pos[x[a]+1]) ans++;
        if (pos[x[a]+1] < pos[x[a]] and b <= pos[x[a]+1]) ans--;
        pos[x[a]] = b;

        if (pos[x[b]-1] <= pos[x[b]] and a < pos[x[b]-1]) ans++;
        if (pos[x[b]-1] > pos[x[b]] and a >= pos[x[b]-1]) ans--;
        if (pos[x[b]+1] >= pos[x[b]] and a > pos[x[b]+1]) ans++;
        if (pos[x[b]+1] < pos[x[b]] and a <= pos[x[b]+1]) ans--;
        pos[x[b]] = a;

        swap(x[a], x[b]);
    };

    rep(i, m) {
        int a, b;
        cin >> a >> b;
        upd(a, b);
        cout << ans << '\n';
    }

    return 0;
}

3. Find the Snaky

从 $s_0$ 在网格中的位置出发跑 $\operatorname{dfs}$ 即可

代码实现

#include <bits/stdc++.h>
#define rep(i, n) for (int i = 0; i < (n); ++i)

using namespace std;
using P = pair<int, int>;

int main() {
    int h, w;
    cin >> h >> w;

    vector<string> g(h);
    rep(i, h) cin >> g[i];

    int n;
    string s;
    cin >> n >> s;

    bool ok = false;
    set<P> st;
    auto dfs = [&](auto& f, int i, int j, int k) -> void {
        if (k == n) {
            ok = true;
            return;
        }

        st.emplace(i, j);
        for (int di = -1; di <= 1; ++di) {
            for (int dj = -1; dj <= 1; ++dj) {
                if (di == 0 and dj == 0) continue;
                int ni = i+di, nj = j+dj;
                if (ni < 0 or ni >= h or nj < 0 or nj >= w) continue;
                if (st.count(P(ni, nj))) continue;
                if (g[ni][nj] != s[k]) continue;
                f(f, ni, nj, k+1);
            }
        }
        st.erase(P(i, j));
    };

    rep(i, h)rep(j, w) {
        if (g[i][j] == s[0]) {
            dfs(dfs, i, j, 1);
        }
    }

    if (ok) puts("Yes");
    else puts("No");

    return 0;
}