cfecr68 1-2-K Game (简单巴什博弈变形)

https://codeforces.com/contest/1194/problem/D

一堆n石头中可以取1,2,k个,没得取就输。

规律完全可以打表看出来,k%3==0时循环节是3,否则循环节是k+1。k+1里面又会有1,1,0,1,1,0这种循环节是3的模式。

当然也可以简单证明一下,当k足够大的时候n<=k部分就是只能取1,2的巴什博弈,胜负判断条件当然是n%3。然后达到k的时候,若k%3==0,那么不会改变必败的情况。若k%3不为0,那么一个原本必败位置变为必胜,之后(k+1)这段内部又是3的循环节,所以大循环节是(k+1)。

  1.  
  2.  
  3.     /*
  4.     Author: fffasttime
  5.     Date: 
  6.     */
  7.     #include <bits/stdc++.h>
  8.     using namespace std;
  9.     typedef long long ll;
  10.     #define inc(i,n) for (int i=0;i<n;i++)
  11.     const int N=100010;
  12.  
  13.     int a[10000];
  14.  
  15.     int main(){
  16.     	int T; cin>>T;
  17.     	while (T--){
  18.     		int n,k; cin>>n>>k;
  19.     		int ans;
  20.     		if (k%3) ans=n%3;
  21.     		else{
  22.     			int r=n%(k+1);
  23.     			if (r==k) ans=1;
  24.     			else ans=r%3;
  25.     		}
  26.     		puts(ans?"Alice":"Bob");
  27.     	}
  28.     	return 0;
  29.     }

发表评论

您的电子邮箱地址不会被公开。 必填项已用*标注