博弈论学习

巴什博奕：

结论：若n%(m+1)!=0则先手必败，否则先手必胜。（证明）

简单证明：若有一方面临着m+1的局面，那么那一方必败，所以对方都想让互相陷入m+1的局面。

若n%(m+1)！=0，那么先手就可以通过取走余数使后手最终面临m+1的局面。

Nim游戏：

有两个顶尖聪明的人在玩游戏，游戏规则是这样的：

证明：（来源）

反正最终情况就是每堆都为0，先手必输，所以我们考虑怎么把情况转换到这里。
如果异或和的最高位为i，则有一堆石子第i为为1（不然怎么会有i位）
设A1就为那堆石子，其他堆石子异或和设为x，总异或和设为k，则 A1 xor x=k，把A1变成A1 xor k，那么后手面对的则是（A1 xor k）xor x=0，

举个例子:11001 xor 11100=101，则有（11001 xor 101）xor 11100=0
如果现在的异或和已经为0了（不为最终情况），那么怎么转换异或和都不能为0
好，我们根据3 4点得出：如果先手异或和不为0，可以一步让后手的情况为异或和为0；如果先手异或和为0，那么后手异或和就不为0
如果现在先手面对的情况异或和不为0，则一直让后手异或和为0，最后面对最终情况，后手输，则先手赢；如果先手面对的情况异或和为0，后手则赢

简单来说，就是想尽办法让对方面临着全0局面。

模板：

#include<bits/stdc++.h>
using namespace std;
#define ri register int
int main()
{
    int T;
    scanf("%d",&T);
    while(T--){
        int n,ans=0,a;
        scanf("%d",&n);
        for(ri i=1;i<=n;++i) scanf("%d",&a),ans^=a;
        if(ans!=0) printf("Yes
");
        else printf("No
");
    }
    return 0;
}

View Code

威佐夫博弈：

有两堆石子，两个顶尖聪明的人在玩游戏，每次每个人可以从任意一堆石子中取任意多的石子或者从两堆石子中取同样多的石子，不能取得人输，分析谁会获得胜利。

（证明好像很复杂的样子，直接记结论啦）（找规律理解证明）

先手必败，当且仅当：x==（y-x）*（sqrt（5）+1）/2

模板：

#include<bits/stdc++.h>
using namespace std;
int main() 
{
    long long a,b;
    scanf("%lld%lld",&a,&b);
    if(a>b) swap(a,b);
    long long x= (b-a)*(sqrt(5.0)+1.0)/2.0;//记得打.0 注意精度问题 要把整个式子写在外面 再比较 否则会错 
    if(a==x) printf("0
");
    else printf("1
");
}

View Code

斐波那契博弈：

有一堆石子，两个顶尖聪明的人玩游戏，先取者可以取走任意多个，但不能全取完，以后每人取的石子数不能超过上个人的两倍。

结论：先手必败，当且仅当石子数为斐波那契数。

（证明）

其它博弈：

P1290 欧几里德的游戏

分析：

数变换的方式类似于辗转相除法。

以辗转相除来划分游戏的局面，称这一过程为一局：

a,b

a-b,b

……

a%b,b

首先，最后的赢家一定会面临最后一局的初状态（即a%b,b的形式），所以对方都希望自己掌握初状态。

假设玩家为A，B

当a/b>1时，A此时可以将a，b变成a%b+b，b，那么B就被强制地要将其变成a%b，b，这个状态被留给了A，所以A必胜。

由上述可知，谁目前掌握了a/b>1，谁就会赢。

当a/b==1时，无论是谁走，都只有一种走法：变成b,a%b

当走完一段连续的a/b==1后，走到了a%b==0或a/b>1可以直接判胜负的阶段，就可以直接得出谁是赢家了。

所以我们只需要记录连续的一段a/b==1的个数即可。

#include<bits/stdc++.h>
using namespace std;
#define ll long long
int main()
{
    int T;
    scanf("%d",&T);
    while(T--){
        ll a,b;
        scanf("%lld%lld",&a,&b);
        if(a<b) swap(a,b);
        int win=0;
        while(a/b==1 && a%b){
            ll tmp=a%b;
            a=b; b=tmp;
            win^=1;
        }
        if(!win) printf("Stan wins
");
        else printf("Ollie wins
");
    }
}
/*
10
25 7
24 15
7 4
3 4
1 3
*/

View Code