Alice有很多2*1的长方形，Bob有很多1*2的长方形，现在有如下15种棋盘，两人轮流用手中长方形去覆盖，第一个不能走的人输，问谁赢。
转自：http://www.cnblogs.com/kuangbin/archive/2012/08/23/2652902.html
这个题目应该是一个博弈类的题目，既然是博弈，那么每一步就要为自己争取最大的利益或者为对方带来最大的损失，那么先放哪一个就要综合对自己的利益与对对方的损失来考虑。
最后谁获得胜利只取决于Alice能走的步数是否比Bob多，同时这一因素又取决于两点：1.在双方都不能为对方带来损失时，谁是先手；2.双方还有多少个稳定的走位。
所谓稳定的走位，就是不论对方如何走，都不会占去的但自己却随时可以走的位置。
从上面分析的角度出发，我们可以把图分成下面5组：
1.（1）（2）是一组，分别是Alice和Bob的稳定走位，所以可以放到最后去考虑。
2.（15）单独为一组，综合来讲，（15）一旦放一个瓷砖，那么不仅使自己走出了一步，还能为自己留一个稳定走位，同时又能使对手失去两个位置，所以在（15）放一个瓷砖是效益最高的走法，因而双方最先都会争（15）。
3.（3）（4）（5）（6）是一组，至于为什么这四个是一组，我们不妨从Alice的角度分析下一。如果Alice走（5）或（6），那么Alice同时可以获得一稳定走位，并让Bob失去一个位置，如果Alice走（3）（4），那么Alice可以让Bob失去两个位置，所以这两种走法对Alice的收益是相同的。反过来，对Bob而言也是一样的。既然两种走法相同，那么便于我们的统计，不妨先让Alice走（5）（6），Bob走（3）（4），直到一方走完自己的主场，然后再去瓜分剩下的（3）（4）或者（5）（6）。
4.（7）（8）（9）（10）是一组，因为都是有一方可以牵制另一方，但另一方不能牵制这一方，具体的分析见下。
5.（11）（12）（13）（14）是一组，为什么这样分就不说了，主要说一下双方再走完第3组之后，究竟应该先走第4组还是先走第5组。
首先，从Alice的角度来讲，如果走（7）（8），都可以使Bob失去一个位置，走（11）（12）（13）（14）也是如此，但两种走法对Alice的收益来讲是不同的，如果Alice走（11）~（14）其中的任意一个，而Bob无论走（7）或（8）都会留一个稳定走位给Alice，而如果Alice走（7）（8）而Bob走（11）~（14）就没有这种效果了。因而Alice一定会先走（11）~（14），再走（7）（8）。同样的道理，Bob一定会先走（11）~（14），再走（9）（10）。
至于（7）（8）（9）（10）的瓜分，从Alice角度来讲，走（7）（8）不仅会使自己走出了这一步，同时会使Bob失去一个位置，而Alice走（9）（10）却只能使自己走出一步罢了，并不能给Bob带来什么损失，所以Alice一定优先走（7）（8），而对于Bob来讲，他一定会先走（9）（10），最后如果（7）（8）或者（9）（10）有剩余，双方再继续瓜分。
最后再把（1）（2）的统计加进去并看最后该谁走了即可。
综上所述，在统计的过程中，我们要记录3个量，Alice与Bob剩余的稳定走位和走当前组的图时，该谁先走，如果图是偶数谁先谁后无所谓，但如果图是奇数，先后手的收益就会有所差别。同时，对于走同一组图，如果双方的剩余的稳定走位有相同的部分，我们可以略去这些不去统计，因为最后我们只考虑两人可走的位置数的差，所以相同的部分会抵消掉，因而就不重要了。
#include <iostream>
#include <cstdio>
using namespace std;
const int maxn = 20;
int num[maxn];
int alice,bob,now;
void read()
{
alice = bob = now = 0;
for(int i=1;i<=15;i++)
{
scanf("%d",&num[i]);
}
return;
}
void solve()
{
if(num[15] & 1)
{
alice++;
now ^= 1;
}
int tmpa = num[5] + num[6];
int tmpb = num[3] + num[4];
if(tmpa < tmpb)
{
tmpb -= tmpa;
if(tmpb & 1)
{
if(now == 0)
{
bob += tmpb / 2;
}
else
{
bob += (tmpb + 1) / 2;
}
now ^= 1;
}
else
{
bob += tmpb / 2;
}
}
else if(tmpa > tmpb)
{
tmpa -= tmpb;
if(tmpa & 1)
{
if(now == 0)
{
alice += (tmpa + 1) / 2;
}
else
{
alice += tmpa / 2;
}
now ^= 1;
}
else
{
alice += tmpa / 2;
}
}
int tmp = num[11] + num[12] + num[13] + num[14];
if(tmp & 1) now ^= 1;
tmpa = num[7] + num[8];
tmpb = num[9] + num[10];
if(tmpa < tmpb)
{
tmpb -= tmpa;
if(tmpb & 1)
{
if(now == 0)
{
bob += (tmpb + 1) / 2;
}
else
{
bob += tmpb / 2;
}
now ^= 1;
}
else
{
bob += tmpb / 2;
}
}
else if(tmpa > tmpb)
{
tmpa -= tmpb;
if(tmpa & 1)
{
if(now == 0)
{
alice += tmpa / 2;
}
else
{
alice += (tmpa + 1) / 2;
}
now ^= 1;
}
else
{
alice += tmpa / 2;
}
}
alice += num[1] * 2;
bob += num[2] * 2;
if(now == 0)
{
if(bob >= alice) puts("Bob");
else puts("Alice");
}
else
{
if(alice >= bob) puts("Alice");
else puts("Bob");
}
return;
}
int main()
{
int cas;
scanf("%d",&cas);
for(int i=1;i<=cas;i++)
{
printf("Case #%d: ",i);
read();
solve();
}
return 0;
}