CF1931E Anna and the Valentine's Day Gift 题解

Eason_cyx · 2024-02-14 11:21:39 · 题解

简单博弈（？，橙吧。

先考虑 Anna 的最佳操作。

Anna 要使这个数的位数尽可能小，那么能使位数变小的，只有去掉后面的 0 了。由于操作次数有限，那么贪心，Anna 需要从 0 个数最多的数开始操作。但是，由于 Sasha 同样是最佳策略，当 Anna 操作完最多的之后，Sasha 可以将第 2 多的合并，于是 Anna 再操作第 3 多的，以此类推。

那么我们只需先算出所有数的初始总位数和 0 个数，将 0 个数排序后，用总位数减掉 Anna 可以去掉的 0 个数，即为最终位数。

注意：如果最终位数 \ge m，就可以认为这个数一定 \ge10^m。

时间复杂度 O(Tn\log n)，其中 n\log n 为排序复杂度。

#include <bits/stdc++.h>
using namespace std;
int a[200005],zeronum[200005];
int main() {
    int T; cin >> T;
    while(T--) {
        memset(zeronum,0,sizeof zeronum);
        int n,m; cin >> n >> m;
        int siz = 0;
        for(int i = 1;i <= n;i++) {
            cin >> a[i];
            int cur = a[i];
            while(cur) {
                siz++;
                cur /= 10;
            }
        }
        if(siz < m) {
            cout << "Anna" << endl;
            continue;
        }
        for(int i = 1;i <= n;i++) {
            while(a[i] % 10 == 0) {
                zeronum[i]++;
                a[i] /= 10;
            }
        }
        sort(zeronum+1,zeronum+n+1,greater<int>());
        for(int i = 1;i <= n;i += 2) siz -= zeronum[i];
        // cout << siz;
        if(siz <= m) cout << "Anna" << endl;
        else cout << "Sasha" << endl;
    }
    return 0;
}

AC Record