自动搬运

查看原文

来自洛谷，原作者为

	ycy1124 ENTJ-A | 有事私。| 清关了，私信基本也不会回关（除非满足条件），但可以支持小号回关 | 出去玩去了。不在线。微信可能上。

搬运于2025-08-24 21:17:59，当前版本为作者最后更新于2025-08-19 22:17:28，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

题意

现在有一个长度为 $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 记录。