A - 滑雪

题目链接

思路

搜索模板题无需多说，注意一下记忆化搜索和剪枝

代码

#include<iostream>
#include<algorithm>
using namespace std;
const int N = 1005;
typedef pair<int, int> PII;
int n, m, dis[N][N], s[N][N];
int dx[4] = {1, -1, 0, 0};
int dy[4] = {0, 0, 1, -1};
int dfs(int i, int j)
{
    if (dis[i][j] != 0)
        return dis[i][j];
    dis[i][j]=1;
    for (int l = 0; l < 4; l++)
    {
        int x = i + dx[l];
        int y = j + dy[l];
        if (x >= 1 && x <= n && y >= 1 && y <= n && s[i][j] > s[x][y])
            dis[i][j] = max(dfs(x, y) + 1, dis[i][j]);
    }
    return dis[i][j];
}
int main()
{
    cin >> n >> m;
    for (int i = 1; i <= n; i++)
        for (int j = 1; j <= m; j++)
            cin >> s[i][j];
    int mas = 0;
    for (int i = 1; i <= n; i++)
        for (int j = 1; j <= m; j++)
            mas = max(dfs(i, j), mas);
    cout<<mas;
    return 0;
}

B - Dungeon Master

题目链接

题意

一个三维的迷宫问题

思路

三维于二维迷宫问题只是多了上下两个搜索方向，其余没有什么不同

代码

#include <stdio.h>
#include <string.h>
#include <queue>
using namespace std;

#define maxn 100

struct node
{
    int x, y, z, step;
};

int h, m, n; //高，长和宽
// 6个方向可以走
int dir[6][3] = {{1, 0, 0}, {-1, 0, 0}, {0, 1, 0}, {0, -1, 0}, {0, 0, 1}, {0, 0, -1}};
char G[maxn][maxn][maxn];

int OK(int z, int x, int y) //判断这点是否可以走
{
    if (z >= 0 && z < h && x >= 0 && x < m && y >= 0 && y < n && G[z][x][y] != '#')
        return 1;
    return 0;
}
int DFS(node s, node e)
{
    queue<node> Q;
    Q.push(s);

    while (Q.size())
    {
        s = Q.front();
        Q.pop();

        if (s.x == e.x && s.y == e.y && s.z == e.z)
            return s.step;

        for (int i = 0; i < 6; i++)
        {
            node q = s;
            q.x += dir[i][0];
            q.y += dir[i][1];
            q.z += dir[i][2];
            q.step += 1;

            if (OK(q.z, q.x, q.y) == 1)
            {
                G[q.z][q.x][q.y] = '#';
                Q.push(q);
            }
        }
    }

    return -1;
}

int main()
{
    while (scanf("%d%d%d", &h, &m, &n), h + m + n)
    {
        int i, j, k;
        node s, e;

        for (i = 0; i < h; i++)
            for (j = 0; j < m; j++)
            {
                scanf("%s", G[i][j]);
                for (k = 0; k < n; k++)
                {
                    if (G[i][j][k] == 'S')
                    {
                        s.z = i;
                        s.x = j;
                        s.y = k;
                        s.step = 0;
                    }
                    if (G[i][j][k] == 'E')
                    {
                        e.z = i;
                        e.x = j;
                        e.y = k;
                    }
                }
            }

        int ans = DFS(s, e);

        if (ans != -1)
            printf("Escaped in %d minute(s).\n", ans);
        else
            printf("Trapped!\n");
    }

    return 0;
}

C - 8 Puzzle on Graph

题目链接

题意

给一个 3 x 3 的表格从上到下位置编号为 1~3，4~6，7~9，将1~8 共8个数放入其中，给予一系列的移动规则，如 1 - 2 指编号为1的格子可以于编号为2的格子互换，互换时必须有一个格子为空。问是否能将数字移到对应编号上，如果可以输出至少移动几步，不可以输出 -1

思路

想明白题意花了好长时间，注意题目给的初始状态是指第几个数在哪个位置 比如 

    3 9 2 4 5 6 7 8

1 在 编号 3 

2 在 编号 9

 . . .

以此类推

明白了题意接下来就简单了，只要从空白格子开始广搜就行了，用字符串表示不同状态同时标记避免重复

代码

#include <bits/stdc++.h>
using namespace std;
map<string, int> ma;
int vis[10][10];
vector<int> q[10];
int main()
{
    int n;
    cin >> n;
    for (int i = 1; i <= n; i++)
    {
        int a, b;
        cin >> a >> b;
        q[a - 1].push_back(b - 1);
        q[b - 1].push_back(a - 1);
    }
    string s = "999999999";
    for (int i = 1; i <= 8; i++)
    {
        int a;
        cin >> a;
        s[a-1] = i + '0';
    }
    queue<string> e;
    e.push(s);
    ma[s] = 0;
    while (!e.empty())
    {
        string s1 = e.front();
        e.pop();
        if (s1 == "123456789")
        {
            cout << ma[s1];
            return 0;
        }
        int k;
        for (int i = 0; i < 9; i++)
            if (s1[i] == '9')
                k = i;
        for (int i = 0; i < q[k].size(); i++)
        {
            string sc = s1;
            swap(sc[k], sc[q[k][i]]);
            if (ma[sc] == 0)
            {
                ma[sc] = ma[s1] + 1;
                e.push(sc);
            }
            
        }
    }
    cout << -1;
    return 0;
}

D - Subtree K-th Max

题目链接

题意

n 个数，q 个询问
接下来一行 n 个数：xi 表示第 i  个点的权值是 xi
接下来 n − 1  行，每行两个数 a , b ，表示 a  和 b  之间有一条边
接下来 q  行，每行两个数 a , b ，问以 a 为根节点的子树中所有节点权值的第 b大是多少。

思路

从1开始搜索，每到一个节点记录以这个节点为根节点的前20大（因为 1<=b<=20，所以记录20个就够了）

然后对每个查询就可以直接输出

代码

#include <bits/stdc++.h>
using namespace std;
const int N = 100233;
int sa[N];
vector<int> q[N];
vector<int> w[N];
bool cmp(int a, int b)
{
    return a > b;
}
void dfs(int t, int p)//t为根结点，p为其父节点
{
    w[t].push_back(sa[t]);
    for (auto x : q[t])
    {
        if (x == p)//避免重复
            continue;
        dfs(x,t);
        for (auto y : w[x])
            w[t].push_back(y);
    }
    sort(w[t].begin(), w[t].end(), cmp);
    if (w[t].size() > 20)
        w[t].resize(20);
}
int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0), cout.tie(0);
    int n, m;
    cin >> n >> m;
    for (int i = 1; i <= n; i++)
        cin >> sa[i];
    for (int i = 1; i < n; i++)
    {
        int a, b;
        cin >> a >> b;
        q[a].push_back(b);
        q[b].push_back(a);
    }
    dfs(1, 0);
    for (int i = 1; i <= m; i++)
    {
        int a, k;
        cin >> a >> k;
        cout << w[a][k - 1] << endl;
    }
    return 0;
}