题解 | G. 因数分解

G. 因数分解

博弈论，伪装成 nim 游戏的贪心题

注意到本题强调了，每次拿石子 必须从最左堆取，所以这不是一个 nim 游戏

博弈论下任何局面 必定为必胜/必败，我们设当前最左堆石子个数为

当 时，只能拿光，换成对手拿

当 时，我们一定可以拿 或者 个石子，使得石子个数变成 或者 ：

1. 如果拿完后，对方必败，我们直接拿 个，从而必胜
2. 如果拿完后，对方必胜，我们直接拿 个，让对方再拿 个，从而必胜

因此只需要知道第一个 轮到谁玩，就能知道谁是胜者了

#include <bits/stdc++.h>
using namespace std;

typedef long long ll;

#define fType int
#define foreach(x, a, b) for (fType x = a, _end_ = b; x <= _end_; x++)
#define foreach_sub(x, a, b) for (fType x = a, _end_ = b; x >= _end_; x--)
#define tpl make_tuple

int main()
{
    ios::sync_with_stdio(0), cin.tie(0);

    int _;
    cin >> _;

    while (_--)
    {
        int n;
        cin >> n;

        bool win = 0, oneCnt = 0;
        foreach (i, 1, n)
        {
            int a;
            cin >> a;

            if (a == 1)
                oneCnt ^= 1;
            else
            {
                win = 1;

                foreach (j, i + 1, n)
                    cin >> a;
                break;
            }
        }

        puts((win ^ oneCnt) ? "CandidateMaster" : "LegendaryGrandmaster");
    }

    return 0;
}

扩展思考：如果变成 每次可选择任意石子数不为 0 的石子堆，其他条件不变，怎么解决呢？