2021 牛客多校2 题解

C Draw Grids

n个点，两个点之间连一条线，不成环，很明显只能连n*m-1条边

此时判断先手胜负非常简单了

#include <bits/stdc++.h>
using namespace std;
int main() {
    int n, m;
    cin >> n >> m;
    if (n > m) swap(n, m);
    if ((m * n - 1) & 1)
        puts("YES");
    else
        puts("NO");
    return 0;
}

D Er Ba Game

按题意模拟即可

#include <bits/stdc++.h>
using namespace std;
void solve() {
    int a, b, c, d;
    cin >> a >> b >> c >> d;
    if (a > b)
        swap(a, b);
    if (c > d)
        swap(c, d);
    if (a == 2 and b == 8) {
        if (c == 2 and d == 8)
            cout << "tie" << endl;
        else
            cout << "first" << endl;
    } else if (c == 2 and d == 8)
        if (a == 2 and b == 8)
            cout << "tie" << endl;
        else
            cout << "second" << endl;
    else if (a == b) {
        if (c == d) {
            if (a > c)
                cout << "first" << endl;
            else if (c > a)
                cout << "second" << endl;
            else
                cout << "tie" << endl;
        } else
            cout << "first" << endl;
    } else if (c == d)
        cout << "second" << endl;
    else if ((a + b) % 10 > (c + d) % 10)
        cout << "first" << endl;
    else if ((a + b) % 10 < (c + d) % 10)
        cout << "second" << endl;
    else if (b == d)
        cout << "tie" << endl;
    else if (b > d)
        cout << "first" << endl;
    else
        cout << "second" << endl;
}
signed main() {
    int t;
    cin >> t;
    while (t--)
        solve();

    return 0;
}

F Girlfriend

题意

给定空间中四个点 $A,B,C,D$ ，求点 $P_1,P_2$ 满足 $|AP_1|\ge k_1|BP_1|,|CP_2|\ge k_2|DP_2|$ 的所有点集。

可以很明显的发现 $P_1$ 和 $P_2$ 的所有点集为一个球，问题即可转化为求两个球的交集

分类讨论两个球之间相交、相离、内切等情况即可求出

#include <bits/stdc++.h>
using namespace std;
#define endl '\n'
typedef long double ld;
typedef long long ll;
const ld pi = acos(-1);
const ld eps = 1e-8;
struct point {
    ld x, y, z;
    point operator+(const point &a) {
        point t;
        t.x = x + a.x, t.y = y + a.y, t.z = z + a.z;
        return t;
    }
    point operator/(const ld k) {
        point t;
        t.x = x / k, t.y /= k, t.z /= k;
        return t;
    }
    ld sd() { return x * x + y * y + z * z; }
};
struct ball {
    point center;
    ld rad;
};
ld getdis(point a, point b) {
    return sqrt((a.x - b.x) * (a.x - b.x) + (a.y - b.y) * (a.y - b.y) +
                (a.z - b.z) * (a.z - b.z));
}
ld getV(ball a) { return 4.0 * pi * a.rad * a.rad * a.rad / 3.0; }
ld getcos(ld a, ld b, ld c) { return (a * a + b * b - c * c) / (2 * a * b); }
ld getVs(ld h, ld r) { return pi / 3.0 * (3.0 * r - h) * h * h; }
ld cal(ball a, ball b) {
    ld dis = getdis(a.center, b.center);
    if (dis >= (a.rad + b.rad))
        return 0;
    else if (dis + a.rad - b.rad < eps)
        return getV(a);
    else if (dis + b.rad - a.rad < eps)
        return getV(b);
    else {
        ld alpha = getcos(a.rad, dis, b.rad), beta = getcos(dis, b.rad, a.rad);
        ld h1 = a.rad * (1 - alpha), h2 = b.rad * (1 - beta);
        return getVs(h1, a.rad) + getVs(h2, b.rad);
    }
}
ball getcenter(ld k, point a, point b) {
    ld A, B, C, D, tmp;
    k = k * k, tmp = 1 - k;
    A = 2 * (k * b.x - a.x) / tmp;
    B = 2 * (k * b.y - a.y) / tmp;
    C = 2 * (k * b.z - a.z) / tmp;
    D = -(k * b.sd() - a.sd()) / tmp;
    ball res;
    res.center.x = A / 2, res.center.y = B / 2, res.center.z = C / 2;
    res.rad = sqrt((A * A + B * B + C * C - D * 4.0) / 4.0);
    return res;
}
void solve() {
    point A, B, C, D;
    ld k1, k2;
    cin >> A.x >> A.y >> A.z >> B.x >> B.y >> B.z >> C.x >> C.y >> C.z >> D.x >>
        D.y >> D.z >> k1 >> k2;
    ball a, b;
    a = getcenter(k1, A, B);
    b = getcenter(k2, C, D);
    cout << cal(a, b) << endl;
}
signed main() {
    int t;
    cin >> t;
    while (t--)
        solve();
    return 0;
}

I Penguins

题意

左右各有两只企鹅，需要操作左边的企鹅，右边的企鹅会随着左边的运动而对应的镜像运动

即：左边向上、下、左、右

右边向上、下、右、左

使得左边的企鹅从右下角移动到右上角，右边的企鹅从左下角移动到左上角

输出字典序最小的操作方式

按照字典序按顺序模拟操作即可

