题目传送门: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; }
Comments NOTHING