CF1931E Anna and the Valentine's Day Gift

· · 题解

思路

容易发现，如果位数不能减少，那么无论两人如何操作，是不会改变最终结果的，所以当总位数大于 m 时，Sasha 会获胜，否则，Anna 会获胜。

首先发现，对于不是十的倍数的数，无论 Anna 如何操作，位数是不会改变的，但是如果是十的倍数，我们假设 x 是其末尾连续零的个数，那么颠倒后会使位数减少 x。

所以如果是 Anna 操作，那么她一定会选择末尾连续零个数最多的数。

再思考 Sasha 会如何操作，如果她将一个末尾有零的数放在某个数的前面，那么这些零就无法变成前导零从而减少位数了，所以 Sasha 也会选择一个末尾连续零个数最多的数。

所以我们只需要提前统计好总位数 res 以及各个数字的末尾连续零个数。

然后排个序，从大到小，将 res 减去第奇数个数字的末尾连续零个数。

最后看 res 与 m 关系即可。

AC code

#include<bits/stdc++.h>
using namespace std;
int T,n,m,a,zero[200005],res,ff;
inline void sol()
{
    scanf("%d%d",&n,&m),res=0;
    for(int i=1;i<=n;++i)
    {
        scanf("%d",&a),ff=1;
        while(a)
        {
            if(a%10==0) zero[i]+=ff;
            else ff=0;
            ++res,a/=10;
        }
    }
    sort(zero+1,zero+n+1),reverse(zero+1,zero+n+1);
    for(int i=1;i<=n;++i) res-=(i&1)*zero[i],zero[i]=0;
    puts((res<=m)?"Anna":"Sasha");
}
int main()
{
    scanf("%d",&T);
    while(T--) sol();
    return 0;
}