Codeforces Round 920 (Div. 3)补题D~F

Codeforces Round 920 (Div. 3)

D.

思路

取a最大和c最小的或c最小和a最大的匹配

ac代码

#include <bits/stdc++.h>

using namespace std;
using i64 = long long;
const i64 inf = 8e18;
typedef pair<int, int> pii;
const int mod = 1e9 + 7;
const int N = 2e6 + 10;

void solve() {
    int n, m; 
    cin >> n >> m;
    deque<i64> a(n), b(m);
    for (auto &i : a) cin >> i;
    for (auto &i : b) cin >> i;

    sort(a.begin(), a.end());
    sort(b.begin(), b.end());

    i64 ans = 0;
    while (a.size()) {
        if (abs(a.front() - b.back()) >= abs(b.front() - a.back())) {
            ans += abs(a.front() - b.back());
            a.pop_front();
            b.pop_back();
        } else {
            ans += abs(b.front() - a.back());
            b.pop_front();
            a.pop_back();
        }
    }

    cout << ans << endl;
}   

int main() {
    ios::sync_with_stdio(0); cin.tie(0);
    cout.tie(0);

    int t = 1;
    cin >> t;
    while (t --) solve();

    return 0;
}

D.

思路

可以看出来，当行数差为奇数时是Alice吃Bob，行数为偶数时是Bob吃Alice。先特判一下初始时Alice和Bob在同一行或Alice在Bob下面的情况，这种情况下就是平局。然后来看一般的情况。若是Alice吃Bob，当他们的列数差小于1时Alice必定吃到Bob，当他们列数差大于1时就要看Alice的操作次数和Alice离墙的距离；若是Bob吃Alice，当他们列数相等时Bob必定吃到Alice，否则就要看Bob的操作次数和他与墙距离的大小关系。

ac代码

#include <bits/stdc++.h>

using namespace std;
using i64 = long long;
const i64 inf = 8e18;
typedef pair<int, int> pii;
const int mod = 1e9 + 7;
const int N = 1e6 + 10;

void solve() {
    int h, w, xa, ya, xb, yb;
    cin >> h >> w >> xa >> ya >> xb >> yb;
    if (xa >= xb) cout << "Draw\n";
    else if ((xb - xa) % 2) {
        int t = (xb - xa + 1) / 2;//操作次数，因为Alice是先手，所以操作次数比Bob多一次
        if (abs(ya - yb) <= 1 || ya < yb && (w - ya) <= t || ya > yb && ya - 1 <= t) cout << "Alice\n";
        else cout << "Draw\n";
    } else {
        int t = (xb - xa) / 2;
        if (ya == yb || ya < yb && yb - 1 <= t || ya > yb && (w - yb) <= t) cout << "Bob\n";
        else cout << "Draw\n";
    }

}   

int main() {
    ios::sync_with_stdio(0); cin.tie(0);
    cout.tie(0);

    int t = 1;
    cin >> t;
    while (t --) solve();

    return 0;
}

F.

带权前缀和，根号分治