T1[坚强的小昆虫]

题目描述

由于新冠肺炎疫情的爆发，小明养在宿舍的小昆虫已经很久都没有人管了。小昆虫已经饿的不行了，必须出来找东西吃，可是出来之后需要走出一个迷宫。小昆虫每次可以朝上、下、左、右四个方向之一走一步，且只要走出任意一条边界线即可逃出迷宫。这只小昆虫曾感染过X星的一种奇异病毒，目前还没有发现任何副作用，但是却拥有了一项特异功能，破坏障碍物。假设小昆虫在$N * M$的迷宫中，“@”代表小昆虫的初始位置，“.”代表可以通过的空地，“*”代表可以破坏的障碍物，“#”代表不可破坏的障碍物。请问小昆虫最少需要使用多少次特异功能才可以逃出迷宫？

输入描述

多组数据，第1行有1个正整数T，表示有T组数据。（$T \leq 100$）
对于每组数据，第1行有两个整数$N$和$M$。（$1 \leq N, M \leq 1000$）
接着$N$行，每行有一个长度为$M$的字符串，表示$N * M$的迷宫。

输出描述

输出一个整数，表示使用特异功能的最少次数。如果小昆虫不能走出迷宫，则输出-1。

示例1

样例输入

3
3 3
###
#@*
***
3 4
####
#@.*
**.*
3 3
.#.
#@#
.#.

样例输出

1
0
-1

算法

(BFS) $O(T \times n \times m)$

C++ 代码

#include <bits/stdc++.h>
using namespace std;

#define x first
#define y second

const int N = 1010;
typedef pair<int, int> PII;
typedef pair<int, PII> PIII;

int T, n, m;
char g[N][N];
int d[N][N];
int dx[4] = {0, 0, 1, -1}, dy[4] = {1, -1, 0, 0};
PII start;

int bfs() {
    memset(d, -1, sizeof d);
    d[start.x][start.y] = 0;

    priority_queue<PIII, vector<PIII>, greater<PIII>> q;
    q.push({0, start});

    while (q.size()) {
        auto t = q.top(); q.pop();

        int times = t.x, x = t.y.x, y = t.y.y;
        for (int i = 0; i < 4; i ++ ) {
            int a = x + dx[i], b = y + dy[i];
            if (a < 0 || b < 0 || a >= n || b >= m) return times;
            if (g[a][b] == '#' || d[a][b] != -1) continue;
            d[a][b] = d[x][y] + 1;
            if (g[a][b] == '.') q.push({times, {a, b}});
            else if (g[a][b] == '*') q.push({times + 1, {a, b}});
        }
    }

    return -1;
}

int main() {
    cin >> T;

    while (T -- ) {
        cin >> n >> m;
        for (int i = 0; i < n; i ++ ) {
            cin >> g[i];
            for (int j = 0; j < m; j ++ )
                if (g[i][j] == '@')
                    start = {i, j};
        }

        cout << bfs() << endl;
    }

    return 0;
}

T2[祖先]

题目描述

你的实验室中诞生了一种新的无性繁殖生物，这种生物每一个都有且仅有一个父亲（注意，其中有且仅有1号生物的父亲无法追踪到了）。为了研究方便，你定义一个生物的1级祖先即为其父亲，而其K级祖先为K-1级祖先的父亲（$K \leq 2$）。例如，2级祖先即为父亲的父亲。现在你想知道一些生物的若干级父亲。

输入描述

第一行两个以空格给开的正整数$n$和$q$，表示生物总和询问次数
第二行有$n-1$个由空格隔开的正整数，$a_2, a_3, \dots, a_n$依次表示2号生物的父亲、3号生物的父亲…i号生物的父亲的编号为$a_i$。其中1号生物的父亲已经无法追踪到了。
接下来$q$行，每行两个由空格隔开的正整数$x, k$，表示询问第$x$号生物的$k$级祖先。
$n, q \leq 50000, 1 \leq a_i < i, 1 \leq x, k \leq n$

输出描述

输出$q$行，每行依次对应一个询问的答案，即第$x$号生物的$k$级祖先。如果无法追踪到该祖先，则输出0。

示例1

样例输入

5 3
1 2 3 4
5 1
1 1
5 3

样例输出

4
0
2

算法

(LCA) $O(mlog(n))$

C++ 代码

#include <bits/stdc++.h>
using namespace std;

const int N = 5e4 + 10, M = 16;

int n, m;
int p[N], f[N][M];
vector<int> g[N];

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

    p[1] = -1;
    for (int i = 2; i <= n; i ++ ) cin >> p[i], g[p[i]].push_back(i);

    memset(f, -1, sizeof f);
    queue<int> q; q.push(1);

    while (q.size()) {
        int t = q.front(); q.pop();
        for (auto c: g[t]) {
            q.push(c);
            f[c][0] = t;
            for (int k = 1; k < 16; k ++ )
                if (f[c][k - 1] != -1)
                    f[c][k] = f[f[c][k - 1]][k - 1];
        }
    }

    while (m -- ) {
        int a, k; cin >> a >> k;
        for (int i = 16; i >= 0; i -- )
            if (k >> i & 1) {
                a = f[a][i];
                if (a == -1) break;
            }
        if (a != -1) cout << a << endl;
        else puts("0");
    }

    return 0;
}