博弈论基础

思路也就出来了。

#include 
using namespace std;

long long a, b, T;
bool f = false;
int main(){
	cin >> T;
	while(T--){
	    f = false;
	    cin >> a >> b;
	    while(1){
		    if(a < b) swap(a, b);
		    if(a % b == 0) break;
		    if(a - b > b) break;
	    	f = 1 - f;
	    	a -= b; 
    	}
    	if(!f) cout << "Stan wins" << endl;
    	else cout <<"Ollie wins" << endl;
    }
	return 0;
} 

接下来就是大头了！！

----- N i m Nim Nim游戏

【P2197】nim游戏

甲，乙两个人玩 N i m Nim Nim取石子游戏。

n i m nim nim游戏的规则是这样的：地上有 n n n堆石子（每堆石子数量小于 10000 10000 10000），每人每次可从任意一堆石子里取出任意多枚石子扔掉，可以取完，不能不取。每次只能从一堆里取。最后没石子可取的人就输了。假如甲是先手，且告诉你这 n n n堆石子的数量，他想知道是否存在先手必胜的策略。

输入格式：

• 第一行一个整数 T < = 10 T<=10 T<=10,表示有 T T T组数据
• 接下来每两行是一组数据，第一行一个整数 n n n，表示有 n n n堆石子， n < = 10000 n<=10000 n<=10000;
• 第二行有 n n n个数，表示每一堆石子的数量

输出格式：

• 共 T T T行，如果对于这组数据存在先手必胜策略则输出 " Y e s " "Yes" "Yes",否则输出 " N o " "No" "No"，不包含引号，每个单词一行。

输入样例：

2 2 2

2 2 2

1   1 1 1 1 1

2 2 2

1   0 1 0 1 0

输出样例

N o No No

Y e s Yes Yes

这个题，答案就是！！！！

如果每堆石子异或起来不等于零，那么先手必胜，否则先手必败。

为什么？？

首先我们假设没有石头了，那这种情况就是必败态。

现在我们来举个栗子。每堆石头的个数我用二进制来表示：

10010   100   1 10010 100 1 10010 100 1

它们异或起来是 10111 10111 10111（大概吧）

我们发现，最高位1是（从右往左数）第五位。而且这些石头里必定有的数量的第五位是 1 1 1（这还是比较好理解的，因为相同为零，不同为一，既然是一，那就肯定说明肯定有的石头在一位上是 1 1 1.把这堆的数和异或之后的数异或起来得到a，然后将那一堆石头取出到只有 a a a^原本石头数量 的数量）

这个例子中也就是 10010 10010 10010 ^ 10111 = 00101 10111 = 00101 10111=00101，然后我们发现这个跟其他石头的数量异或起来居然是零！

那么无论下一个人取出多少，都不可能异或为零了，然后这个人再根据上面所推的结论将异或变成零。也就是，如果异或不为零的话先手必胜！

#include
using namespace std;
int t,n;
int main(){
    scanf("%d",&t);
    while(t--){
        scanf("%d",&n);
        int ans=0;
        for(int i=1; i<=n; ++i){
            int shu;
            scanf("%d",&shu);
            ans^=shu;
        }
        if(!ans) printf("Non");
        else printf("Yesn");
    }
}

这个结论，哪怕背都要背过！因为这跟我们后面要讲的息息相关……

可以说这个就是综上所述的内容了。

G r u n d y Grundy Grundy数是个什么东西？

G r u n d y Grundy Grundy就是从这一个点开始，除了走一步就能到的点以外的最小非负整数，也就是所谓的 m e x mex mex操作。

每个点取了 G r u n d y Grundy Grundy之后，就跟 n i m nim nim游戏一样了。何出此言？

• N i m Nim Nim游戏中有x颗石子的点可以转化为有 0 , 1 , . . . , x − 1 0,1,...,x-1 0,1,...,x−1颗石头的点
• 从 G r u n d y Grundy Grundy为x开始的点，可以转移到 G r u n d y Grundy Grundy为 0 , 1 , . . . , x − 1 0,1,...,x-1 0,1,...,x−1的状态

脑子累了？？来道题清醒一下！

硬币游戏 2 2 2

A l i c e Alice Alice和 B o b Bob Bob在玩这样一个游戏。给定k个数字 a 1 , a 2 , . . . , a k a_1,a_2,...,a_k a1​,a2​,...,ak​。一开始，有n堆硬币，每一堆有 x i x_i xi​枚硬币， A l i c e Alice Alice和 B o b Bob Bob轮流取硬币。每次所取硬币的数量一定要在 a 1 , a 2 , . . . , a k a_1,a_2,...,a_k a1​,a2​,...,ak​之中。Alice先取，取走最后一枚硬币的一方获胜。当双方都采取最优策略时，谁会获胜？题目假定 a 1 , a 2 , . . . , a k a_1,a_2,...,a_k a1​,a2​,...,ak​中一定有 1 1 1。

