博弈论 威佐夫博奕呜

R - 取石子游戏

有两堆石子，数量任意，可以不同。游戏开始由两个人轮流取石子。游戏规定，每次有两种不同的取法，一是可以在任意的一堆中取走任意多的石子；二是可以在两堆中同时取走相同数量的石子。最后把石子全部取完者为胜者。现在给出初始的两堆石子的数目，如果轮到你先取，假设双方都采取最好的策略，问最后你是胜者还是败者。
Input
输入包含若干行，表示若干种石子的初始情况，其中每一行包含两个非负整数a和b，表示两堆石子的数目，a和b都不大于1,000,000,000。
Output
输出对应也有若干行，每行包含一个数字1或0，如果最后你是胜者，则为1，反之，则为0。
Sample Input
2 1
8 4
4 7
Sample Output
0
1
0
经典的威佐夫博奕详细介绍左转参考大佬的网址
定义奇异局势 （a[k],b[k]）面对奇异局势就会输 a[k]<b[k] k!=0
（0 0），（1 2），（3 5）···也就是新的奇异局势 是前面没出现过的最小整数且b[k]=a[k]+k,而且 每个非零整数在奇异局势中一定存在且只有一次出现机会 任何非零整数 都包含在一个有且 仅有一个 奇异局势 中 所以有以下性质
1 任何操左都会使奇异局势变为非奇异局势 我感觉这个其实是巴什博弈的扩展？ 证明 由于每次只能拿一堆 或 两堆拿同样数量的石子 每一个奇异局势都是由顺序产生的 a[k]>a[k-1] b[k]=a[k]+k>a[k-1]+k-1=b[k-1],b[k]-b[k-1]与a[k]-a[k-1]作比较 前者比后者多一以此类推 同时拿同样个数的石子一定不能得到奇异局势 由于每个非零整数 都包含在一个有且 仅有一个 奇异局势 中 不可能从一堆里拿出任意的石子 变为另一个奇异局势

2.采用最好的推理判断 可以将非奇异局势变为奇异局势
面对局势 （a，b））（前提a<=b） a=b 直接全部拿走 当a=a[k] 1. b>b[k] 只需要b-（b-b[k]） 2.b<b[k] 由于a=a[k]<b a[k]+b-a=b b-(b-a)=a[k] a[k]-(b-a)=a[b-a] 所以从两堆中同时拿走b-a个石子即可 当b=b[k] 1.a>a[k] 只需要a-（a-a[k]） 2.a<a[k] 由于 任何非零整数 都包含在一个有且 仅有一个 奇异局势 中会存在两种情况 a=a[j] 只需要b-（b-b[j]）即可 a=b[j] 只需要 b-(b-a[j])
3.奇异局势b[k]-a[k]的值表示第几个奇异局势 。
这里我简要说一下最难的部分是找n和m是不是奇异局势

解题关键 判断（n m）是不是奇异局势 可以假设 abs（m-n）是第（m-n）个奇异局势那么min（a，b）=a[abs(m-n)] 判断一下即可

#include<cstdio>
#include<cstring>
#include<cmath>
#include<cstdlib>
#include<iostream>
#include<algorithm>
#include<sstream>
#include<fstream>
#include<vector>
#include<map>
#include<stack>
#include<list>
#include<set>
#include<queue>
#include<string>
#include<string.h>
#define ll long long
using namespace std;
int main()
{
    int n,m;

    while(scanf("%d %d",&n,&m)!=EOF)
    {  
        int k=abs(n-m);
        n=n<m?n:m;
        int ok= floor(k*(1+sqrt(5.0))/2);
        printf("%d\n",ok!=n);


    }
    return 0;
}

本文地址：https://blog.csdn.net/qq_45827278/article/details/107881196