牛客多校赛题解 （二）

Er Ba Game

题目链接：https://ac.nowcoder.com/acm/contest/11253/D

题目大意：

大模拟 给了一种打牌的方式，让你判断谁输谁赢

解题思路：

没啥思路，按照他说的写就行

#include <bits/stdc++.h>
using namespace std;
int main()
{
    int t;
    cin >> t;
    while (t--)
    {
        int a, b, c, d;
        cin >> a >> b >> c >> d;
        int minn = min(a, b);
        int maxn = max(a, b);
        a = minn;
        b = maxn;
        minn = min(c, d);
        maxn = max(c, d);
        c = minn;
        d = maxn;
        if (a == 2 && b == 8 || a == 8 && b == 2)
        {
            if (c == 2 && d == 8 || c == 8 && d == 2)
                cout << "tie" << endl;
            else
                cout << "first" << endl;
        }
        else
        {
            if (c == 2 && d == 8 || c == 8 && d == 2)
                cout << "second" << endl;
            else
            {
                if (a == b)
                {
                    if (c != d)
                    {
                        cout << "first" << endl;
                    }
                    else
                    {
                        if (a == d)
                        {
                            cout << "tie" << endl;
                        }
                        else
                        {
                            if (a > d)
                            {
                                cout << "first" << endl;
                            }
                            else
                            {
                                cout << "second" << endl;
                            }
                        }
                    }
                }
                else
                {
                    if (c == d)
                    {
                        cout << "second" << endl;
                    }
                    else
                    {
                        int t = (a + b) % 10;
                        int f = (c + d) % 10;
                        if (t > f)
                        {
                            cout << "first" << endl;
                        }
                        else if (t < f)
                            cout << "second" << endl;
                        else
                        {
                            if (b > d)
                                cout << "first" << endl;
                            else if (b < d)
                                cout << "second" << endl;
                            else
                                cout << "tie" << endl;
                        }
                    }
                }
            }
        }
    }
}

Penguins

题目链接：https://ac.nowcoder.com/acm/contest/11253/I

题目大意：

有两只企鹅，想要以相反的方向移动，左上到右下，右上到左下，问最短的移动方式是啥

解题思路：

这是一个赤裸裸的广搜啊，只是给了一些条件，处理一下就行

ACCode：

/*
 * @Author: Mr.Sen
 * @LastEditTime: 2021-07-20 21:14:39
 * @Description: 
 * @Website: https://grimoire.cn
 * Copyright (c) Mr.Sen All rights reserved.
 */
#include <bits/stdc++.h>
using namespace std;
char m1[25][25];
char m2[25][25];
bool vis[25][25][25][25];

int nt[4][4] = {{1, 0, 1, 0}, {0, -1, 0, 1}, {0, 1, 0, -1}, {-1, 0, -1, 0}};
string dir[] = {"D", "L", "R", "U"};

struct node
{
    int x1, y1, x2, y2;
    string s;
} ans;

void move(int &x1, int &y1, int &x2, int &y2, int dirc)
{
    x1 += nt[dirc][0], y1 += nt[dirc][1], x2 += nt[dirc][2], y2 += nt[dirc][3];
    if (m1[x1][y1] == '#')
        x1 -= nt[dirc][0], y1 -= nt[dirc][1];
    if (m2[x2][y2] == '#')
        x2 -= nt[dirc][2], y2 -= nt[dirc][3];
    m1[x1][y1] = m2[x2][y2] = 'A';
}

void Print()
{
    int x1 = 20, y1 = 20, x2 = 20, y2 = 1;
    m1[20][20] = m2[20][1] = 'A';
    int len = ans.s.size();
    for (int i = 0; i < len; i++)
    {
        if (ans.s[i] == 'D')
            move(x1, y1, x2, y2, 0);
        else if (ans.s[i] == 'L')
            move(x1, y1, x2, y2, 1);
        else if (ans.s[i] == 'R')
            move(x1, y1, x2, y2, 2);
        else if (ans.s[i] == 'U')
            move(x1, y1, x2, y2, 3);
    }
    for (int i = 1; i <= 20; i++)
    {
        for (int j = 1; j <= 20; j++)
            cout << m1[i][j];
        cout << " ";
        for (int j = 1; j <= 20; j++)
            cout << m2[i][j];
        cout << endl;
    }
}

int main()
{
    for (int i = 0; i <= 30; i++)
        for (int j = 0; j <= 30; j++)
            m1[i][j] = m2[i][j] = '#';
    for (int i = 1; i <= 20; i++)
    {
        for (int j = 1; j <= 20; j++)
        {
            cin >> m1[i][j];
        }
        for (int j = 1; j <= 20; j++)
            cin >> m2[i][j];
    }
    queue<node> q;
    node a = {20, 20, 20, 1, ""};
    q.push(a);
    vis[20][20][20][1] = 1;
    while (!q.empty())
    {
        node t = q.front();
        q.pop();
        if (t.x1 == 1 && t.y1 == 20 && t.x2 == 1 && t.y2 == 1)
        {
            ans = t;
            break;
        }
        for (int i = 0; i < 4; i++)
        {
            int x1 = t.x1 + nt[i][0], y1 = t.y1 + nt[i][1];
            int x2 = t.x2 + nt[i][2], y2 = t.y2 + nt[i][3];
            bool left = (bool)(!(m1[x1][y1] == '#'));
            bool right = (bool)(!(m2[x2][y2] == '#'));
            if (!left)
                x1 = t.x1, y1 = t.y1;
            if (!right)
                x2 = t.x2, y2 = t.y2;
            node p = {x1, y1, x2, y2, t.s + dir[i]};
            if (!vis[x1][y1][x2][y2])
            {
                vis[x1][y1][x2][y2] = 1;
                q.push(p);
            }
        }
    }
    cout << ans.s.size() << "\n"
         << ans.s << "\n";
    Print();
    return 0;
}

Stack

题目连接：https://ac.nowcoder.com/acm/contest/11253/K

题目大意：

给了一串伪代码，对一个数组a添加进去的每一个数都要运行一下这个代码，然后用另一个数组b来记录当前数组a长度，只记得数组b的几个数，问有无一种情况的a数组能满足当前情况

解题思路：

求出可行的数组b，然后再根据数组b倒推数组a，就可以得出这个题的答案了（答案不唯一）

/*
 * @Author: Mr.Sen
 * @LastEditTime: 2021-07-20 20:59:36
 * @Description: 
 * @Website: https://grimoire.cn
 * Copyright (c) Mr.Sen All rights reserved.
 */
#include <bits/stdc++.h>
using namespace std;

const int N = 1e6 + 10;
int val[N], L[N], R[N], pos[N], ans[N];

vector<int> v[N];
int main()
{
    int n, k;
    cin >> n >> k;
    for (int i = 1; i <= k; i++)
    {
        int p, x;
        scanf("%d%d", &p, &x);
        pos[p] = x;
    }
    for (int i = 1; i <= n; i++)
    {
        if (pos[i])
        {
            if (pos[i] - pos[i - 1] > 1)
            {
                cout << -1;
                return 0;
            }
        }
        else
            pos[i] = pos[i - 1] + 1;
        v[pos[i]].push_back(i);
    }
    int as = n;
    for (int i = n; i; i--)
    {
        int sz = v[i].size();
        for (int j = 0; j < sz; j++)
        {
            ans[v[i][j]] = as--;
        }
    }
    for (int i = 1; i <= n; i++)
        printf("%d ", ans[i]);
    return 0;
}