题解：B4227 [常州市赛 2024] 游戏

· · 题解

题意

现在有一个长度为 2 \times n 的序列。有两个人 Alice 和 Bob 在博弈。由 Alice 先手开始两人轮流从序列中删掉一个数，如果在 Bob 的某一次操作后序列变成了一个回文序列，则 Bob 胜利。反之，如果在序列长度等于二时 Bob 还未胜利则 Alice 胜利。两人都采用最优策略的情况下要求判断 Alice 是会赢还是会输。

思路

我们发现由于 2 \times n 为偶数，所以每一次 Bob 操作完之后序列的长度一定为偶数。然后我们考虑什么时候这个序列最有可能是回文串，一定是序列长度等于二且剩下的两个数相同。

我们先猜个结论，如果序列在长度不为二时为回文串，那么 Bob 存在一种策略使得这个序列被删到两个数时还是回文串。由于序列长度此时为偶数，这个序列中所有的数字的个数均为偶数。因此我们接下来每次操作只需要 Bob 删 Alice 上一次删除的数，就能保证剩下的两个数相等。

得到这个结论后，我们的问题变成了有没有一种删数方案使得剩下的两个数相等。我们发现，只要有一种数字的出现个数大于等于 2 那么 Bob 最终就有可能赢。Alice 需要做的是在她的 n-1 次操作后使得没有任意一种数的出现个数大于等于 2。我们发现，Alice 如果想要赢的话她需要的操作数为 2 \times n - color（这里的 color 指的是序列中不同的数字的个数）。这个式子 2\times n - color 是数字重复出现的个数。我们希望这个值小于等于 n - 1。因此最后推出来的式子为 n + 1\le color。

代码

#include<bits/stdc++.h>
#define N 100000 + 39
using namespace std;
int n, t, sum;
bool vis[N];
int main()
{
    ios :: sync_with_stdio(0), cin.tie(0), cout.tie(0);
    cin >> t;
    while(t --)
    {
        cin >> n;
        sum = 0;
        for(int i = 1; i < 100000 + 39; i ++)
        {
            vis[i] = 0;
        }
        for(int i = 1; i <= 2 * n; i ++)
        {
            int x;
            cin >> x;
            sum += !vis[x];
            vis[x] = 1;
        }
        if(sum >= n + 1)
        {
            cout << "Win\n";
        }
        else
        {
            cout << "Lose\n";
        }
    }
    return 0;
}

AC 记录。