2021牛客多校联赛#1：A-Alice and Bob

A-Alice and Bob

原题链接:https://ac.nowcoder.com/acm/contest/11166/A

题目大意

有两堆石头，数量分别为 n,m 。两个人轮流操作，每次可以从一堆石头中拿走 k(k>0) 块石头，在另一堆中拿走 s*k 个石头。不能操作着输。
双方均采取最优策略，求先手胜还是后手胜。

解题思路

这是一道博弈论的经典题，用到了博弈论的基本思想：任意一个必胜态，他的下一步都是必败态。，本题的必败态显而易见，就是n,m都为0时。由它延伸的必胜态就是n|m或m|n的时候，如1,2；2,4······所以，只要事先打好表，就能直接输出答案。

代码实现

#include<bits/stdc++.h>
using namespace std;
int t,m,n;
bool a[10011][10011];
int main()
{
    for(int i=0;i<=5000;i++)for(int j=0;j<=i;j++)//一个小小的优化，j只到i，防止TLEif(a[i][j]==0){
    for(int k=1;i+k<=5000;k++)for(int l=0;j+k*l<=5000;l++)a[i+k][j+k*l]=1,a[j+k*l][i+k]=1;//防止TLEfor(int k=1;j+k<=5000;k++)for(int l=0;i+k*l<=5000;l++)a[j+k][i+k*l]=1,a[i+k*l][j+k]=1;//同上}scanf("%d",&t);while(t--){
    scanf("%d%d",&n,&m);if(a[n][m])puts("Alice");elseputs("Bob");}
}