【Coreforces-1194D】1-2-K Game

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

题意:T组样例,给你一堆数量为a的石子,每次可以取1 ,2 或 k个,无法进行操作的人必败,输入败的人。

题解:这是一个博弈论,打表模拟, 分两种情况,

  1、如果b为3的倍数,打表模拟k = 3、6;

    当k = 3时,必败态有 0 4  8 12 ......

    当k = 6时,必败态有 0  7  14 21 .......

               3 10 17 24 .......

    结论:当 a%(k+1)%3==0并且 a%(k+1)!=k 必败。

  2、如果b不为3的倍数,不考虑取出k个(原因:只考虑必败态的话,它对必败态没有任何影响,因此必胜态也不会受到影响),也就是,只判断a%3的结果即可。

代码如下:

#include <cstdio>
using namespace std;
int main(){
    int T;
    scanf("%d",&T);
    while(T--){
        int a,b;
        scanf("%d%d",&a,&b);
        if(b%3==0){
            if(a%(b+1)%3==0&&a%(b+1)!=b)printf("Bob
");
            else printf("Alice
");
        }
        else{
            if(a%3==0)printf("Bob
");
            else printf("Alice
");
        }
    }
    return 0;
}
原文地址:https://www.cnblogs.com/Vagrant-ac/p/12111170.html