CF1931E 【Anna and the Valentine's Day Gift】 题解

MorLeaves · 2024-02-15 21:00:25 · 题解

题意：

有一个长度为 n 的数列 a_1~ a_n ， \tt{Sasha} 与 \tt{Anna} 在玩一个游戏。

双方先后轮流进行操作，直到剩下一个数时，若这个数不小于（\ge） 10^m ，则 \tt{Sasha} 获胜；反之 \tt{Anna} 获胜，输出获胜者的名字。

思路：

由题意可以发现，其实 \tt{Anna} 就是要让最后的数较小， \tt{Sasha} 要让最后的数较大。

• 观察 \tt{Anna} 所进行的操作，能发现：如果没有删去前导零，则该数操作后位数不会变；如果删去了，则位数会变小。位数变小对比位数不变，显然是前者更有利于 \tt{Anna} 取胜（能让该数变得更小），并且只有位数变小才能使最终得到的数的位数进行永久性的减小（可能有点抽象），所以 \tt{Anna} 一定会选择当前所有 a_i 中后导零数量最多的那个数进行操作，操作后将会使该数无后导零。

• 观察 \tt{Sasha} 所进行的操作，和 \tt{Anna} 类似，他的任务就是让 \tt{Anna} 不那么顺利的进行操作，也就是他要将一个后导零最多的数的后导零数量减少，其实他每次都可以将该数的后导零减少至 0 。可以发现， \tt{Anna} 每次操作完后，都会留下一个后导零数量为 0 的数，因此 \tt{Sasha} 可以选择后导零数量最多和后导零数量为 0 的这两个数进行操作，将无后导零的这个数放后，最终可以“拼”出一个无后导零的新数。

至此，双方每次的最佳操作都已确定。因为最后只需判断是否 \ge 10^m ，所以只需计算出最终数的位数即可，注意 10^m 有 (m+1) 位数。因为要计算每个数的后导零数量和每个数的位数，所以每个数用 string 类型存储更加方便，记得多测要清空。

CODE:

最后奉上带注释的代码。

#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cstring>
#include<string>
using namespace std;
int T,n,m,k[200005];// k数组存储每个数的后导零数量 
string s[200005];//用 string 类型存储每个数 
int main() {
    scanf("%d",&T);
    while(T--) {
        scanf("%d %d",&n,&m);
        int sum=0;//用来统计最终数的位数 
        for(int i=1;i<=n;i++) {
            cin>>s[i];
            sum+=s[i].size();//先加上所有数的总位数 
            for(int j=s[i].size()-1;j>=0;j--) {//计算每个数的后导零数量 
                if (s[i][j]=='0') k[i]++;
                else break;
            }
        }
        sort(k+1,k+n+1);//将后导零数量进行排序 
        for(int i=n;i>=1;i-=2) sum-=k[i];//对应 Anna 的每次操作，在 Anna 每次操作后 sum 减少当前后导零数量
        if (sum>=m+1) printf("Sasha\n");//记得是 m+1  
        else printf("Anna\n");
        fill(k+1,k+n+1,0);//多测清空，等价于for(int i=1;i<=n;i++) k[i]=0;
    }
    return 0;//完美结束撒花！！！ 
}