[杭电多校7 | HDUOJ7216]Triangle Game（Nim博弈）

题目传送门：Problem - 7216 (hdu.edu.cn)

题意 / Problem

两个人玩游戏，给定3个数字，分别表示一个三角形的三条边，双方轮流进行一次操作，将三条边的其中一条减去一个正整数的长度，且使得新的三个数依然可以组成三角形。当无法操作时就输了。

思路 / Thought

先将结论，当(a - 1) ^ (b - 1) ^ (c - 1)不为0时必胜，否则必败。

典型的Nim博弈，可以分为两个状态，我将其设为W态和L态。

• W态：\( (a-1)\oplus (b-1)\oplus (c-1) \ne 0 \)
• L态：\( (a-1)\oplus (b-1)\oplus (c-1) = 0 \)

现在来证明：

不妨设\( a <= b <= c \)。非退化三角形的定义为\( a + b > c \)，即\( (a-1) + (b-1) \ge (c-1) \)。（上面的状态公式是从这里分析出来的，利用了异或的性质\(a + b = 2 * (a \& b) + a \oplus b \ge a \oplus b\)）

当选手处于L态时，由于\( (a-1)\oplus (b-1) \oplus (c-1) = 0 \)，所以\( (a-1) \oplus (b - 1) = (c - 1) \Rightarrow (a-1)+(b-1) \ge (a-1)\oplus(b-1) = (c-1) \)，所以L态一定为非退化三角形。

此时又分为两种情况：

• \( a = 1\)时，\( b = c \)，此时为必败态，无法操作。
• \( a > 1\)时，此时一定存在一种方案使得某个长度减小后使得状态变为W态。

当选手处于W态时，不妨设\( (a-1)\oplus (b-1)\oplus(c-1) = r\)，那么在\((a-1), (b-1), (c-1)\)这三个数当中必然存在一个数字的二进制最高位与r的二进制最高位相同，也就是说这三个数中存在一个数 \(k\) 异或\(r\)后变小，即\(k \oplus r < k\)，因为二进制位的最高位从1异或1变为0了，后面的位数不管多大也比之前的小咯。

所以找出这个\(k\)并将其异或\(r\)，等价于减少的操作，此时因为异或了一个\(r\)，导致状态从W到了L，也就是\((a-1)\oplus(b-1)\oplus(c-1)\oplus r = 0\)。

所以状态L可以变为必败态或状态W，状态W可以变为状态L，也就是说如果一开始是状态W就直接赢，一开始是状态L最后只能输。

代码 / Code

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

void solve()
{
	int a, b, c;cin >> a >> b >> c;
	cout << (((a - 1) ^ (b - 1) ^ (c - 1)) ? "Win" : "Lose") << '\n';
}

signed main()
{
	ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
	
	int _;cin >> _;
	while(_ --)solve();
	return 0;
}