题解 P1247 【取火柴游戏】
更好的阅读体验请点击
忽然发现博弈论是个很好玩的东西哎
之前假期学长讲课的时候就发现这种必胜的战略可以用来坑人做题
这两天终于做了第一道博弈论的题，写篇博客纪念一下
灵感来源：洛谷P1247
Pre-scene
众所周知，李明和Jenny都喜欢Danny，为了争夺Danny的所有权，他们决定玩一个游戏。规则是这样的：
有k堆扑克牌（不成套），两人轮流从某一堆中拿出x张牌，不能不拿，也不能跨堆拿牌，拿走最后一张(堆)牌的一方获胜。
命运当然是不公平的，李明来向你请教有没有必胜的方法，你聪明的，能告诉他么
0X10 知识
先来了解一下，什么是Nim博弈
通常的Nim游戏的定义是这样的：有若干堆石子，每堆石子的数量都是有限的，合法的移动是“选择一堆石子并拿走若干颗（不能不拿）”，如果轮到某个人时所有的石子堆都已经被拿空了，则判负（因为他此刻没有任何合法的移动）。 ——百度百科
了解Nim游戏之后，我们会发现这是一个经典的ICG游戏（不要问我什么是ICG因为我百度百科也不知道）
显然游戏有两种局面，先手必败和先手必胜，我们分别定义他们为P-position和N-position两种，其中P代表Previous，N代表Next，那么我们可以得出，从N-position转移而来的一定是P-position，反之也成立。
0X20 简单的证明
我们先来手玩一组小数据，一共有2堆石子，每一堆都有3个，你是先手的话，会怎么拿？由规则我们知道，玩家的目标是拿走最后一个石子，所以先手的你一定不会把某一堆全部拿走，因为如果这样，后手将会拿走另一堆，先手必败；但是如果你先拿1个，后手会跟着你从另一堆也拿一个，你拿2个，后手仍可以做和你一样的操作，先手必败。至此我们发现，（3，3）是一个P-position的局面。
推论：
1.当a1^a2^a3^……a^n=0时，为P-position，即先手必败。
2.当a1^a2^a3^……a^n!=0时，一定存在某个移动，使得局面变成一个P-position，即此局面为N-position。
0X30 实现
直接异或运算即可，代码过于简单就不放了。
0X40 题解
传送门
了解了上述知识后，这道题几乎就是一个裸的板子了，就是加了一个输出怎么取和取完的状态而已，这也很好实现。
0X41 怎么取
由于我们发现异或和不等于0，我们就要考虑怎么取使得其等于0了。
设k=a1^a2^a3^……a^n，因为k!=0，而显然k^k=0，所以要使a1^a2^a3^……a(n-1)^an^k=0，只需要把其中一个ai变成ai^k即可，又因必须要取，可得ai^k<ai
0X42 取完的状态
直接更改即可
0X43 代码
#include <cstdio>
int n;
int a[500005];
int main(){
scanf("%d",&n);
int check=0;
for(int i=1; i<=n; i++){
scanf("%d",&a[i]);
check^=a[i];
}
if(!check){
printf("lose\n");
return 0;
}
for(int i=1; i<=n; i++){
if((check^a[i])<a[i]){
printf("%d %d\n",a[i]-(check^a[i]),i);
for(int j=1; j<=n; j++)
if(j!=i)
printf("%d ",a[j]);
else printf("%d ",check^a[i]);
break;
}
}
return 0;
}