2021CCPC湘潭全国邀请赛 G Game

题目描述

http://acm.hdu.edu.cn/showproblem.php?pid=6944

Solution

注意到 $99$ 和 $999$ 等都是拿了奇数个 $9$，不会改变操作数的奇偶性，且操作一定会强制进行完

所以我们直接判断一下操作总数的奇偶性即可

#include <iostream>
#include <vector>
#define maxn 200010
#define ll long long
using namespace std;

int n, a[maxn];

void work() {
    for (int i = 1; i <= n; ++i) cin >> a[i];
    vector<int> A[9]; ll ans = 0; 
    for (int i = 1; i <= n; ++i) A[a[i] % 9].push_back(a[i]);
    for (int i = 0; i < 9; ++i) {
        for (auto u : A[i]) ans += (u - 1) / 9;
        ll sz = A[i].size();
        ans -= sz * (sz - 1) / 2; 
    }
    if (ans & 1) cout << "A" << "\n";
    else cout << "B" << "\n"; 
}

int main() {
    while (cin >> n) work(); 
    return 0;
}