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示例

Output示例

A
B
A

思路：

利用sg函数打表找规律，发现能被3整除的数均为必败：

打表：

#include <iostream>
#include <cstring>
#include <stdio.h>
using namespace std;

int f[7] = {1,16,32,64};
int sg[100];
bool flag[100];

int mex(int x)
{
	memset(flag,false,sizeof(flag));
	for (int i = 0; i < 7; i++)
	{
		if (f[i] > x)
		{
			break;
		}

		flag[sg[x - f[i]]] = true;
	}

	for (int i = 0;; i++)
	{
		if (!flag[i])
		{
			return i;
		}
	}

	return 0;
}

int main()
{
	sg[0] = 0;
	for (int i = 1; i < 100; i++)
	{
		sg[i] = mex(i);
	}

	for (int i = 0; i < 100; i++)
	{
		cout << i << " = " << sg[i] << endl;
	}
	return 0;
}

程序：

#include <iostream>
#include <cstring>
#include <stdio.h>
using namespace std;

const int N = 1005;
char input[N];
int T;

int main()
{
	cin >> T;
	for (int i = 0; i < T; i++)
	{
		cin >> input;
		int sum = 0;
		int len = strlen(input);
	
		for (int j = 0; j < len; j++)
		{
			sum += input[j] - '0';
		}

		if (sum % 3 == 0)
		{
			cout << "B" << endl;
		}
		else
		{
			cout << "A" << endl;
		}
	}

	return 0;
}

原文链接：https://www.f2er.com/bash/389167.html

猜你在找的Bash相关文章