牛客多校1 A. Alice and Bob

题目链接：https://ac.nowcoder.com/acm/contest/11166/A

题目描述

Alice and Bob like playing games. There are two piles of stones with numbers n n n and m m m. Alice and Bob take turns to operate, each operation can take away k ( k > 0 ) k(k>0) k(k>0) stones from one pile and take away s × k ( s ≥ 0 ) s × k (s≥0) s×k(s≥0) stones from another pile. Alice plays first. The person who cannot perform the operation loses the game.

Please determine who will win the game if both Alice and Bob play the game optimally.

输入描述:

The first line contains an integer T T T ( 1 ≤ T ≤ 1 0 4 1≤T≤10^4 1≤T≤104)

) denotes the total number of test cases.

Each test case contains two integers n , m ( 1 ≤ n , m ≤ 5 × 1 0 3 ) n,m(1 \le n,m \leq 5 \times 10^3) n,m(1≤n,m≤5×103)in a line, indicating the number of two piles of stones.

输出描述:

For each test case, print “Alice” if Alice will win the game, otherwise print “Bob”.

示例1

输入

5

2 3

3 5

5 7

7 5

7 7

输出

Bob

Alice

Bob

Bob

Alice

题目大意：

给定两堆石头，两玩家Alice和Bob将轮流执行以下操作（Alice先手）：

选定其中一堆，从中移除k块石头，k为正整数，并从另一堆中移除s * k块石头，其中s为非负整数。

当某玩家试图从数量小于k的堆中移除k块石头时，该操作不可执行

当某玩家没有任意一个操作可以执行时，则该玩家输掉本局，对方胜出。

给定T组数据，每组数据给定两个整数n，m表示两堆石头的数量。

若Alice和Bob每次都会执行最优操作，那么谁会胜出？

思路：

博弈类的游戏，每一个局面都对应着“最优策略下 先手/后手必胜”的情况，也就是说，没有所谓的局面，是胜手不确定的。

首先，我们知道，当两堆石头的石头数都为0的局势下，轮到的一方必然输掉对局。

即，当n = 0, m = 0时，轮到Alice操作的话，Alice就输掉对局。

把这个局势命名为局势A，把先手必败的局势称为败点，与之相反的是胜点，如果由某一种局势B，可以通过合法的操作将局势B变成局势A（败点A），那么局势B情况下轮到的玩家必胜，因为他可以将局势引导到一个先手必败的局面，并让对方成为先手。

这意味着，对于一个败点，我们可以逆推出范围内的可以一步到达这个败点的胜点。

这里的局面表示起来比较方便，只需要建立一个布尔类型的二维数组，两个下标分别表示两堆石头的数量，对应的值用来表示其为败点或者胜点即可。

依照题目的操作规则，两堆石头的数量不会增加，那么对于一个局势A，进行一次操作变成局势B之后，B的石头总数一定是比A要少的。其中一堆移除k个石头，另一堆移除k*s个石头。

那么逆推的情况下，我们就要将操作反过来用。若当前局势为X，我们可以选择其中一堆加上k个石头，另一堆则加上k*s个石头，从而得到局势Y，如果Y的数据在题目给定范围内， 则视为合法的。

首先，（0,0）是败点，依照逆推的方式，我们可以知道

( 0 + k , 0 + k * s )，( 0 + k * s , 0 + k )是胜点 ，其中k为正整数，s为非负数

注：(a ,b)可以由（a + k , b + s * k）得到，也可由(a + s * k , b + k)得到

同理有：如果（ i , j ）是败点，那么( i + k , j + k * s)，( i + k * s, j + k )是胜点

每当我们找到一个败点，就将其可逆推到的所有局势标记为胜点。我们从小到大寻找没有被标记为胜点的点，找到的点就一定是败点（因为先前逆推的时候没有推到这个局势，说明这个局势走不到接下来的败点，那么它自己就不是胜点，所以只能是败点）。然后从这个败点再往上逆推。

AC代码：

#include<iostream>
#include<stdio.h>
using namespace std;
bool ans[5003][5003] = { false };
int main() {
    for (int i = 0; i <= 5000; i++) {
        for (int j = 0; j <= 5000; j++) {
            if (ans[i][j] == false) {
                for (int k = 1; k + i <= 5000; k++) {
                    for (int s = 0; k * s + j <= 5000; s++) {
                        ans[i + k][j + s * k] = true;
                    }
                }
                for (int k = 1; k + j <= 5000; k++) {
                    for (int s = 0; s * k + i <= 5000; s++) {
                        ans[i + s * k][j + k] = true;
                    }
                }
            }
        }
    }
    int t, n, m;
    cin >> t;
    while (t--) {
        cin >> n >> m;
        printf("%s\n", ans[n][m] ? "Alice" : "Bob");
    }
}