Codeforces Round #846 (Div. 2)【A - D】

unrated 了……

比赛链接：https://codeforces.com/contest/1780

A. Hayato and School

题解

特判两种答案不存在的情况。

代码

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

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int t;
    cin >> t;

    while (t--) {
        int n;
        cin >> n;

        vector<int> odd, even;
        for (int i = 0; i < n; i++) {
            int x;
            cin >> x;
            (x & 1 ? odd : even).push_back(i);
        }

        if (odd.empty() or (odd.size() == 2 and even.size() == 1)) {
            cout << "NO" << "\n";
        } else {
            cout << "YES" << "\n";
            if (odd.size() >= 3) {
                cout << odd[0] + 1 << ' ' << odd[1] + 1 << ' ' << odd[2] + 1 << "\n";
            } else if (even.size() >= 2) {
                cout << odd[0] + 1 << ' ' << even[0] + 1 << ' ' << even[1] + 1 << "\n";
            }
        }
    }

    return 0;
}

B. GCD Partition

题解

合并相邻的两段不改变 gcd，所以只考虑分两段的情况即可。

代码

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

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int t;
    cin >> t;

    while (t--) {
        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];
        }

        long long ans = 0, cur = 0;
        for (int i = 0; i < n - 1; i++) {
            cur += a[i];
            ans = max(ans, gcd(cur, sum - cur));
        }
        cout << ans << "\n";
    }

    return 0;
}

C. Bon appetit!

题解

贪心的做法可以试下这两组测试样例：

9 3

1 1 1 1 1 2 2 2 2

4 3 2

9 4

1 1 1 1 1 2 2 2 2

3 2 2 2

分别对应 lower_bound 桌子容量和某道菜喜欢人数的情况。

D. Bit Guessing Game

题解

逐位确定，减去一位后有三种情况：

• 总位数减一，说明该位为 1
• 总位数不变，说明该位和前一位为 10
• 总位数加一，说明该位和前两位为 100
• ……

代码

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

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int t;
    cin >> t;

    while (t--) {
        int cnt;
        cin >> cnt;

        int n = cnt;

        int ans = 0;
        auto ask = [](int i) {
            cout << "- " << (1 << i) << endl;
            int x;
            cin >> x;
            return x;
        };
        for (int time = 0, i = 0; time < cnt; time++) {
            int m = ask(i);
            ans |= (1 << (i + m - (n - 1)));
            i += m - (n - 1) + 1;
            n = m;
        }
        cout << "! " << ans << endl;
    }

    return 0;
}