牛客多校第一场 A. Alice and Bob （暴力SG）

题目大概

有两堆石子，有两个人拿，一个人从一堆中拿(k)个，那么就必须从另一堆中拿(s*k)个，Alice先拿，问是否必赢。

解题：

数据不大，看到前(20)名队伍没有推结论做的。。除了打表就是暴力，其实打表还是暴力，但是打1000多行的表也太恐怖了吧。。暴力就是暴力处理每一种状态下(SG)所有情况，(SG[n][m])就表示当前第一堆石子数量为(n)，第二堆石子数量为(m)的(SG)函数，那么再枚举一个(k)和(s)，暴力即可，这打眼一看好像复杂度很恐怖，这难道就是高手们的经验吗。。

注意：一开始我用了(int)数组判断(true)，(false\,\,\,\,T)到飞起，后来换成(bool)数组，八百毫秒就过了。

哦记得，不要忘了处理(SG(0，0))的情况

#include <iostream>

using namespace std;

const int N = 5002;
bool sg[N][N];

void cal(int n, int m) {
    for (int k = 1; n + k < N; k++) {
        for (int s = 0; m + s * k < N; s++) {
            sg[n + k][m + k * s] = 1; //先拿第一堆
        }
    }
    swap(n, m);
    for (int k = 1; n + k < N; k++) {
        for (int s = 0; m + s * k < N; s++) {
            sg[m + k * s][n + k] = 1; //先拿第二堆
        }
    }
}

int main() {
    cal(0 ,0);
    for (int i = 1; i < N; i++) {
        for (int j = 0; j < N; j++) {
            if (!sg[i][j]) {
                cal(i, j);
            }
        }
    }
    
    int t;
    cin >> t;
    while (t--) {
        int n, m;
        cin >> n >> m;
        if (!sg[n][m]) puts("Bob");
        else puts("Alice");
    }

    return 0;
}