51nod 1072 博弈威佐夫游戏

怼烎@ 2022-08-21 13:56 189阅读 0赞

有2堆石子。A B两个人轮流拿，A先拿。每次可以从一堆中取任意个或从2堆中取相同数量的石子，但不可不取。拿到最后1颗石子的人获胜。假设A B都非常聪明，拿石子的过程中不会出现失误。给出2堆石子的数量，问最后谁能赢得比赛。

例如：2堆石子分别为3颗和5颗。那么不论A怎样拿，B都有对应的方法拿到最后1颗。

Input

第1行：一个数T，表示后面用作输入测试的数的数量。（1 <= T <= 10000)
    第2 - T + 1行：每行2个数分别是2堆石子的数量，中间用空格分隔。(1 <= N <= 2000000)

Output

共T行，如果A获胜输出A，如果B获胜输出B。

Input示例

3
    3 5
    3 4
    1 9

Output示例

B
    A
    A

经典的威佐夫游戏。

解法在下面：

首先我们根据条件来分析博弈中的奇异局势

第一个（0 ， 0），先手输，当游戏某一方面对（ 0 ， 0）时，他没有办法取了，那么肯定是先手在上一局取完了，那么输。

第二个 （ 1  ， 2  ），先手输，先手只有四种取法，

1）取 1 中的一个，那么后手取第二堆中两个。

2）取 2 中一个，那么后手在两堆中各取一个。

3）在 2 中取两个，那么后手在第一堆中取一个。

4）两堆中各取一个，那么后手在第二堆中取一个。

可以看出，不论先手怎么取，后说总是能赢。所以先手必输！

第三个 （ 3 ， 5 ），先手必输。首先先手必定不能把任意一堆取完，如果取完了很明显后手取完另一堆先手必输，那么

假如看取一堆的情况，假设先手先在第一堆中取。 取 1 个，后手第二堆中取4个，变成（1 ，2）了，上面分析了是先手的必输局。

取 2 个，后手第二堆中取3个，也变成（ 1 ， 2）局面了。

假设先手在第二堆中取，取 1 个，那么后手在两堆中各取 2 个，也变成 ( 1 , 2 )局面了。

取 2 个 ，那么后手可以两堆中都去三个， 变成 （ 0 ， 0）局面，上面分析其必输。

取  3  个，后手两堆各取 1 个 ，变成（ 1 ， 2）局面了。

取 4 个，后手在第一堆中取一个，变成（ 1 ， 2）局面了。

可见不论先手怎么取，其必输！

第四个（4  ， 7），先手必输。

自己推理可以发现不论第一次先手如何取，那么后手总是会变成前面分析过的先手的必输局面。

那么到底有什么规律没有呢，我们继续往下写。

第四个 （ 6 ，10  ）

第五个 （ 8 ，13）

第六个 （ 9 ， 15）

第七个 （ 11 ，18）

会发现他们的差值是递增的，为 0 ， 1 ， 2， 3， 4 ， 5 ， 6， 7.....n

而用数学方法分析发现局面中第一个值为前面局面中没有出现过的第一个值，比如第三个局面，前面出现了 0  1 2，那么第三个局面的第一个值为 3 ，比如第五个局面，前

面出现了 0  1  2 3 4 5 ,那么第五个局面第一个值为6。

再找规律的话我们会发现，第一个值 = 差值 \* 1.618

而1.618 = （sqrt（5）+ 1） /  2 。

大家都知道0.618是黄金分割率。而威佐夫博弈正好是1.618，这就是博弈的奇妙之处！

#include <iostream>
    #include <cstdio>
    #include <cstring>
    #include <cmath>
    #include <map>
    #include <algorithm>
    
    using namespace std;
    
    int const maxn = 2000005 ; 
    int a[maxn];
    map<int,int>m;
    
    //map的效率在这里好低
    void cal()
    {
    	for(int i = 0 ; ;i++)
    	{
    		int a = i*(sqrt(5.0)+1)/2;
    		//cout<<a<<endl;
    		m[a]=(a+i);
    		if((a+i)>100)break ; 
    	}
    }
    
    void cal1()
    {
    	memset(a,0,sizeof(a));
    	int num = 1 ; 
    	for(int i = 1 ; ; i++)
    	{
    		if((i+num)>=maxn)break;
    		if(a[i])continue;
    		a[i]=i+num;
    		a[i+num]=i;
    		num++;
    		//cout<<a[i]<<endl;
    	}
    }
    
    /*
    scanf("%I64d%I64d",&x,&y);
    if(x > y)
    {
    k = x;
    x = y;
    y = k;
    }
    k = y - x;
    if(x == (LL)((k)*(1 + sqrt(5.0))/2.0))
    {
    printf("B\n");
    }
    else
    printf("A\n");
    */
    
    int main()
    {
    	cal1();
    	int t;
    	int x,y;
    	//scanf("%d",&t);
    	cin>>t;
    	while(t--)
    	{
    		//scanf("%d%d",&a,&b);
    		cin>>x>>y;
    		if(a[x]==y) puts("B");
    		else puts("A");
    	}
    	return  0 ; 
    }

终极版：

#include <stdio.h>
    
    typedef __int64 ll;
    ll fib[100] = {1, 1};
    
    ll i2f(ll x, ll s[]) {
    	ll w = 1;
    	while(fib[w] <= x) ++w;
    	--w;
    	for(ll i = w; i > 0; --i) 
    	{
    		if(x >= fib[i]) 
    		{
    			s[i - 1] = 1;
    			x -= fib[i];
    		} 
    		else 
    		{
    			s[i - 1] = 0;
    		}
    	}
    	return w;
    }
    
    ll f2i(ll w, ll s[]) 
    {
    	ll ret = 0;
    	for(ll i = 0; i < w; ++i) if(s[i]) ret += fib[i + 1];
    	return ret;
    }
    
    ll solve(ll x) 
    {
    	ll w, s[100];
    	w = i2f(x, s + 1);
    	s[0] = 0;
    	ll n = 1;
    	while(!s[n]) ++n;
    	if(n & 1) 
    	{
    		return f2i(w + 1, s);
    	} 
    	else 
    	{
    		return f2i(w - 1, s + 2);
    	}
    }
    
    void print(ll w, ll s[]) 
    {
    	for(ll i = w - 1; i >=0; --i) printf("%I64d",s[i]);
    }
    
    int main() 
    {
    	for(int i = 2; i < 100; ++i) 
    	{
    		fib[i] = fib[i - 1] + fib[i - 2];
    	}
    	ll a, b;
    	int t ; 
    	scanf("%d",&t);
    	while(t--) 
    	{
    		scanf("%I64d %I64d", &a, &b);
    		if(solve(a) == b) puts("B");
    		else puts("A");
    	}
    	return 0;
    }