1 条题解

  • 0
    @ 2024-9-11 22:48:25

    这是一个经典的博弈论问题,可以使用Nim游戏的思想来解决。

    Nim游戏是一个二人博弈,游戏的初始状态为有 nn 堆石子,每堆石子的数量可以是任意自然数。双方轮流进行行动,每次行动可以从任意一堆石子中取走若干个石子(不能不取),取走最后一个石子的人获胜。

    根据Nim游戏的定理,如果所有堆的石子数量的异或和为 00 ,则先手必败,否则先手必胜。这个定理可以通过数学归纳法证明。

    对于这个问题,我们可以将每堆钱看做一堆石子,那么问题就转化为了Nim游戏。如果所有堆的钱数异或和为 00,则Rarity必输光光,否则Rarity必拿回压岁钱。

    #include <iostream>
    
    using namespace std;
    
    int main(void)
    {
        int t;
        cin >> t;
        for (int i=0;i<t;i++)
        {
            int n;
            cin>>n;
            int res = 0;
            for (int j=0;j<n;j++)
            {
                int x;
                cin >> x;
                res ^= x;
            }
            if (res)
                cout << "NO" << endl;
            else
                cout << "YES" << endl;
        }
        return 0;
    }
    
    • 1

    信息

    ID
    103
    时间
    1000ms
    内存
    256MiB
    难度
    5
    标签
    递交数
    29
    已通过
    15
    上传者