51nod Bash游戏(V1,V2,V3,V4(斐波那契博弈))

Bash游戏V1

有一堆石子共同拥有N个。

A B两个人轮流拿。A先拿。每次最少拿1颗。最多拿K颗。拿到最后1颗石子的人获胜。如果A B都很聪明，拿石子的过程中不会出现失误。给出N和K，问最后谁能赢得比赛。

比如N = 3。K = 2。不管A怎样拿，B都能够拿到最后1颗石子。

Input

第1行：一个数T。表示后面用作输入測试的数的数量。（1 <= T <= 10000)
第2 - T + 1行：每行2个数N，K。中间用空格分隔。（1 <= N,K <= 10^9)

Output

共T行。假设A获胜输出A，假设B获胜输出B。

Input演示样例

4
3 2
4 2
7 3
8 3

Output演示样例

B
A
A
B

解题思路：

    假设是(k+1)的整数倍。先手取不论什么一个1~k内的数x。后手都能够取(k+1-x)个石子，于是k+1的整数倍是先手的必败态，同理，不是k+1的整数倍时，先手能够取n%(k+1)个石子。从而使后手必败。

代码：

#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;

int main()
{
    int n,k,t;
    scanf("%d",&t);
    while(t--)
    {
        scanf("%d%d",&n,&k);
        if(n%(k+1))
        printf("A\n");
        else
        printf("B\n");
    }
    return 0;
}

Bash游戏V2

有一堆石子共同拥有N个。A B两个人轮流拿，A先拿。每次仅仅能拿1，3，4颗。拿到最后1颗石子的人获胜。如果A B都很聪明，拿石子的过程中不会出现失误。给出N，问最后谁能赢得比赛。

比如N = 2。

A仅仅能拿1颗，所以B能够拿到最后1颗石子。

Input

第1行：一个数T，表示后面用作输入測试的数的数量。（1 <= T <= 10000)
第2 - T + 1行：每行1个数N。(1 <= N <= 10^9)

Output

共T行，假设A获胜输出A。假设B获胜输出B。

Input演示样例

3
2
3
4

Output演示样例

B
A
A

解题思路：

    这题假设直接想不出来能够用sg函数打表发现规律来做。

 sg函数和sg定理:

     对于随意状态x。定义SG(x)=mex(S),当中S是x的后继状态的SG函数的集合。mex(s)表示不在S内的最小负整数。比方，x有6个后继状态。SG函数数值分别为0,1,1,2,4,7,则SG(x)=3，由于3是第一个没有出如今后继状态SG函数值集合中的非负整数。

这题的sg函数代码：

const int maxn=45;
bool vis[maxn];
int sg[maxn];
int a[5]={1,3,4};
void sgs()
{
    for(int i=0;i<maxn;i++)
    {
        memset(vis,false,sizeof(vis));
        for(int j=0;j<3;j++)
        {
            if(i>=a[j])
            vis[sg[i-a[j]]]=true;
        }
        for(int j=0;;j++)
        {
            if(!vis[j])
            {
                sg[i]=j;
                break;
            }
        }
        printf("%d %d\n",i,sg[i]);
    }
}

通过打表发现，7的整数倍和n%7==2的是必败态。

证明：

    1,对于2。肯定必败。

    2,对于1,3,4,先手必胜。

    3,对于5,6,先手能够取3,4,让后手进入必败态2。

    2,对于7。不管先手取什么。后手都能够让其进入必败态。先手取1,后手取4,进入必败态2;先        手取3,后手取4；先手取4,后手取3就可以。于是仅仅要是7的倍数或%7余2的。都是必败态，其它      都为必胜态。

代码：

#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <vector>
using namespace std;

int main()
{
    int t;
    scanf("%d",&t);
    while(t--)
    {
        int n;
        scanf("%d",&n);
        if(n%7==0||n%7==2)
        printf("B\n");
        else
        printf("A\n");
    }
    return 0;
}

Bash游戏V3

有一堆石子共同拥有N个。A B两个人轮流拿，A先拿。每次拿的数量仅仅能是2的正整数次幂。比方(1,2,4,8,16....)。拿到最后1颗石子的人获胜。

如果A B都很聪明，拿石子的过程中不会出现失误。给出N。问最后谁能赢得比赛。

比如N = 3。

A仅仅能拿1颗或2颗，所以B能够拿到最后1颗石子。（输入的N可能为大数）

Input

第1行：一个数T，表示后面用作输入測试的数的数量。

（1 <= T <= 1000)
第2 - T + 1行：每行1个数N。

(1 <= N <= 10^1000)

Output

共T行。假设A获胜输出A，假设B获胜输出B。

Input演示样例

3
2
3
4

Output演示样例

A
B
A

解题思路：

   sg函数：

const int maxn=1000+100;
int sg[maxn];
bool vis[maxn];
int main()
{
    for(int i=0;i<50;i++)
    {
        memset(vis,false,sizeof(vis));
        for(int j=0;(1<<j)<=i;j++)
        {
            int s=i-(1<<j);
            vis[sg[s]]=true;
        }
        for(int j=0;;j++)
        {
            if(!vis[j])
            {
                sg[i]=j;
                break;
            }
        }
        printf("%d ",sg[i]);
    }
    return 0;
}

