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);
    }
}