杭电多校七 1008-Triangle Game（博弈）

题目链接：杭电多校7 - Virtual Judge

样例输入： 

3
2 2 3
2 3 4
5 3 4

样例输出：

Win
Lose
Win

题意：一开始给定一个非退化三角形的三边长a,b,c，两个人轮流操作，，每次操作可以选择一个边长将其减少不小于1个单位长度，要保证操作后必须还是非退化三角形，保证两个玩家都是采取的最优策略，问先手是必胜还是必败。

注意下面以^代表异或

分析：结论：先手胜当且仅当(a-1)^(b-1)^(c-1)!=0。

我们定义先手的必胜态为W态：(a-1)^(b-1)^(c-1)!=0

必败态为L态：(a-1)^(b-1)^(c-1)==0

我们先来看一下必败态是不是一个非退化三角形，假设a<=b<=c,c-1=(a-1)^(b-1)<=(a-1)+(b-1)等价于c<a+b，所以显然必败态是一个非退化三角形。

根据博弈论的知识我们知道，一个必胜态一定能够经过一次操作到达必败态，而一个必败态无论怎样操作都只能到达必胜态。

下面我们分别来证明这两个结论：
假设我们当前处于必败态L态，也就是有(a-1)^(b-1)^(c-1)==0

假设a<=b<=c

如果a等于1，那么代入必败态条件种可以知道有b==c，那么这显然是一个必败态，也就是说先手已经无法操作。

如果a不等于1，那么肯定有b<c，那么就有1<a<b<c，那么显然我们可以对a，b，c中的一个数进行操作，不妨假设对a进行操作，得到x，那么有a>x，由于(b-1)^(c-1)=a-1>x-1，那么显然有(b-1)^(c-1)^(x-1)!=0，也就是说我们由必败态走到了必胜态，而且无论如何都无法找到一个x使得(b-1)^(c-1)^(x-1)==0，也就是说我们由必败态只能走到必胜态。

下面我们证一下由必胜态存在一种合法方案走到必败态。

这里的证明方法类似于尼姆博弈：我们令x=(a-1)^(b-1)^(c-1)，那么如果我把(a-1)或者(b-1)或者(c-1)的其中一个对应地换成(a-1)^x,(b-1)^x,(c-1)^x，那么就会得到操作后的三个数异或值变为0.能这样进行操作的条件就是(a-1)>(a-1)^x,(b-1)>(b-1)^x,(c-1)>(c-1)^x三个不等式中至少有一个是成立的，由于x=(a-1)^(b-1)^(c-1)，那么x的二进制中为1的位置代表在(a-1)、(b-1)、(c-1)这三个数中的出现次数为奇数次，那么我们不妨让x中最高位为1的那一位上也为1的一个数来跟x进行异或，那么异或后值肯定会变小，那么也就是说三个不等式中肯定有成立的不等式，所以也就是说一定存在一个操作使得我们从必胜态走到必败态。

证毕！

下面是代码：

#include<cstdio>
#include<iostream>
#include<algorithm>
#include<cstring>
#include<map>
#include<queue>
#include<vector>
#include<cmath>
using namespace std;
int main()
{
	int T;
	cin>>T;
	while(T--)
	{
		int a,b,c;
		scanf("%d%d%d",&a,&b,&c);
		if(((a-1)^(b-1)^(c-1))!=0) printf("Win\n");
		else printf("Lose\n");
	}
	return 0;
}