[cf 1194 D] 1-2-K Game

（当时让这道sb题卡住了，我比sb还sb）

题意：

n个东西，两个人轮流取，每次可以取走1个，2个或k个，不能取的人输，求谁必胜。

$0\leq n \leq 10^{9},3\leq k \leq 10^{9}$

题解：

假如没有这个$k$，显然如果$n$是3的倍数则后手赢，否则先手赢。

操作方法就是某一个人永远保证$n\equiv 0(mod 3)$

那么这个题的思考方式就是：

若$k\equiv 0(mod 3)$，推一下SG函数，容易发现它有一个长度为$(k+1)$的循环节，于是$mod(k+1)$后按SG值判断即可。
否则，这个$k$的作用跟1或2一样，取不取$k$不影响必胜情况，按原来的方法判断即可。

代码：

#include<bits/stdc++.h>

#define maxn 100005

#define maxm 500005

#define inf 0x7fffffff

#define ll long long

using namespace std;

int N,K;

inline int read(){

    int x=,f=; char c=getchar();

    for(;!isdigit(c);c=getchar()) if(c=='-') f=-;

    for(;isdigit(c);c=getchar()) x=x*+c-'';

    return x*f;

}

int main(){

    int T=read();

    while(T--){

        N=read(),K=read();

        if(K%==) N%=(K+);

        if((N+)%== && N!=K) printf("Bob\n");

        else printf("Alice\n");

    }

    return ;

}

1-2-K Game

巴特西

[cf 1194 D] 1-2-K Game

最新文章

热门文章