1070 Bash游戏 V4

基准时间限制：1 秒空间限制：131072 KB 分值: 40 难度：4级算法题

有一堆石子共有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示例

Output示例

B

B

A

思路

斐波那契博弈，当石子数量为斐波那契数的时候，先取者处于必败态

证明：根据zeckendorf定理（齐肯多夫定理）：任何正整数都可以表示成若干个不连续的斐波那契数（不包括第一个斐波那契数）之和。

若n不是Fib数，则n可被分解为多个不连续Fib数，设其可分为a，b，c三堆（a>b>c）。

A在第一步先拿走堆c。

考虑谁能先拿完倒数第二堆：设倒数第二堆个数为Fib(n)，首先，因为Fib(n)>2*Fib(n-2)，B不可能一次拿完倒数第二堆。若B拿走的石子数大于等于Fib(n-2)，则剩余石子必然可被A一次拿完。若B拿走的石子数为x<Fib(n-2)，则有Fib(n)-x必然不是Fib数，将(Fib(n)-x)视作一个子游戏，由归纳假设知，A必在子游戏中获胜。因此无论如何，拿完倒数第二堆的都是A。如此递推，知A必胜。

证得若n不是Fib数，则A必胜。

在上方对于子游戏的考虑中，实际已蕴含了证明若n为Fib数，则A必败。

证明过程来自知乎https://zhuanlan.zhihu.com/p/21706111

AC代码

#include <stdio.h>

#include <string.h>

#include <iostream>

#include <algorithm>

#include <math.h>

#include <limits.h>

#include <map>

#include <stack>

#include <queue>

#include <vector>

#include <set>

#include <string>

#define ll long long

#define ull unsigned long long

#define ms(a) memset(a,0,sizeof(a))

#define pi acos(-1.0)

#define INF 0x7f7f7f7f

#define lson o<<1

#define rson o<<1|1

const double E=exp(1);

const int maxn=1e2+10;

const int mod=1e9+7;

using namespace std;

int a[maxn];

int main(int argc, char const *argv[])

{

	ios::sync_with_stdio(false);

	a[0]=1;a[1]=1;

	map<int,int>mp;

	mp[1]=1;

	for(int i=2;i<=45;i++)

	{

		a[i]=a[i-1]+a[i-2];

		mp[a[i]]=1;

	}

	int t;

	int n;

	cin>>t;

	while(t--)

	{

		cin>>n;

		if(mp[n])

			cout<<"B"<<endl;

		else

			cout<<"A"<<endl;

	}

	return 0;

}

秒客网

51Nod 1070：Bash游戏 V4（斐波那契博弈）

1070 Bash游戏 V4

思路

AC代码

相关文章