这也是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"; } }