AcWing 4005. 取石子游戏
原题链接
困难
作者:
氘ba-wt
,
2021-12-21 16:44:28
,
所有人可见
,
阅读 317
/*
博弈论问题
初始状态:先手必胜、先手必败显然的状态
其他位置到底是必胜还是必败,如何确定?
(假设当前取数的方法有很多,至少一个)
如果取完之后让下一个人取的状态有一种是必败态
(其余取法可以必胜态)
那么当前取数的人就是必胜态(可以自主选择让下一个人成为必败)
同理,如果取完之后的状态全部是必胜态
那么当前取数的人就是必败态(无论如何取,下一个人都是必胜)
下文A表示当前位置先取必胜,B表示先取必败
按照本题意思:
0位 B(没数可取)
1位 A(取1个就取完了)
2位 A(取2个就取完了)
先假设K很大
3位 B(不管取1还是取2,下一个人都是必胜了)
4位 A(只要取1个,让下一个人面对3就必败了)
5位 A(只要取2个,让下一个人面对3就必败了)
6位 B (同理)
……
所以,如果当前数小于K,结论是模3为0则B,否则为A。
又
K位必定是A(一次性取完)
如果K模3非0,则所有位置取1、取2、取K(%3 != 0)
按照之前的讨论,3x + 1和3x + 2位置都是A,K位A不稀奇
若当前位置为3y,按照之前讨论,
结论应该是B(证明:已知减1和减2都是A,再看减K)
现在可以取K值,3y-(3x+1) 或者 3y-(3x+2)都是模3非零0位,
即都是A,
则取完1、2、K之后都是A位,则当前位是B位
若当前位置是3y + 1或者3y + 2,其前两位必定有B,则当前为A。
换句话说,K模3非0,结论和不取K值的结论一致。
如果K模3为0,则需要单独讨论,(这里记K=3x)
本来模3为0的位置是B,现在可以取K,则强行改成了A,
K-1位A
K 位A
K+1位B(前两位A,K+1是3y+1,而(3y+1)-(3x)=3z+1 < K,也是A)
K+2位A(前两位有B)
K+3位A(前两位有B)
K+4位B(设K很大,K+4是3y+1,而(3y+1)-(3x)=3z+1 < K,也是A)
从K+1开始BAABAABAA……依次循环
2K-2位 B,(按照前面结论,注意K%3=0)
2K-1位 A,(按照前面结论)
2K 位 A,(BAA-->A)
2K+1位 A,(AA,(t-1)K+1位是B,所以是A)
从2K+2开始BAABAABAA……依次循环
3K+2位出现一个A
从3K+3开始BAABAABAA……依次循环
所以从K位开始是A(BAA...BAA)A(BAA...BAA)A(BAA...)A
结论是n%=(K+1),如果n==k或者n%3>0即A,否则为B
*/
#include<bits/stdc++.h>
using namespace std;
int main() {
int T;
cin >> T;
while(T--) {
int n, k;
cin >> n >> k;
if(k % 3 || n < k){
puts(n % 3 ? "Alice" : "Bob");
}else{
n %= k + 1;
puts(n == k || n % 3 ? "Alice" : "Bob");
}
}
return 0;
}