忽然发现博弈论是个很好玩的东西哎
之前假期学长讲课的时候就发现这种必胜的战略可以用来坑人做题
这两天终于做了第一道博弈论的题，写篇博客纪念一下
灵感来源：洛谷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 代码
1 // 2 // main.cpp 3 // Luogu 4 // 5 // Created by gengyf on 2019/5/16. 6 // Copyright © 2019 yifan Geng. All rights reserved. 7 // 8 9 #include <cstdio> 10 int n; 11 int a[500005]; 12 int main(){ 13 scanf("%d",&n); 14 int check=0; 15 for(int i=1; i<=n; i++){ 16 scanf("%d",&a[i]); 17 check^=a[i]; 18 } 19 if(!check){ 20 printf("lose "); 21 return 0; 22 } 23 for(int i=1; i<=n; i++){ 24 if((check^a[i])<a[i]){ 25 printf("%d %d ",a[i]-(check^a[i]),i); 26 for(int j=1; j<=n; j++) 27 if(j!=i) 28 printf("%d ",a[j]); 29 else printf("%d ",check^a[i]); 30 break; 31 } 32 } 33 return 0; 34 }