AtCoder Beginner Contest 313 A-E Code

比赛链接：AtCoder Beginner Contest 313 - AtCoder

A：

#include <bits/stdc++.h>
using namespace std;

int main()
{
    cin.tie(0);
    ios::sync_with_stdio(false);
    
    int n;
    cin >> n;
    
    int p1;
    cin >> p1;
    
    int maxp = 0;
    for (int i = 2; i <= n; ++ i) {
        int p;
        cin >> p;
        maxp = max(maxp, p);
    }
    
    cout << max(0, maxp + 1 - p1) << endl;
    
    return 0;
}

B：

#include <bits/stdc++.h>
using namespace std;

int main()
{
    cin.tie(0);
    ios::sync_with_stdio(false);
    
    int n, m;
    cin >> n >> m;
    vector<int> din(n+1);
    
    while (m--) {
        int a, b;
        cin >> a >> b;
        ++ din[b];
    }
    
    int id, num = 0;
    for (int i = 1; i <= n; ++ i) {
        if (!din[i]) {
            id = i, ++ num;
        }
    }
    
    cout << (num == 1 ? id : -1) << endl;
    
    return 0;
}

C：

#include <bits/stdc++.h>
using namespace std;

int main()
{
    cin.tie(0);
    ios::sync_with_stdio(false);
    
    int n;
    cin >> n;
    
    vector<int> a(n);
    long long sum = 0;
    for (int i = 0; i < n; ++ i) {
        cin >> a[i];
        sum += a[i];
    }
    
    vector<int> b(n);
    for (int i = 0; i < n; ++ i) {
        if (i < n - sum % n) b[i] = sum / n;
        else b[i] = sum / n + 1;
    }
    
    long long ans = 0;
    sort(a.begin(), a.end());
    for (int i = 0; i < n; ++ i) {
        if (a[i] > b[i]) break;
        ans += b[i] - a[i];
    }
    cout << ans << endl;
    
    return 0;
}

D：

#include <bits/stdc++.h>
using namespace std;

int main()
{
    // cin.tie(0);
    // ios::sync_with_stdio(false);
    
    // [1,k+1] 缺1,2,3,···,k  -->  1与2,3,···,k是相同还是相异  -->  1,2,3,···,k
    // [1,k], [2,k+1], ···, [n-k+1,n]  -->  1与k+1, 2与k+2, ···, n-k与n
    
    int n, k;
    cin >> n >> k;
    
    // 返回包含[l,r]区间但除去x的数的vector
    auto q = [](int l, int r, int x) -> vector<int> {
        vector<int> v;
        for (int i = l; i <= r; ++ i) {
            if (i == x) continue;
            v.push_back(i);
        }
        return v;
    };
    
    // 输出查询
    auto query = [](vector<int> &v) -> void {
        cout << "? ";
        for (int x : v) {
            cout << x << ' ';
        }    
        cout << endl;
    };
    
    map<vector<int>, int> mp;
    for (int i = 1; i <= k; ++ i) {
        vector<int> v = q(1, k+1, i);
        query(v);
        int T;
        cin >> T;
        mp[v] = T;
    }
    
    for (int i = 1; i <= n - k + 1; ++ i) {
        vector<int> v = q(i, i+k-1, 0);
        if (mp.count(v) > 0) continue;
        query(v);
        int T;
        cin >> T;
        mp[v] = T;
    }
    
    int T1 = mp[q(1, k+1, 1)];
    int cnt1 = 1, cnt2 = 0;
    for (int i = 2; i <= k; ++ i) {
        if (T1 == mp[q(1, k+1, i)]) ++ cnt1;
        else ++ cnt2;
    }
    
    vector<int> A(n+1);
    int A1k = mp[q(1, k, 0)];
    A[1] = A1k == (cnt1 & 1);
    
    for (int i = 2; i <= k; ++ i) {
        if (T1 == mp[q(1, k+1, i)]) A[i] = A[1];
        else A[i] = !A[1];
    }
    
    for (int i = 1; i <= n - k; ++ i) {
        if (mp[q(i, i+k-1, 0)] == mp[q(i+1, i+k, 0)]) {
            A[i+k] = A[i];
        } else {
            A[i+k] = !A[i];
        }
    }
    
    cout << "! ";
    for (int i = 1; i <= n; ++ i) {
        cout << A[i] << ' ';
    }
    cout << endl;
    
    return 0;
}

E：

#include <bits/stdc++.h>
using namespace std;

int main()
{
    cin.tie(0);
    ios::sync_with_stdio(false);
    
    int n;
    cin >> n;
    
    string s;
    cin >> s;
    s = ' ' + s;
    
    bool flag = true;
    for (int i = 1; i < n; ++ i) {
        if (s[i] > '1' && s[i+1] > '1') {
            flag = false;
            break;
        }
    }
    
    if (!flag) {
        cout << -1 << endl;
    } else {
        const int p = 998244353;
        long long ans = 1;
        for (int i = n - 1; i >= 1; -- i) {
            ans = (ans + 1 + (s[i+1] - '1') * ans) % p;
        }
        cout << ans - 1 << endl;
    }
    
    return 0;
}