0%

Codeforces - Round 846 Div 2

Contestant. Unrated, with problem C removed.

A. Hayato and School

题意

给定一个数组 ,输出一对下标,满足下标对应的元素的和为奇数。保证数组 至少有 个元素。

思路

分类讨论:

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

时间复杂度:

对应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

题意

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

思路

可以证明,分隔为两段后可以保证取到 ,因此我们枚举即可。

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

既然分两段,暴力即可。

时间复杂度:

对应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

题意

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

思路

我们考虑到题给范围为 ,此时二进制的最大位数恰好为 ,那么我们不妨枚举所有位的情况。

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

若某一位为 ,我们将该位减去后,一定可以保证 的数量恰好

而若某一位为 ,则恰好相反,我们找不出有一种情况满足 的数量恰好

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

时间复杂度:

对应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