51nod1070 博弈

「爱情、让人受尽委屈。」 2022-08-21 13:39 160阅读 0赞

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

分析：

接着打表，反正我做过的所有的博弈就没几个用过正规的sg函数的，一般都是打表找规律来写的。

这个题目也是一样的，打表发现，2，3，5，8，13....等B都可以赢，斐波那契数列呀这是。

#include <iostream>
    #include <algorithm>
    #include <string>
    #include <map>
    #include <cstring>
    #include <cstdio>
    using namespace std; 
    
    map<long long ,int>m;
    
    void cal()
    {
    	long long a = 1 ;
    	long long b = 2 ;
    	long long c ;
    	for(int i = 1 ; ;i++)
    	{
    		m[a] = i ; 
    		c = a+b ; 
    		a = b ; 
    		b = c ; 
    		if(a>=1000000000)break ; 
    		//cout<<m[a]<<endl;
    	}
    }
    
    
    int main()
    {
    	cal() ;
    	int t;
    	long long n;
    	cin>>t ; 
    	while(t--)
    	{
    		cin>>n ; 
    		if(m[n])puts("B");
    		else puts("A");
    	}
    	return 0 ;
    }

发表评论取消回复

表情：

评论列表（有 0 条评论，160人围观）

还没有评论，来说两句吧...

相关阅读

相关 51nod 1072 博弈威佐夫游戏

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

怼烎@/ 2022年08月21日 13:56/ 0 赞/ 171 阅读

相关 51nod1070 博弈

有一堆石子共有N个。A B两个人轮流拿，A先拿。每次拿的数量最少1个，最多不超过对手上一次拿的数量的2倍（A第1次拿时要求不能全拿走）。拿到最后1颗石子的人获胜。假设A B都非

「爱情、让人受尽委屈。」/ 2022年08月21日 13:39/ 0 赞/ 161 阅读

相关 51nod1068 博弈

有一堆石子共有N个。A B两个人轮流拿，A先拿。每次拿的数量只能是2的正整数次幂，比如(1,2,4,8,16....)，拿到最后1颗石子的人获胜。假设A B都非常聪明，拿石子的

刺骨的言语ヽ痛彻心扉/ 2022年08月21日 12:59/ 0 赞/ 167 阅读

相关 51nod 1067 博弈

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

比眉伴天荒/ 2022年08月21日 12:59/ 0 赞/ 190 阅读

相关 51nod1417 博弈

多年后，每当Noder看到吉普赛人，就会想起那个遥远的下午。 Noder躺在草地上漫无目的的张望，二楼的咖啡馆在日光下闪着亮，像是要进化成一颗巨大的咖啡豆。天气稍有

桃扇骨/ 2022年08月21日 12:48/ 0 赞/ 129 阅读

相关 51nod 1043

题意：求在2\n位的数字中，前n位的和等于后n位的和的个数，比喻n=1的时候，11,22,33...99等数字都是的，还有1102，2121等都是满足要求的数字。n<=10

灰太狼/ 2022年08月21日 03:14/ 0 赞/ 197 阅读

相关 51nod-加农炮

一个长度为M的正整数数组A，表示从左向右的地形高度。测试一种加农炮，炮弹平行于地面从左向右飞行，高度为H，如果某处地形的高度大于等于炮弹飞行的高度H（A\[i\] >= H），

男娘i/ 2022年06月17日 14:08/ 0 赞/ 203 阅读

相关 51nod 1185 威佐夫游戏 V2 （博弈+大数乘法模拟）

题目链接： [点击打开题目链接][Link 1] 题解：如果数据在106左右，可以直接用(b−a)∗5√\+12。但是这道题数据是1018，那么直接乘的话，肯定会有

ゝ一纸荒年。/ 2022年06月15日 02:13/ 0 赞/ 154 阅读

相关 51nod-1770

为该问题添加一个话题隐藏话题 [1770 数数字][1770] 基准时间限制：1 秒空间限制：262144 KB 分值: 20 [难度：3级算法题][3] ![s

小灰灰/ 2022年05月28日 12:51/ 0 赞/ 179 阅读

相关 51nod--1284

[1284 2 3 5 7的倍数][1284_2_3_5_7] ![ok.png][] 基准时间限制：1 秒空间限制：131072 KB 分值: 5 [难度：1级算法题][

分手后的思念是犯贱/ 2022年05月27日 11:22/ 0 赞/ 184 阅读