[杭电多校7 | HDUOJ7216]Triangle Game(Nim博弈)

发布于 2022-08-09  404 次阅读


题目传送门: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;
}
19岁,性别未知,ACM-XCPC退役选手,CCPC全国邀请赛金牌,ICPC亚洲区域赛银牌,武汉某院校计算机科学与技术专业本科在读。
最后更新于 2022-08-24