~~白嫖队友代码~~

#include <bits/stdc++.h>
using namespace std;
#define rep(i, l, r) for (int i = l; i <= r; ++i)
const int N = 50;
char a[N][N], b[N][N], go[] = "DLRU";
bool vis[N][N][N][N];
int dis[4][4] = {{1, 0, 1, 0}, {0, -1, 0, 1}, {0, 1, 0, -1}, {-1, 0, -1, 0}};
inline bool chk(int x, int y, char a[][N]) {
    if (x > 20 || x <= 0 || y > 20 || y <= 0 || a[x][y] == '#')
        return 1;
    else
        return 0;
}
struct node {
    int ax, ay, bx, by;
    string s = "";
};
string bfs() {
    queue<node> q;
    node st = {20, 20, 20, 1, ""}, now, tmp;
    q.push(st);
    vis[st.ax][st.ay][st.bx][st.by] = 1;
    while (!q.empty()) {
        now = q.front();
        q.pop();
        if (now.ax == 1 and now.ay == 20 and now.bx == 1 and now.by == 1)
            return now.s;
        rep(i, 0, 3) {
            int ax = now.ax + dis[i][0], ay = now.ay + dis[i][1],
                bx = now.bx + dis[i][2], by = now.by + dis[i][3];
            if (chk(ax, ay, a))
                ax -= dis[i][0], ay -= dis[i][1];
            if (chk(bx, by, b))
                bx -= dis[i][2], by -= dis[i][3];
            if (!vis[ax][ay][bx][by]) {
                vis[ax][ay][bx][by] = 1;
                q.push({ax, ay, bx, by, now.s + go[i]});
            }
        }
    }
    return "";
}
signed main() {
    rep(i, 1, 20) scanf("%s", a[i] + 1), scanf("%s", b[i] + 1);
    string s = bfs();
    cout << s.size() << endl << s << endl;
    int ax = 20, ay = 20, bx = 20, by = 1;
    for (char c : s) {
        a[ax][ay] = 'A', b[bx][by] = 'A';
        if (c == 'D') {
            ax += dis[0][0], ay += dis[0][1], bx += dis[0][2], by += dis[0][3];
            if (chk(ax, ay, a))
                ax -= dis[0][0], ay -= dis[0][1];
            if (chk(bx, by, b))
                bx -= dis[0][2], by -= dis[0][3];
        }
        if (c == 'L') {
            ax += dis[1][0], ay += dis[1][1], bx += dis[1][2], by += dis[1][3];
            if (chk(ax, ay, a))
                ax -= dis[1][0], ay -= dis[1][1];
            if (chk(bx, by, b))
                bx -= dis[1][2], by -= dis[1][3];
        }
        if (c == 'R') {
            ax += dis[2][0], ay += dis[2][1], bx += dis[2][2], by += dis[2][3];
            if (chk(ax, ay, a))
                ax -= dis[2][0], ay -= dis[2][1];
            if (chk(bx, by, b))
                bx -= dis[2][2], by -= dis[2][3];
        }
        if (c == 'U') {
            ax += dis[3][0], ay += dis[3][1], bx += dis[3][2], by += dis[3][3];
            if (chk(ax, ay, a))
                ax -= dis[3][0], ay -= dis[3][1];
            if (chk(bx, by, b))
                bx -= dis[3][2], by -= dis[3][3];
        }
    }
    a[1][20] = b[1][1] = 'A';
    rep(i, 1, 20) printf("%s %s\n", a[i] + 1, b[i] + 1);
    return 0;
}

K Stack

题意

给出一个排列 $A$ 通过下面伪码构造一个序列 $B$

Stk is an empty stack
for i = 1 to n :
    while ( Stk is not empty ) and ( Stk's top > a[i] ) : 
        pop Stk
    push a[i]
    b[i]=Stk's size

先给定 $B$ 中 $k$ 个元素，构造排列 $A$

明显发现：序列 $B$ 存储的是当 $A$ 中第 $i$ 个元素进栈时栈中满足栈顶元素比它小的栈的元素个数（单调栈

考虑每个元素都是大于上一个元素，即全都压栈，计算出每个元素压栈时栈的元素数量，然后在从后往前，模拟压栈顺序，依次取出即可。

#include <bits/stdc++.h>
using namespace std;
#define rep(i, j, k) for (ll(i) = (j); (i) <= (k); (++i))
#define rrep(i, j, k) for (ll i = (ll)(j); i >= (ll)(k); i--)
typedef long long ll;
const int N = 1e6 + 7;
ll a[N], b[N], st[N];
signed main() {
    int n, k, t, cnt = 0;
    ios::sync_with_stdio(false), cin.tie(0), cout.tie(0);
    cin >> n >> k;
    rep(i, 1, k) cin >> t >> a[t];
    rep(i, 1, n) {
        if (!a[i]) // 当前元素压栈
            a[i] = a[i - 1] + 1;
        else if (a[i] > a[i - 1] + 1) // 当前元素压栈，栈中元素数量只会多1，否则不行
            return cout << "-1\n", 0;
    }
    st[t = 0] = 0;
    // 从后往前模拟加入的元素即可
    rrep(i, n, 1) {
        while (a[i] > t)
            st[++t] = ++cnt;
        b[i] = st[t--];
    }
    rep(i, 1, n) cout << b[i] << " \n"[i==n];
    return 0;
}