「解题报告」AtCoder Beginner Contest 313

比赛地址：AtCoder Beginner Contest 313 - AtCoder

后记：请正确理解题意后再做题！！！

A - To Be Saikyo

A - To Be Saikyo (atcoder.jp)

每个人有一个数值，问第一个人要加多少才能使得自己的数值变成最大的。

就这么个破题我还 WA 了一发

//The code was written by yifan, and yifan is neutral!!!

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
#define bug puts("NOIP rp ++!");

template<typename T>
inline T read() {
    T x = 0;
    bool fg = 0;
    char ch = getchar();
    while (ch < '0' || ch > '9') {
        fg |= (ch == '-');
        ch = getchar();
    }
    while (ch >= '0' && ch <= '9') {
        x = (x << 3) + (x << 1) + (ch ^ 48);
        ch = getchar();
    }
    return fg ? ~x + 1 : x;
}

const int N = 110;

int n, maxx, cnt;
int p[N];

int main() {
    n = read<int>();
    for (int i = 1; i <= n; ++ i) {
        p[i] = read<int>();
        if (maxx == p[i]) {
            ++ cnt;
        } else {
            maxx = max(maxx, p[i]);
            cnt = 1;
        }
    }
    sort(p + 2, p + n + 1, greater<int>());
    if (p[2] < p[1]) {
        puts("0");
    } else {
        cout << p[2] - p[1] + 1 << '\n';
    }
    return 0;
}

B - Who is Saikyo?

B - Who is Saikyo? (atcoder.jp)

给你一些关系 \((a, b)\)，代表 \(a\) 比 \(b\) 强。问最强的人，无法判断则输出 \(-1\)。

判断入度为 \(0\) 的点的个数即可。

//The code was written by yifan, and yifan is neutral!!!

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
#define bug puts("NOIP rp ++!");

template<typename T>
inline T read() {
    T x = 0;
    bool fg = 0;
    char ch = getchar();
    while (ch < '0' || ch > '9') {
        fg |= (ch == '-');
        ch = getchar();
    }
    while (ch >= '0' && ch <= '9') {
        x = (x << 3) + (x << 1) + (ch ^ 48);
        ch = getchar();
    }
    return fg ? ~x + 1 : x;
}

int n, m, maxx;
int in[100];

int main() {
    n = read<int>(), m = read<int>();
    for (int i = 1, a, b; i <= m; ++ i) {
        cin >> a >> b;
        ++ in[b];
    }
    for (int i = 1; i <= n; ++ i) {
        if (!in[i]) {
            if (maxx) {
                puts("-1");
                return 0;
            }
            maxx = i;
        }
    }
    cout << maxx << '\n';
    return 0;
}

C - Approximate Equalization 2

C - Approximate Equalization 2 (atcoder.jp)

有一个操作，选择最大的数和最小的数，然后最小的数加一，最大的数减一，问最少操作多少次，可以使得最大的数和最小的数差值最大是 \(1\)。

求商和余数，有多少个余数就代表有多少个数只到达商 \(+ 1\) 的位置。

//The code was written by yifan, and yifan is neutral!!!

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
#define bug puts("NOIP rp ++!");

template<typename T>
inline T read() {
    T x = 0;
    bool fg = 0;
    char ch = getchar();
    while (ch < '0' || ch > '9') {
        fg |= (ch == '-');
        ch = getchar();
    }
    while (ch >= '0' && ch <= '9') {
        x = (x << 3) + (x << 1) + (ch ^ 48);
        ch = getchar();
    }
    return fg ? ~x + 1 : x;
}

const int N = 2e5 + 5;

ll sum, ans;
ll a[N];

int main() {
    int n = read<int>();
    for (int i = 1; i <= n; ++ i) {
        a[i] = read<ll>();
        sum += a[i];
    }
    sort(a + 1, a + n + 1);
    ll res = sum % n, zc = sum / n;
    for (int i = 1; i <= n - res; ++ i) {
        ans += abs(zc - a[i]);
    }
    for (int i = n - res + 1; i <= n; ++ i) {
        ans += abs(a[i] - zc - 1);
    }
    cout << ans / 2 << '\n';
    return 0;
}

D - Odd or Even

D - Odd or Even (atcoder.jp)

这是一道交互题，本人是第一次做这种新题型。

题目大意：有一个序列 \(A\)，每一个元素只可能是 \(0\) 或者 \(1\)，现在，你可以从中任选 \(k\) 个位置，通过询问这 \(k\) 个位置的数它们的和的奇偶性，来判断每个元素是 \(0\) 还是 \(1\)。

对于前 \(k + 1\) 个数，我们一共选 \(k + 1\) 次，第 \(i\) 次空出第 \(i\) 个位置，计算出这些数的奇偶性，再依次异或，来得出前 \(k + 1\) 个数的奇偶性，后面的数只要把最后一个数换掉即可。

//The code was written by yifan, and yifan is neutral!!!

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
#define bug puts("NOIP rp ++!");

template<typename T>
inline T read() {
    T x = 0;
    bool fg = 0;
    char ch = getchar();
    while (ch < '0' || ch > '9') {
        fg |= (ch == '-');
        ch = getchar();
    }
    while (ch >= '0' && ch <= '9') {
        x = (x << 3) + (x << 1) + (ch ^ 48);
        ch = getchar();
    }
    return fg ? ~x + 1 : x;
}

const int N = 1010;

int n, k;
int ans[N];

void out(vector<int> x) {
    int siz = x.size();
    for (int i = 0; i < siz; ++ i) {
        cout << x[i] << " \n"[i + 1 == siz];
    }
}

int main() {
    n = read<int>(), k = read<int>();
    auto send = [&](vector<int> v) {
        for (int &x : v) {
            ++ x;
        }
        cout << "? ";
        out(v);
        cout.flush();
        int x;
        x = read<int>();
        return x;
    };
    vector<int> ans(n);
    int r = 0;
    for (int i = 0; i < k + 1; ++ i) {
        vector<int> v;
        for (int j = 0; j < k + 1; ++ j) {
            if (i != j) {
                v.emplace_back(j);
            }
        }
        ans[i] = send(v);
        r ^= ans[i];
    }
    for (int i = 0; i < k + 1; ++ i) {
        ans[i] ^= r;
    }
    vector<int> v(k);
    int s = 0;
    for (int i = 0; i < k - 1; ++ i) {
        v[i] = i;
        s ^= ans[i];
    }
    for (int i = k + 1; i < n; ++ i) {
        v.back() = i;
        int t = send(v);
        ans[i] = s ^ t;
    }
    cout << "! ";
    out(ans);
    cout.flush();
    return 0;
}

E 的题目……说实话，没读懂……