当面临两堆石头数量为(0,0)时失败,最后可以一次取光所有石头,此为必胜态。无论如何取,都不能面临最后一次取光石头的情况,此为必败态。
用一个二维数组f[i][j]表示两堆石头的数量,一堆为i,一堆为j,设f[i][j]=1为必胜态,f[i][j]=0为必败态。
初始状态f[0][0]=0,枚举s,k,两堆石头一堆数量为i+k,另一堆为j+sk,此时可以一次取光所有石头,是必胜态,标记 f[i+k][j+sk]=1,f[i+s*k][j+k]=1 。
遍历 i,j,寻找下一个必败态。必败态相当于是在必胜态的基础上,两堆石头分别加了k,s*k,进而变成了必败态。必败态由于无论如何取,都无法一次取完所有石头,剩下的石头可以被另一个玩家一次取光,所以是必败态。
因此,要标记出所有必胜态,只需在必败态的基础上,枚举s,k,使其变为必胜态。
从i=0,j=0开始由小到大枚举s,k,当f[i][j]=0时,枚举s,k,标记f[i+k][j+sk]=1, f[i+sk][j+k]=1。
#include<iostream> using namespace std; bool f[5001][5001]; int main() { for(int i=0; i<=5000; i++) { for(int j=0; j<=5000; j++) { if(f[i][j]==0) { for(int k=1; k+i<=5000; k++) { for(int s=0; s*k+j<=5000; s++) { f[i+k][j+s*k]=1; } } for(int k=1; k+j<=5000; k++) { for(int s=0; s*k+i<=5000; s++) { f[i+s*k][j+k]=1; } } } } } int t,n,m; scanf("%d",&t); while(t--) { scanf("%d%d",&n,&m); if(f[n][m]==0) { printf("Bob\n"); } else printf("Alice\n"); } return 0; }