Moe's CF Life

喵~ 主人，下午好呀！今天我们来看一道关于安娜和萨沙的趣题，感觉就像是两个小猫在玩毛线球呢，嘻嘻。这道题是 Codeforces 上的 1931E - Anna and the Valentine's Day Gift，让我们一起来看看怎么帮安娜赢得游戏吧！

题目大意

简单来说，就是安娜和萨沙玩一个数字游戏啦。

初始状态：有一个包含 $n$ 个整数的列表 $a$ 。
安娜的回合：安娜必须选择列表里的一个数，然后把它按位翻转。比如说，123 变成 321，1580 就会变成 851（前面的 0 会被去掉哦）。
萨沙的回合：萨沙必须选择列表里两个不同的数，把它们拼接成一个更大的数，然后放回列表里。比如，选了 2007 和 19，他可以合成 200719 或者 192007，然后用这个新数替换掉原来的两个。这样列表里的数字总数就减少了一个。
游戏结束：当列表里只剩下一个数字时，游戏就结束啦。
胜利条件：如果最后剩下的那个数字大于 $m$ （技术上讲是 $\ge 10^m$ ，但我们后面会发现其实就是位数大于 $m$ ），那么萨沙赢。否则，安娜赢。

安娜先手，而且两个人都超级聪明，会用最优策略来玩。我们要判断最后谁会赢~

解题思路

这道题看起来像个复杂的博弈论问题，但其实只要我们抓住了核心，就会变得很简单哦，喵~

核心矛盾：最终数字的位数

首先我们来想一下，决定胜负的是什么？是最后那个超级大数字的位数。萨沙想让它尽可能长，而安娜则希望它尽可能短。

萨沙的操作：他把两个数 A 和 B 拼起来。不管怎么拼，新数字的位数就是 A 的位数加上 B 的位数。经过 n-1 次拼接后，最终的那个大数字，它的总位数其实就是最初那 n 个数字的位数之和！等等，好像有哪里不对……
安娜的操作：安娜翻转一个数字。
- 如果数字末尾没有 0，比如 123 翻转成 321，位数不变。
- 但如果数字末尾有 0，比如 1200 翻转成 21，位数从 4 减少到了 2！减少的位数正好等于末尾 0 的个数。

所以，整个游戏的关键点就浮出水面啦： 最终数字的总位数 = 初始所有数字的总位数之和 - 安娜成功翻转带来的总位数减少量

安娜的目标是让位数减少量最大化，而萨沙的目标是让它最小化。

玩家的最优策略

现在，游戏就变成了一场争夺“位数减少量”的比赛！这些“位数减少量”只来自于那些末尾有 0 的数字。我们可以把每个数字的末尾 0 的个数看作一个可以争夺的“分数”。

让我们把所有数字的末尾 0 的个数（也就是潜在的位数减少量）找出来，从大到小排个序，得到一个列表 Z = {z_1, z_2, z_3, ...}，其中 z_1 >= z_2 >= ...。

现在我们来模拟一下两个聪明蛋的对决：

安娜的回合 (先手)：安娜想让减少的位数最多。她会怎么做呢？当然是选择当前能提供最大减少量的数字来翻转啦！也就是对应 z_1 的那个数字。她翻转了这个数字，就成功获得了 z_1 的位数减少。
萨沙的回合：萨沙的目标是阻止安娜。他看到安娜接下来最想翻转的，肯定是对应 z_2 的数字。他要怎么阻止呢？他的操作是合并两个数。只要他把对应 z_2 的那个数字和任何其他一个数字合并掉，安娜就再也不能单独翻转它了！所以，为了让安娜的收益最小，萨沙会选择消除掉对她来说最诱人的选项，也就是 z_2 对应的数字。
安娜的下一回合：z_1 已经被她用掉了，z_2 被萨沙破坏了。那她现在能选择的、能带来最大收益的就是 z_3 啦。于是她翻转了 z_3 对应的数字。
萨沙的下一回合：他会同样地破坏掉安娜的下一个最优选择，也就是 z_4。

这个过程会一直持续下去。我们发现了规律：

安娜拿走了 z_1, z_3, z_5, ... (所有奇数位置的“分数”)
萨沙破坏了 z_2, z_4, z_6, ... (所有偶数位置的“分数”)

所以，安娜最终能获得的总位数减少量就是 z_1 + z_3 + z_5 + ...。

算法步骤

总结一下，我们的解题步骤就是：

遍历所有输入的数字，计算它们最初的位数总和 total_digits。
对于每个数字，数一下它末尾有几个 0。把所有大于 0 的末尾零个数收集到一个列表里。
把这个列表从大到小排序。
从这个排好序的列表里，把所有偶数索引（0, 2, 4, ...）上的值加起来，得到安娜能实现的总位数减少量 reduction。（注意哦，列表里第1、3、5...个元素，在程序里是索引为0、2、4...的元素）。
用 total_digits - reduction 得到最终数字的位数 final_digits。
判断 final_digits > m 是否成立。如果成立，萨沙赢；否则，安娜赢。

这样一来，一个复杂的博弈问题就变成了一个简单的贪心和排序问题啦，是不是很神奇，喵~

题解代码

这是解题思路对应的 C++ 代码，我已经加上了一些可爱的注释哦！

cpp

#include <iostream>
#include <vector>
#include <string>
#include <algorithm>
#include <functional>

void solve() {
    int n;
    long long m;
    std::cin >> n >> m;

    long long total_digits = 0;
    std::vector<int> trailing_zeros; // 用来存放所有末尾0的个数（潜在的位数减少量）

    for (int i = 0; i < n; ++i) {
        std::string s;
        std::cin >> s;

        // 1. 累加初始总位数
        total_digits += s.length();

        // 2. 计算每个数末尾0的个数
        int z = 0;
        for (int j = s.length() - 1; j >= 0; --j) {
            if (s[j] == '0') {
                z++;
            } else {
                break;
            }
        }
        
        if (z > 0) {
            trailing_zeros.push_back(z);
        }
    }

    // 3. 把所有“位数减少量”从大到小排序
    std::sort(trailing_zeros.begin(), trailing_zeros.end(), std::greater<int>());

    long long reduction = 0;
    // 4. 安娜拿走奇数位置的，也就是索引为 0, 2, 4, ... 的
    for (size_t i = 0; i < trailing_zeros.size(); i += 2) {
        reduction += trailing_zeros[i];
    }

    // 5. 计算最终位数
    long long final_digits = total_digits - reduction;

    // 6. 判断胜负
    // 最终数字位数 > m 等价于 最终数字 >= 10^m
    if (final_digits > m) {
        std::cout << "Sasha\n";
    } else {
        std::cout << "Anna\n";
    }
}

int main() {
    std::ios_base::sync_with_stdio(false);
    std::cin.tie(NULL);

    int t;
    std::cin >> t;
    while (t--) {
        solve();
    }

    return 0;
}

题目大意 ​

解题思路 ​

核心矛盾：最终数字的位数 ​

玩家的最优策略 ​

算法步骤 ​

题解代码 ​

相关知识点介绍 ​