中石油个人训练赛第18场问题 J: 1-2-K Game Bash游戏变形&&博弈论

题目描述

Alice and Bob play a game. There is a paper strip which is divided into n + 1 cells numbered from left to right starting from 0. There is a chip placed in the n-th cell (the last one).

Players take turns, Alice is first. Each player during his or her turn has to move the chip 1, 2 or k cells to the left (so, if the chip is currently in the cell i, the player can move it into cell i - 1, i - 2 or i - k). The chip should not leave the borders of the paper strip: it is impossible, for example, to move it k cells to the left if the current cell has number i < k. The player who can't make a move loses the game.

Who wins if both participants play optimally?

Alice and Bob would like to play several games, so you should determine the winner in each game.

输入

The first line contains the single integer T (1 ≤ T ≤ 100) — the number of games. Next T lines contain one game per line. All games are independent.

Each of the next T lines contains two integers n and k (0 ≤ n ≤ 109, 3 ≤ k ≤ 109) — the length of the strip and the constant denoting the third move, respectively.

输出

For each game, print Alice if Alice wins this game and Bob otherwise.

样例输入

复制样例数据

样例输出

Bob
Alice
Bob
Alice

题目大意：抽象出来就是，有n个石头，你每次只能拿 1 2 或者k 个，谁最后拿完谁赢，Alice先拿，问Alice是否会输。

题目思路：Bash游戏的变形，分两种情况：

1.k不是3的倍数

因为k不是3的倍数，所以3是必输局面，也就是谁碰到这个局面谁就输。

接下来我们考虑，如果n是3的倍数，先手先拿，后手绝对可以使当前局面成为3的倍数，先手拿1 后手拿2 ，2 1 ，先手拿 k 后手拿 3-(k%3) < 3{1 2}，所以后手总有办法让先手陷入3的倍数的局面，这个倍数一点点减少，最后就会使得先手面临0 和 3的局面，这两种局面都是必输，所以这种情况下先手必输。再考虑 n不是3的倍数，这种情况下，先手只要拿3的余数使得当前局面时3的倍数，那对手就面临必输局所以先手必赢。

2.k是3的倍数

还是一样，首先考虑必输局面 k+1是必输局面，拿k我拿1，拿1我拿k，拿2的话因为k-1<k 又陷入了拿1 拿2 的环节又因为k是3的倍数，所以k-1一定不是3的倍数，所以拿2的话会让对手面临必赢局面，所以k+1是必输局面。这么考虑如果n%k+1==0，那么你拿一个对手都可以给你凑成 m*(k+1)的局面，到最后你还是必输局面。所以n%k+1==0是必输局面。如果n%k+1！=0，那么他的余数就是1 2 3 ....k 如果余数是k，那么必赢，因为可以一次拿到k使得对面陷入 n%k+1==0的局面，余数<k,问题就转换成了，谁想赢的话，谁就最后一个拿完使得对面陷入m*(k+1)的必输局面，所以右成了1 2 的问题，如果res%3==0 那么必输，否则必赢。

第一次玩博弈论，感觉好热血啊哈哈哈哈，附AC代码：

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const ll INF=1e15+5;
const int maxn=1e6+8;
const double PI=acos(-1);
const ll mod=1e9+7;
ll n,m;
ll num[maxn];
int main()
{
    ll k;
    int T;
    scanf("%d",&T);
    while(T--)
    {
        scanf("%lld%lld",&n,&k);
        if(k%3!=0)
        {
            if(n%3==0)
                printf("Bob\n");
            else
                printf("Alice\n");
        }
        else
        {
            if(n%(k+1)==0) printf("Bob\n");
            else
            {
                ll res=n%(k+1);
                if(res%3==0&&res!=k) printf("Bob\n");
                else printf("Alice\n");
            }
        }
    }
    return 0;
}

Bash博弈变形。