牛客竞赛1 A Alice and Bob

链接:https://ac.nowcoder.com/acm/contest/11166/A
来源:牛客网

/*
dp[i][j] 存 (i,j)对应的Alice 输赢状态,1胜,0败
根据初始态dp[0][0]=0,也就是Alice 面对此状态时,为败,推出所有胜的状态
即 dp[i+k][j+s*k]=1,dp[i+s*k][j+k]=1 

*/

#include <bits/stdc++.h>
using namespace std;
int t;
const int maxn=5005;
bool dp[maxn][maxn];
int main()
{
	for(int i=0;i<=5000;i++)
	{
		for(int j=0;j<=5000;j++)
		{
			if(!dp[i][j])
			{
				for(int k=1;i+k<=5000;k++)
				{
					for(int s=0;j+k*s<=5000;s++)
					{
						dp[i+k][j+k*s]=1;
					}
				}
				for(int k=1;j+k<=5000;k++)
				{
					for(int s=0;i+k*s<=5000;s++)
					{
						dp[i+k*s][j+k]=1;
					}
				}
			}
		}
	}
	cin>>t;
	while(t--)
	{
		int a,b;
		scanf("%d %d",&a,&b);
		if(dp[a][b]) cout<<"Alice"<<endl;
		else cout<<"Bob"<<endl;		
	}
	return 0;
	
}




上一篇:牛客2021年多校训练营<1>


下一篇:2021牛客暑期多校训练营1