2021牛客暑期多校训练营2

C

一共有 $n*m$ 个点，考虑生成树，即判断生成树边数量的奇偶性即可。

#include <bits/stdc++.h>
#define sc(x) scanf("%lld", &(x))
#define pr(x) printf("%lld\n", (x))
#define rep(i, l, r) for (int i = l; i <= r; ++i)
using namespace std;
typedef long long ll;
const int N = 1e5 + 7;
const int mod = 1e9 + 7;
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

小模拟注意细节

#include <bits/stdc++.h>
#define sc(x) scanf("%lld", &(x))
#define pr(x) printf("%lld\n", (x))
#define rep(i, l, r) for (int i = l; i <= r; ++i)
using namespace std;
typedef long long ll;
const int N = 1e5 + 7;
const int mod = 1e9 + 7;
int a[3], b[3];
int main() {
    int T;
    scanf("%d", &T);
    while (T--) {
        scanf("%d%d", &a[1], &a[2]);
        scanf("%d%d", &b[1], &b[2]);
        if (a[1] > a[2]) swap(a[1], a[2]);
        if (b[1] > b[2]) swap(b[1], b[2]);
        if (a[1] == 2 and a[2] == 8 and b[1] == 2 and b[2] == 8) puts("tie");
        else if (a[1] == 2 and a[2] == 8)
            puts("first");
        else if (b[1] == 2 and b[2] == 8)
            puts("second");
        else if (a[1] == a[2] and b[1] == b[2]) {
            if (a[1] > b[1])
                puts("first");
            else if (a[1] < b[1])
                puts("second");
            else
                puts("tie");
        } else if (a[1] == a[2]) {
            puts("first");
        } else if (b[1] == b[2])
            puts("second");
        else {
            int aa = (a[1] + a[2]) % 10;
            int bb = (b[1] + b[2]) % 10;
            if (aa > bb)
                puts("first");
            else if (bb > aa)
                puts("second");
            else {
                if (a[2] == b[2])
                    puts("tie");
                else
                    puts(a[2] > b[2] ? "first" : "second");
            }
        }
    }
    return 0;
}

F

题意是计算两球的交的体积。套板即可，写了注释。

#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 = 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

暴力bfs即可。

比赛的时候为了逻辑清楚，把每个方向具体怎么走独立成了函数。

#include <bits/stdc++.h>
#define sc(x) scanf("%lld", &(x))
#define pr(x) printf("%lld\n", (x))
#define rep(i, l, r) for (int i = l; i <= r; ++i)
using namespace std;
typedef long long ll;
const int N = 25;
#define M 20
char a[N][N], b[N][N];
inline bool out(int x, int y, char a[][N]) {
    return x > M || x <= 0 || y > M || y <= 0 || a[x][y] == '#';
}
bool vis[N][N][N][N];
int dx[] = {1, 0, 0, -1};
int dy[] = {0, -1, 1, 0};
// DLRU

struct node {
    int ax, ay, bx, by;
    string s = "";
    void dbg() { cerr << ax << ' ' << ay << ' ' << bx << ' ' << by << '\n'; }
};

inline node goD(node t) {
    t.ax += dx[0], t.ay += dy[0];
    if (out(t.ax, t.ay, a)) t.ax -= dx[0], t.ay -= dy[0]; // 如果出界或碰壁则回溯
    t.bx += dx[0], t.by += dy[0];
    if (out(t.bx, t.by, b)) t.bx -= dx[0], t.by -= dy[0];
    t.s += 'D';
    return t;
}
inline node goL(node t) {
    t.ax += dx[1], t.ay += dy[1];
    if (out(t.ax, t.ay, a)) t.ax -= dx[1], t.ay -= dy[1];
    t.bx += dx[2], t.by += dy[2];
    if (out(t.bx, t.by, b)) t.bx -= dx[2], t.by -= dy[2];
    t.s += 'L';
    return t;
}
inline node goR(node t) {
    t.ax += dx[2], t.ay += dy[2];
    if (out(t.ax, t.ay, a)) t.ax -= dx[2], t.ay -= dy[2];
    t.bx += dx[1], t.by += dy[1];
    if (out(t.bx, t.by, b)) t.bx -= dx[1], t.by -= dy[1];
    t.s += 'R';
    return t;
}
inline node goU(node t) {
    t.ax += dx[3], t.ay += dy[3];
    if (out(t.ax, t.ay, a)) t.ax -= dx[3], t.ay -= dy[3];
    t.bx += dx[3], t.by += dy[3];
    if (out(t.bx, t.by, b)) t.bx -= dx[3], t.by -= dy[3];
    t.s += 'U';
    return t;
}

string bfs() {
    queue<node> q;
    node ori = {M, M, M, 1, ""}, now = ori;
    q.push(ori);
    vis[now.ax][now.ay][now.bx][now.by] = 1;
    while (!q.empty()) {
        now = q.front();
        q.pop();
        if (now.ax == 1 and now.ay == M and now.bx == 1 and now.by == 1)
            return now.s;
        node nxt;
        nxt = goD(now);
        if (!vis[nxt.ax][nxt.ay][nxt.bx][nxt.by]) {
            vis[nxt.ax][nxt.ay][nxt.bx][nxt.by] = 1;
            q.push(nxt);
        }
        nxt = goL(now);
        if (!vis[nxt.ax][nxt.ay][nxt.bx][nxt.by]) {
            vis[nxt.ax][nxt.ay][nxt.bx][nxt.by] = 1;
            q.push(nxt);
        }
        nxt = goR(now);
        if (!vis[nxt.ax][nxt.ay][nxt.bx][nxt.by]) {
            vis[nxt.ax][nxt.ay][nxt.bx][nxt.by] = 1;
            q.push(nxt);
        }
        nxt = goU(now);
        if (!vis[nxt.ax][nxt.ay][nxt.bx][nxt.by]) {
            vis[nxt.ax][nxt.ay][nxt.bx][nxt.by] = 1;
            q.push(nxt);
        }
    }
    return "";
}
int main() {
    rep(i, 1, M) scanf("%s", a[i] + 1), scanf("%s", b[i] + 1);
    string ans = bfs();
    cout << ans.size() << '\n';
    cout << ans << '\n';
    node t = {M, M, M, 1, ""};
    for (char c : ans) {
        a[t.ax][t.ay] = 'A';
        b[t.bx][t.by] = 'A';
        if (c == 'L')
            t = goL(t);
        else if (c == 'R')
            t = goR(t);
        else if (c == 'U')
            t = goU(t);
        else
            t = goD(t);
    }
    a[1][M] = b[1][1] = 'A';
    rep(i, 1, M) printf("%s %s\n", a[i] + 1, b[i] + 1);
    return 0;
}

K

考虑从后往前

#include <bits/stdc++.h>
using namespace std;
const int N = 1e6 + 7;
int a[N], b[N];
int main() {
    int n, m;
    ios::sync_with_stdio(false), cin.tie(0), cout.tie(0);
    cin >> n >> m;
    for (int i = 1, x; i <= m; i++) cin >> x >> a[x];
    for (int i = 1; i <= n; i++) {
        if (!a[i])
            a[i] = a[i - 1] + 1;
        else if (a[i] > a[i - 1] + 1) {
            cout << "-1";
            return 0;
        }
    }
    stack<int> s;
    for (int i = n, cnt = 0; i >= 1; i--) {
        while (a[i] > s.size()) s.push(++cnt);
        b[i] = s.top();
        s.pop();
    }
    for (int i = 1; i <= n; i++) cout << b[i] << ' ';
    return 0;
}