限制条件

• 1 < = n < = 1000000 1 <= n <= 1000000 1<=n<=1000000
• 1 < = k < = 100 1 <= k <= 100 1<=k<=100
• 1 < = a i , x i < = 10000 1 <= ai,xi <= 10000 1<=ai,xi<=10000

样例输入

n = 3 n = 3 n=3

k = 3 k = 3 k=3

a = { 1 , 3 , 4 } a = {1,3,4} a={1,3,4}

x = { 5 , 6 , 8 } x = {5,6,8} x={5,6,8}

样例输出

B o b Bob Bob

经过了前面讲的，这个，太简单了！求一下 G r u n d y Grundy Grundy然后 x o r xor xor起来就切掉了。

威佐夫博弈大概就是有两堆石子，你可以从第一堆里取任意个，也可以从第二个里取任意个，也可以从两堆里取出同样多的任意个石子。最后面对 ( 0 , 0 ) (0, 0) (0,0)局势的就算输。

我们先打表，发现先手面对这样的局势必输：

( 0 , 0 ) , ( 1 , 2 ) , ( 3 , 5 ) , ( 4 , 7 ) , ( 5 , 9 ) . . . . . . (0, 0), (1, 2), (3, 5), (4, 7), (5, 9)...... (0,0),(1,2),(3,5),(4,7),(5,9)......

有发现规律吗？我们把第一个点看作是『第零个点』。我们发现第一个数实际上就是之前没有出现过的最小自然数，第二个数则是第一个数加上这个点的序号。这也就是我把第一个点设为『第零个点』的原因。

我们将这样的点叫做奇异局势

关于奇异局势，有这么几个性质：

• **它非常少。**如果你的地图无限大的话，那么纵坐标等于1的那一列点就只有一个奇异局势。感性理解一下……
• **任何自然数都包含在一个且仅有一个奇异局势中。**有点类似于那个『充要条件』吧。我们设第 k k k个奇异局势为 ( a , a + k ) (a, a + k) (a,a+k)， 第 k − 1 k - 1 k−1个奇异局势为 ( a ′ , a ′ + k − 1 ) (a', a' + k - 1) (a′,a′+k−1)。每个局势中的 a , b a,b a,b肯定不同。而且 a a a一定大于 a ′ − 1 a'-1 a′−1，而且 a a a的条件是『没有出现过的最小自然数』，所以也不可能等于 a ′ + k a' + k a′+k。关键就看 b b b。其实也很简单， a a a一定大于 a ′ a' a′，所以 a + k > a ′ + k a + k > a'+ k a+k>a′+k，也就 a + k > a ′ + k − 1 a + k > a'+ k - 1 a+k>a′+k−1了。
• **任何操作都会把奇异局势变为非奇异局势。**即使是两个数同时减一个数，他们的差值也不会变。但是不同的奇异局势差值是不一样的。所以即使是同时减去相同的数，也会变成非奇异局势。
• **可以通过某些操作让非奇异局势变为奇异局势。**因为任何自然数都包含在一个且仅有一个奇异局势中，所以只需要让另一个数加或减一个数使之变成奇异局势就好了。比如说 ( 5 , 20 ) (5, 20) (5,20)很明显这不是奇异局势。但是我们把 20 20 20变成 9 9 9，它就变成奇异局势了。

那么，怎么判断是不是奇异局势呢？我们可以用 B e t t y Betty Betty定理：

设 n < m n < m n

( m − n ) ∗ ( ( 1 + 5 ) / 2 ) = = n (m - n) * ((1 + sqrt5) / 2) == n (m−n)∗((1+5 ​)/2)==n

那么这就是一个奇异局势。面对奇异局势先手必输，否则先手必赢。因为先手无论干什么都会让它变成非奇异局势，然后后手通过某些方式把它变成奇异局势这样无限循环……我日你不会断句吗

可以考虑一下这一道傻逼题，裸的威佐夫博弈。

代码吧，很好懂（话说我的码风变了很多）：

#include 
#include 
#include 
using namespace std;
#define endl "n"


int n, m, x, y, t;
    
int main() {
    cin >> x >> y >> t;
    while(t--) {
        cin >> n >> m;
        if(n > m) swap(n, m);
        int b = floor((m - n) * (1.0 + sqrt(5.0)) / 2.0);
        if(b == n) cout << "Farmer John" << endl;
        else cout << "Bessie" << endl;
    }
}