发现仅仅要是3的整数倍就能够。

证明：

   随意1个3的整数倍都能够转化为2*n个2的正整数幂的和。通过枚举能够发现：

   (2^0)%3=1; (2^1)%3=2;(2^2)%3=1;(2^3)%3=2;

   总是1和2，随意1个%3为1的加上%3为2的就能够组成%为3的数了。

代码：

#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <vector>
using namespace std;
char s[maxn];
int main()
{
    int t;
    scanf("%d",&t);
    while(t--)
    {
        scanf("%s",s);
        int n=strlen(s);
        int ans=0;
        for(int i=0;i<n;i++)
        {
            ans=ans+(s[i]-'0');
        }
        if(ans%3)
        printf("A\n");
        else
        printf("B\n");
    }
    return 0;
}

Bash游戏V4(斐波那契博弈)

有一堆石子共同拥有N个。A B两个人轮流拿，A先拿。每次拿的数量最少1个，最多不超过对手上一次拿的数量的2倍（A第1次拿时要求不能全拿走）。拿到最后1颗石子的人获胜。如果A B都很聪明，拿石子的过程中不会出现失误。给出N，问最后谁能赢得比赛。

比如N = 3。

A仅仅能拿1颗或2颗，所以B能够拿到最后1颗石子。

Input

第1行：一个数T，表示后面用作输入測试的数的数量。

（1 <= T <= 1000)
第2 - T + 1行：每行1个数N。(1 <= N <= 10^9)

Output

共T行，假设A获胜输出A，假设B获胜输出B。

Input演示样例

3
2
3
4

Output演示样例

B
B
A

解题思路：

引用http://blog.****.net/acm_cxlove/article/details/7835016

这个游戏叫做Fibonacci Nim，肯定和Fibonacci数列：f[n]：1,2,3,5,8,13,21,34,55,89,… 有密切的关系。假设试验一番之后，能够推測：先手胜当且仅当n不是Fibonacci数。

换句话说。必败态构成Fibonacci数列。

这里须要借助“Zeckendorf定理”（齐肯多夫定理）：不论什么正整数能够表示为若干个不连续的Fibonacci数之和。

先看看FIB数列的必败证明：

1、当i=2时。先手仅仅能取1颗，显然必败，结论成立。

2、如果当i<=k时。结论成立。

则当i=k+1时，f[i] = f[k]+f[k-1]。

则我们能够把这一堆石子看成两堆，简称k堆和k-1堆。

（一定能够看成两堆，由于假如先手第一次取的石子数大于或等于f[k-1]，则后手能够直接取完f[k]，由于f[k] < 2*f[k-1]）

对于k-1堆。由如果可知，不论先手如何取，后手总能取到最后一颗。以下我们分析一下后手最后取的石子数x的情况。

假设先手第一次取的石子数y>=f[k-1]/3。则这小堆所剩的石子数小于2y。即后手能够直接取完。此时x=f[k-1]-y，则x<=2/3*f[k-1]。

我们来比較一下2/3*f[k-1]与1/2*f[k]的大小。即4*f[k-1]与3*f[k]的大小，由数学归纳法不难得出，后者大。

所以我们得到，x<1/2*f[k]。

即后手取完k-1堆后。先手不能一下取完k堆，所以游戏规则没有改变，则由如果可知，对于k堆，后手仍能取到最后一颗，所以后手必胜。

即i=k+1时。结论依旧成立。

对于不是FIB数，首先进行分解。

分解的时候，要取尽量大的Fibonacci数。

比方分解85：85在55和89之间。于是能够写成85=55+30，然后继续分解30,30在21和34之间，所以能够写成30=21+9，

依此类推，最后分解成85=55+21+8+1。

则我们能够把n写成  n = f[a1]+f[a2]+……+f[ap]。

（a1>a2>……>ap）

我们令先手先取完f[ap]，即最小的这一堆。因为各个f之间不连续。则a(p-1) > ap  + 1，则有f[a(p-1)] > 2*f[ap]。即后手仅仅能取f[a(p-1)]这一堆，且不能一次取完。

此时后手相当于面临这个子游戏（仅仅有f[a(p-1)]这一堆石子。且后手先取）的必败态。即先手一定能够取到这一堆的最后一颗石子。

同理可知。对于以后的每一堆，先手都能够取到这一堆的最后一颗石子，从而获得游戏的胜利。

代码：

#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <vector>
using namespace std;
const int maxn=50;
long long f[50];
int main()
{
    f[1]=1,f[2]=2;
    for(int i=3;i<maxn;i++)
    f[i]=f[i-1]+f[i-2];
    int t;
    scanf("%d",&t);
    while(t--)
    {
        int n;
        scanf("%d",&n);
        int sign=1;
        for(int i=1;i<maxn;i++)
        {
            if(f[i]>n)
            break;
            if(f[i]==n)
            {
                sign=0;
                break;
            }
        }
        if(sign)
        printf("A\n");
        else
        printf("B\n");
    }
    return 0;
}