2021牛客暑期多校训练营1 A题 Alice and Bob

题目描述

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)$ stones from one pile and take away $s \times k(s \geq 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(1 \le T \le 10^4)$ denotes the total number of test cases.
Each test case contains two integers $n,m(1 \le n,m \leq 5 \times 10^3)$ 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

题解

这是一道博弈题。题目大致是给你两堆石块，两个人可以选择从任意一个石堆取走${k}(k>0)$个，同时从另一个石堆中取走$s \times k(s \geq 0)$ 个。如果某个人没有办法进行操作，便输了游戏。给定$n$和$m$，问先手必胜还是必败。

做博弈题，我们先确定下状态转移。我们如果知道一个必败态$（a，b）$，那么必胜态一定是$（a+k，b+s*k）$或者$（a+s*k，b+k）$。那么下一个必败态一定是无法由已经得到的必败态通过转移得到。再看一下数据范围，5000*5000，那么我们估算一下必败态数量，可以看出来很少（咳咳应该可以看出来吧）。所以我们只需要对每一个必败态都进行状态转移（类似于埃氏筛的原理），可以转移的就打上必胜态标记，那么遇到没有打上必胜态标记的，一定是必败态（不能由前面的必败态转移得到）。

至于如何开始，首先输的状态一定是（0，0），那么（0，0）可以看作是一个必败态，我们从（0，0）开始转移。

代码

代码如下：

#include <algorithm>
#include <cmath>
#include <iostream>
#include <queue>
#include <string>
#include <vector>
using namespace std;
const int maxn = 5e3 + 5;
typedef long long ll;

int T;
int n, m;
bool a[maxn][maxn];
inline void check(int x, int y) {
  for (int i = x + 1; i < maxn; i++) {
    a[i][y] = 1;
    a[y][i] = 1;
  }
  for (int i = y + 1; i < maxn; i++) {
    a[x][i] = 1;
    a[i][x] = 1;
  }
  for (int i = 1; i + x < maxn; i++) {
    for (int j = 1; j * i + y < maxn; j++) {
      a[x + i][y + j * i] = 1;
      a[y + j * i][x + i] = 1;
    }
  }
  for (int i = 1; i + y < maxn; i++) {
    for (int j = 1; j * i + x < maxn; j++) {
      a[x + j * i][y + i] = 1;
      a[y + i][x + j * i] = 1;
    }
  }
}

int main() {
  for (int i = 0; i < maxn; i++) {
    for (int j = i; j < maxn; j++) {
      if (a[i][j] != 1) {
         check(i, j);
      }
    }
  }
  scanf("%d", &T);
  while (T--) {
    scanf("%d%d", &n, &m);
    if (a[n][m] == 1)
      cout << "Alice" << '\n';
    else
      cout << "Bob" << '\n';
  }
  return 0;
}