nim
我们可以很清楚地看出来,这应该是一个nim游戏。
因为,我们可以把它分为每一行地小博弈所组成的一个矩形的大博弈。
那么我们的关注点就要放在,每一行上的小博弈上了。
乍一看,这个小博弈很复杂。还牵扯到每一列。
但是,我们究其本质还会发现,取哪一列其实并没有什么关系。
是否?关键是我取了多少石子,还剩多少石。
简而言之,我们根本不需要更关心每一列。直接统计每一行的石子数,做nim博弈就好了
代码如下:
#include<iostream> #include<algorithm> #include<cstdio> using namespace std; typedef long long ll; int main() { int T;scanf("%d", &T); for (int tcase = 1;tcase <= T;++tcase) { int m, n; scanf("%d %d", &m, &n); ll ans = 0; for (ll i = 1, res = 0;i <= m;++i, res = 0) { for (ll j = 1, tmp;j <= n;++j) { scanf("%lld", &tmp); res += tmp; }ans ^= res; }ans > 0 ? printf("Case %d: Alice\n", tcase) : printf("Case %d: Bob\n", tcase); } }