Moe's CF Life

喵~ 主人好呀！今天由我，你最可爱的小猫娘，来为你讲解一道关于博弈论的简单小题目 — 01 Game！ nya~

这道题就像和主人玩毛线球一样，规则很简单，但要找到必胜策略就需要动动小脑筋啦。别担心，跟着我的思路，一下子就能明白的，喵！

题目大意

Alice酱和Bob君在玩一个游戏，游戏开始时他们有一个只包含 '0' 和 '1' 的二进制字符串 s。

他们轮流进行操作，Alice酱先手。每一次操作，当前玩家必须从字符串中选择两个相邻且不同的字符（也就是 "01" 或者 "10"）并把它们删除。比如，如果字符串是 1011001，那么可以：

删除 10 -> 11001
删除 01 -> 11001
删除 10 -> 10101
删除 01 -> 10110

如果一个玩家轮到他的时候，已经不能进行任何操作了（也就是找不到相邻的 '0' 和 '1' 了），那么他就输了。

假设Alice酱和Bob君都非常聪明，会以最优策略来玩。我们需要判断，Alice酱最后能不能赢呢？如果能赢，就输出 "DA"，否则输出 "NET"。

解题思路

嘿嘿，主人，这只是一场披着博弈论外衣的简单计数游戏哦，喵~

我们来分析一下每次操作的本质是什么吧！

操作的核心：每次操作，我们都会删除一个 '0' 和一个 '1'。这意味着，无论我们选择删除哪一对 "01" 或者 "10"，字符串中 '0' 的数量会减一，'1' 的数量也会减一。总的字符数量减少了两个。
游戏结束的条件：玩家什么时候会输掉呢？当他找不到任何相邻的 "01" 或 "10" 时。这种情况只会在字符串中只剩下一种字符（全是 '0' 或者全是 '1'）或者字符串变空时发生。
总共能操作多少次？：既然每次操作都会消耗一个 '0' 和一个 '1'，那么游戏能进行的总操作次数，其实就取决于数量较少的那种字符有多少个，对吧？比如说，有3个 '0' 和5个 '1'，我们最多只能凑成3对 "01" 组合，所以最多只能操作3次。之后字符串里就只剩下 '1' 了，游戏结束。所以，总的操作次数就是 min(字符串中 '0' 的数量, 字符串中 '1' 的数量)。
最优策略是什么？：题目说两个人都玩得很好。但我们发现，只要字符串里同时存在 '0' 和 '1'，就必定至少有一对相邻的 "01" 或 "10"。所以，只要有机会，玩家就总能操作。因此，所谓的“最优策略”并不会影响游戏能进行的总轮数。总轮数在一开始就已经被 '0' 和 '1' 的数量决定啦！
判断胜负：现在问题就变得超级简单了！我们知道了总共可以进行 k = min(count('0'), count('1')) 次操作。
- Alice酱是先手，她进行第1、3、5、... 次操作。
- Bob君是后手，他进行第2、4、6、... 次操作。
如果总操作数 k 是奇数（1, 3, 5, ...），那么最后一轮操作（第 k 轮）必然是Alice酱完成的。她操作完之后，Bob君就没法操作了，所以 Alice酱赢！
如果总操作数 k 是偶数（0, 2, 4, ...），那么最后一轮操作（第 k 轮）会是Bob君完成的。他操作完后，轮到Alice酱时，她就没法操作了，所以 Alice酱输（也就是Bob君赢）！

所以，我们的任务就是数一数字符串里有多少个 '0' 和 '1'，然后看看它们数量的最小值是奇数还是偶数就可以啦，是不是很简单呀，喵~

题解代码

这是C++的实现代码，我已经加上了猫娘风味的注释哦，嘿嘿~

cpp

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

// 这个函数用来解决单个测试用例，喵~
void solve() {
    std::string s;
    std::cin >> s; // 读入Alice和Bob要玩的字符串s

    int count0 = 0;
    int count1 = 0;

    // 遍历字符串，数一数'0'和'1'分别有多少个
    // 就像小猫数鱼干一样认真！
    for (char c : s) {
        if (c == '0') {
            count0++;
        } else {
            count1++;
        }
    }

    // 游戏的总移动次数取决于数量较少的那个字符
    // 比如有3个'0'和5个'1'，最多只能移3次
    int total_moves = std::min(count0, count1);

    // 现在来判断谁会笑到最后啦
    // Alice先手，所以如果总移动次数是奇数，她会进行最后一次移动
    if (total_moves % 2 != 0) {
        // 总移动次数是奇数，Alice酱赢！DA！(YES!)
        std::cout << "DA\n";
    } else {
        // 总移动次数是偶数（或者0次），Bob君赢！NET！(NO!)
        std::cout << "NET\n";
    }
}

int main() {
    // 这两行是为了让输入输出快一点，就像猫咪跑得飞快！
    std::ios_base::sync_with_stdio(false);
    std::cin.tie(NULL);

    int t;
    std::cin >> t; // 有t组游戏要判断
    while (t--) {
        solve(); // 一组一组地解决
    }

    return 0;
}

知识点小课堂

这道题虽然简单，但背后也藏着一些有趣的知识点呢，主人快来听听！

公平组合游戏 (Impartial Game) 这个游戏就是一个典型的公平组合游戏。它的特点是：
- 两名玩家交替行动。
- 在游戏的任意一个确定状态下，可以进行的行动集合只与当前状态有关，与轮到哪个玩家无关。比如在这个题目里，只要有 "01" 或 "10"，不管是 Alice 还是 Bob 都可以删除它。
- 游戏会在有限步内结束，不会无限循环。
- 以最后无法操作者为负。
对于这类游戏，我们常常可以通过分析游戏状态来找到必胜或必败策略。这道题就是通过分析发现，游戏总步数是固定的，所以我们只需要看总步数的奇偶性就能判断先手是否必胜。
博弈论中的奇偶性分析 (Parity Analysis in Game Theory) 很多简单的博弈问题最后都可以归结为对某个量的奇偶性分析。就像这道题，我们把复杂的游戏规则简化为了一个数字——总操作数。然后通过判断这个数字的奇偶性，直接得出了结论。这是一种非常强大和常见的思想哦！当主人以后遇到类似的轮流操作问题时，可以想一想，是不是有什么东西的数量在奇偶性上发生了规律性的变化呢？

好啦，这次的题解就到这里啦！希望主人能够喜欢。如果还有什么问题，随时可以再来找我哦，喵~ ❤

题目大意 ​

解题思路 ​

题解代码 ​

知识点小课堂 ​

题目大意

解题思路

题解代码

知识点小课堂