这也是nim游戏,但是sg就不是一个数了,而是一个二元组。
考虑到数据量,我们可以直接记忆化递归暴力求解sg值,然后再异或就可以了
##代码如下:

#include<iostream>
#include<algorithm>
#include<vector>
#include<functional>
using namespace std;
int sg[1500][1500];
bool check(int x, int y) { return x >= 0 && y >= 0; }
int SG(int x,int y) {
    if (sg[x][y] != -1)return sg[x][y];
    vector<int> res;
    int xx = x + 1;int yy = y - 2;
    if (check(xx, yy))res.push_back(SG(xx, yy));
    xx = x - 2;yy = y + 1;
    if (check(xx, yy))res.push_back(SG(xx, yy));
    xx = x - 1;yy = y - 3;
    if (check(xx, yy))res.push_back(SG(xx, yy));
    xx = x - 3;yy = y - 1;
    if (check(xx, yy))res.push_back(SG(xx, yy));
    xx = x - 1;yy = y - 2;
    if (check(xx, yy))res.push_back(SG(xx, yy));
    xx = x - 2;yy = y - 1;
    if (check(xx, yy))res.push_back(SG(xx, yy));
    sort(res.begin(), res.end(), greater<int>());
    for (int i = 0;i <= 250000;++i) {
        if (res.empty())return sg[x][y] = i;
        int tmp = res.back();res.pop_back();
        while (!res.empty() && res.back() == tmp)res.pop_back();
        if (tmp != i)
            return sg[x][y] = i;
    }
}
int main() {
    ios::sync_with_stdio(0);
    for (int i = 0;i < 1500;++i)for (int j = 0;j < 1500;++j)sg[i][j] = -1;
    int T;cin >> T;
    for (int tcase = 1;tcase <= T;++tcase) {
        int n;cin >> n;int ans = 0;
        for (int i = 1, x, y;i <= n;++i) {
            cin >> x >> y;
            ans ^= SG(x, y);
        }cout << "Case " << tcase << ": ";
        ans > 0 ? cout << "Alice\n" : cout << "Bob\n";
    }
}