巴什博弈变形题通解

代码通过洛谷p4018所编写

通解只适用于数据比较小的该类型题目

该代码只能通过洛谷p4018 30% 其他的会超时

#include<bits/stdc++.h>
using namespace std;
char ans[100005];
bool flag[30];
vector<int>v;
void f()
{
	memset(flag,1,sizeof(flag));
	for(int i=2;i<=30;i++)
	{
		if(flag[i])
		{
			for(int j=i+i;j<=30;j+=i)
			{
				flag[j]=0;
			}
		}
	}
	for(int i=1;i<=30;i++)//将质数与1装入容器
	{
		if(flag[i])
		{
			v.push_back(i);
		}
	}
}
int main()
{
	int n;
	scanf("%d",&n);
	f();
	ans[0]='N';//自己先手已经被拿完了
	ans[1]='Y';//只有一个石头的时候必赢
	for(int i=2;i<=30;i++)
	{
		for(int j=0;j<v.size();j++)
		{
			if(ans[i-v[j]]=='N')//我取完后就是他取，他取必输则我必赢
			{
				ans[i]='Y';
				break;
			}
			else if(i<v[j])
			{
				ans[i]='N';
				break;
			}
		}
	}
	while(n--)
	{
		int p;
		scanf("%d",&p);
		if(ans[p]=='Y')
		{
			printf("October wins!\n");
		}
		else if(ans[p]=='N')
		{
			printf("Roy wins!\n");
		}
	}
	return 0;
}

P4018 Roy&October之取石子

P4018 Roy&October之取石子

P4018 Roy&October之取石子

P4018 Roy&October之取石子

P4018 Roy&October之取石子

P4018 Roy&October之取石子

P4018 Roy&October之取石子

P4018 Roy&October之取石子

P4018 Roy&October之取石子

P4018 Roy&October之取石子

P4018 Roy&October之取石子

P4018 Roy&October之取石子

P4018 Roy&October之取石