对于每一个k (下述代码中a[2]) 打表 n(1~99)找规律
#include<iostream>
#include<cstring>
#include<set>
#define ll long long
using namespace std;
const int N=1e4+10;
ll n,m,a[3],T;
int f[1000];
int sg(ll x){
if(f[x]!=-1)return f[x];
set<ll> s;
for(int i=0;i<3;i++)
if(a[i]<=x)s.insert(sg(x-a[i]));
for(ll i=0;;i++)
if(!s.count(i))return f[x]=i;
}
int main(){
memset(f,-1,sizeof f);
a[0]=1,a[1]=2;a[2]=15;//每次改变a[2]打表找规律
for(int i=0;i<100;i++){
if(!(i%16)&&i)puts("");//改变i%数便于发现规律
printf("%2d %c ",i,sg(i)?'W':'L');
}
return 0;
}
W表示先手必胜 L表示先手必败
可以发现 k%3!=0时都有如下结果:
k=4:
k=7:
而对于 k%3==0 则:
k=9:
k=15:
根据打表代码可以得出规律:
k%3!=0:n%3==0为必败态
k%3==0:若n可以表示为$$ t*(k+1) + 3g (t,g=0,1,2… , 3g<k)$$ 则为必败态
AC代码:
#include<iostream>
using namespace std;
int n,m,k,T;
int main(){
cin>>T;
while(T--){
cin>>n>>k;
if(!(k%3)){
n%=k+1;
if(n==k||n%3)puts("Alice");
else puts("Bob");
}
else{
if(n%3)puts("Alice");
else puts("Bob");
}
}
return 0;
}