19:22:34 你说巴黎的雨天依旧，漫无目的的街头，少了我。——沈以诚《不打扰》
爱情公寓5要完了，是小时候啊，还有点舍不得。高一的第一个寒假也要完了。
不要问我为什么看了这么多剧，去问新型冠状病毒！！！希望病毒快快散去，身边的人都健健康康，早日见到自己想见的人。
那话不多说（好像是有点多），进入正题啦！！！
-
巴什博奕
1、问题模型：
只有一堆n个物品，两个人轮流从这堆物品中取物，规定每次至少取一个，最多取m个，最后取光者得胜。
2、解决思路：
当n=m+1时，由于一次最多只能取m个，所以无论先取者拿走多少个，后取者都能够一次拿走剩余的物品，后者取胜，所以当一方面对的局势是n%(m+1)=0时，其面临的是必败的局势。所以当n=（m+1)*r+s，（r为任意自然数，s≤m)时,如果先取者要拿走s个物品，如果后取者拿走x（≤m)个，那么先取者再拿走m+1-k个，结果剩下（m+1）（r-1）个，以后保持这样的取法，那么先取者肯定获胜。总之，要保持给对手留下（m+1）的倍数，就能最后获胜。
3、变形：
条件不变，改为最后取光的人输。
4、结论：
当（n-1）%（m+1）==0时后手胜利。
-
公平组合博弈
1、定义：
（1）两人参与。
（2）游戏局面的状态集合是有限。
（3）对于同一个局面，两个游戏者的可操作集合完全相同
（4）游戏者轮流进行游戏。
（5）当无法进行操作时游戏结束，此时不能进行操作的一方算输。
（6）无论游戏如何进行，总可以在有限步数之内结束。
2、模型：给定一个有向无环图和一个起始顶点上的一枚棋子，两名选手交替的将这枚棋子沿有向边进行移动，无法移动者判负。事实上，这个游戏可以认为是所有公平组合游戏（Impartial Combinatori Games）的抽象模型。其实，任何一个ICG都可以通过把每个局势看成一个顶点，对每个局势和它的子局势连一条有向边来抽象成这个“有向图游戏”。
3、解决思路：
现在，假定我们给出两个游戏G1 和 G2。如果我们只知道单个游戏的P-状态和N-状态我们能够正确地玩好游戏和G1 + G2吗？答案是否定的。不难看出两个P-状态的和总是P-状态，P-状态和N-状态的和总是N-状态。但是两个N-状态的和既可能是P-状态也可能是N-状态。因此，只知道单个游戏的P-状态和N-状态是不够的。
为了正确地玩好游戏和我们需要推广P-状态和N-状态，它就是Sprague-Grudy函数（或者简称为sg函数）
必胜点和必败点的概念：
4、Sprague-Grudy定理：
令N = {0, 1, 2, 3, ...} 为自然数的集合。Sprague-Grundy 函数给游戏中的每个状态分配了一个自然数。结点v的Grundy值等于没有在v的后继的Grundy值中出现的最小自然数.
形式上：给定一个有限子集 S ⊂ N,令mex S(最小排斥值)为没有出现在S中的最小自然数。定义mex(minimal excludant)运算，这是施加于一个集合的运算，表示最小的不属于这个集合的非负整数。例如mex{0,1,2,4}=3、mex{2,3,5}=0、mex{}=0。
对于一个给定的有向无环图，定义关于图的每个顶点的Sprague-Garundy函数sg如下：sg(x)=mex{ sg(y) | y是x的后继 }。
5、性质：
（1）所有的终结点所对应的顶点，其SG值为0，因为它的后继集合是空集——所有终结点是必败点（P点）。
（2）对于一个sg(x)=0的顶点x，它的所有后继y都满足sg(y)!=0——无论如何操作，从必败点（P点）都只能进入必胜点（N点）//对手走完又只能把N留给我们。
（3）对于一个sg(x)!=0的顶点，必定存在一个后继点y满足sg(y)=0——从任何必胜点（N点）操作，至少有一种方法可以进入必败点（P点）//就是那种我们要走的方法。
6、应用：
（1）可选步数为1-m的连续整数，直接取模即可，SG(x) = x % (m+1);
（2）可选步数为任意步，SG(x) = x;
（3）可选步数为一系列不连续的数，用mex(计算每个节点的值)
19:49:10 你就像萤火虫，小小的很普通，却能在黑暗夜里明亮飞翔。——GAI《萤火虫》
-
威佐福游戏
1、定义：
有两堆石子，不妨先认为一堆有 10，另一堆有 15 个，双方轮流取走一些石子，合法的取法有如下两种：
（1）在一堆石子中取走任意多颗；
（2）在两堆石子中取走相同多的任意颗；
约定取走最后一颗石子的人为赢家，求必胜策略。
2、解决思路：
两堆石头地位是一样的，我们用余下的石子数(a,b)来表示状态，并画在平面直角坐标系上。
和前面类似，(0,0)肯定是 P 态，又叫必败态。
(0,k),(k,0),(k,k)系列的节点肯定不是 P 态，而是必胜态，你面对这样的局面一定会胜，
只要按照规则取一次就可以了。
再看 y = x 上方未被划去的格点，(1,2)是 P 态。
k > 2 时，(1,k)不是 P 态，比如你要是面对(1,3)的局面，你是有可能赢的。
同理，(k,2)，(1 + k, 2 + k)也不是 P 态，划去这些点以及它们的对称点，然后再找出 y = x 上方剩余的点，
你会发现(3,5)是一个 P 态，如此下去，如果我们只找出 a ≤ b 的 P 态，则它们是(0,0)，(1,2)，(3,5)，(4,7)，(6,10)……它们有什么规律吗？
忽略(0,0)，很快会发现对于第 i 个 P 态的 a，a = i * (sqrt(5) + 1)/2 然后取整；而 b = a + i。居然和黄金分割点扯上了关系。
前几个必败点如下：(0,0)，(1,2)，(3,5)，(4,7)，(6,10)，(8,13)……可以发现，对于第k个必败点(m(k),n(k))来说，m(k)是前面没有出现过的最小自然数，n(k)=m(k)+k。
那么任给一个局势（a，b），怎样判断它是不是必败态呢？
3、结论：
我们有如下公式：ak =[k（1+√5）/2]，bk= ak + k （k=0，1，2，…,n 方括号表示取整函数)
#include <bits/stdc++.h> using namespace std; int main() { int a,b,k; double eqa = (1+sqrt(5.0))/2.0; while( scanf("%d%d",&a,&b)!=EOF ) { // 当a>b时，交换a,b的值，当然你也可以用一个中间变量来交换a,b值 if( a > b ) { a^=b; b^=a; a^=b; } k=b-a; if( int( k*eqa )==a ) printf("0 "); else printf("1 "); } return 0; }
如果有一堆石子，先手必胜态。
如果有两堆石子，并且两堆石子的数量相等，那么先手采取什么样的策略，后手采取一样的策略，先手必败态。
如果有三堆石子，那么先手可以在第一步取到只剩两堆相同数量的石子，先手必胜。
如果有四堆石子，由于三堆石子是必胜态，所以只要逼对方取完某一堆石子，而只有在四堆石子都为1时，才能迫使某一方取完一堆石子，
只有当四堆石子可以分成两两相等的两队时，先手必败。
总结：
当n为偶，且可以分成n/2对两两相等的石子时，先手必败，否则先手必胜。
#include<stdio.h> #include<iostream> #include<algorithm> using namespace std; int main () { int s[20],i,n; while(scanf("%d",&n)!=EOF) { if(n==0) break; for(i=1;i<=n;i++) scanf("%d",&s[i]); if(n%2) printf ("1 "); else { sort(s+1,s+n+1); for(i=1;i<=n;i=i+2) if(s[i]!=s[i+1]) break; if(i==n) printf ("0 "); else printf("1 "); } } return 0; }
转化为必败状态从 而使得先手胜利。若a1^a2^...^an!=0，一定存在某个合法的移动，将ai改变成ai'后满足a1^a2^...^ai'^...^an=0。若a1^a2^...^an=k，则一定存在某个ai，它的二进制 表示在k的最高位上是1（否则k的最高位那个1是怎么得到的）。这时ai^k<ai一定成立。
则可以将ai改变成ai'=ai^k，此时a1^a2^...^ai'^...^an=a1^a2^...^an^k=0。
#include<bits/stdc++.h> using namespace std; int main() { int a[102],m,i,sum,s,count; while(scanf("%d",&m)!=EOF&&m) { sum=count=0; for(i=0;i<m;i++) { scanf("%d",&a[i]); sum=sum^a[i]; } for(i=0;i<m;i++) { s=sum^a[i]; if(s<a[i]) count++; } printf("%d ",count); } return 0; }