Contestant. Unrated, with problem C removed.

A. Hayato and School

题意

给定一个数组 \(a\)，输出一对下标，满足下标对应的元素的和为奇数。保证数组 \(a\) 至少有 \(3\) 个元素。

思路

分类讨论：

奇数元素数量大于 \(3\)，直接输出前三个奇数。
偶数只有 \(1\) 个，或者没有奇数，无解。
输出一对”奇，偶，偶“即可。

时间复杂度：\(O(n)\)

对应AC代码

#include <bits/stdc++.h>

using namespace std;

const int N = 310;

pair<int, int> a[N], b[N];

#define ll long long

int main() {
    ios::sync_with_stdio(false), cin.tie(0), cout.tie(0);
    int t;
    cin >> t;
    while(t --){
        int n;
        cin >> n;
        int o = 0, e = 0;
        for(int i=1;i<=n;i++){
            int p;
            cin >> p;
            if(p % 2 == 0) a[e ++] = {p, i};
            else b[o ++] = {p, i};
        }
        if(o >= 3){
            cout << "YES" << '\n';
            cout << b[0].second << " " << b[1].second << " " << b[2].second << '\n';
        }else if(o == 0 || e == 1){
            cout << "NO" << '\n';
        }else{
            cout << "YES" << '\n';
            cout << b[0].second << " " << a[0].second << " " << a[1].second << '\n';
        }
    }
}

这么签的题居然WA了，淦

B. GCD Partition

题意

给定一个数组 \(a\)，将数组 \(a\) 切割为任意数量的连续段，满足相邻区间头尾没有交集，对每段分别求和，输出求和后所有和的最大公约数的最大值。

思路

可以证明，分隔为两段后可以保证取到 \(gcd_{\max}\)，因此我们枚举即可。

若需略微证明，因求出的 \(gcd\) 一定是 \(sum_a / d\) (\(d\) 是段数) 的因数，显然 \(d\) 越小，能遍历到的因数就更多，所以分两段即可。

既然分两段，暴力即可。

时间复杂度：\(O(n \times f(x)),f(x)指gcd函数复杂度\)

对应AC代码

import java.math.BigInteger;
import java.util.*;

public class Main{

    private static long gcd(long a, long b) {
        while(b != 0) {
            long tmp = a;
            a = b;
            b = tmp % b;
        }
        return a;
    }

    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        int t = scanner.nextInt();
        while (t-- > 0) {
            int n = scanner.nextInt();
            long tot = 0;
            long[] a = new long[n + 1];
            for(int i=1;i<=n;i++) tot += a[i] = scanner.nextInt();
            long ans = 1, sum = 0;
            for(int i=1;i<n;i++){
                sum += a[i];
                ans = Math.max(ans, gcd(sum, tot - sum));
            }
            System.out.println(ans);
        }
    }

}

怎么还会去想分段怎么分呢，真是，淦

D. Bit Guessing Game

题意

互动游戏，对于一个未知数 \(n\)，有最多 \(30\) 次的猜测机会。对于每次给出的二进制下 \(n\) 中 \(1\) 的个数，允许减去一个值 \(x\)，使 \(n=n-x\)，\(n\) 值得改变会影响下一轮数量的给出。若能确定答案，输出即可。

思路

我们考虑到题给范围为 \(10^9\)，此时二进制的最大位数恰好为 \(30\)，那么我们不妨枚举所有位的情况。

首先，对于一个二进制数，我们引入一个结论：

若某一位为 \(1\)，我们将该位减去后，一定可以保证 \(1\) 的数量恰好 \(-1\)；

而若某一位为 \(0\)，则恰好相反，我们找不出有一种情况满足 \(1\) 的数量恰好 \(-1\)。

因此，我们可以从低位向高位枚举，若满足条件，那么将目标数字的该位标为 \(1\)，否则，在下一次猜测的时候，我们需要减去原先被我们减去的值，以达到反悔的目的。而显然，无论我们减去多少原先的值，最后剩下的数一定大于 \(0\)，因此方案可行。

时间复杂度：\(O(\log_2n)\)

对应AC代码

import java.math.BigInteger;
import java.util.*;

public class Main{


    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        int t = scanner.nextInt();
        while (t-- > 0) {
            int cnt = scanner.nextInt();
            int ans = 0, b = 0, on = 0;
            while(cnt > 0){
                System.out.printf("- %d\n", (1 << on) - b);
                System.out.flush();
                int now = scanner.nextInt();
                if(now == -1) return; //wa了...
                if(cnt - now == 1) {
                    b = 0;
                    cnt = now;
                    ans += 1 << on;
                }
                else b += (1 << on) - b;
                on ++;
            }
            System.out.printf("! %d\n", ans);
            System.out.flush();
        }
    }

}

我跟自己写的代码玩游戏.jpg