zoj 3666 Alice and Bob ， SG函数

在一个有向无环图上，有若干玩具，每人每次只能将一个玩具移动一步，玩具被移动到终点n将不能再被移动了，最后不能移动者输。

组合博弈

SG函数应用

#include<vector>
#include<cstdio>
#include<cstring>
#include<algorithm>

using namespace std;

const int maxn = 10000 + 100;
int SG[maxn];
vector<int> g[maxn];

int mex(int u) { //minimal excludant
    if(SG[u]!=-1) return SG[u];
    int i;
    bool vis[maxn];
    memset(vis, 0, sizeof vis );
    for(i=0; i<g[u].size(); ++i) {
        vis[mex(g[u][i])] = true;
    }
    for(i=0; vis[i]; ++i);
    return SG[u] = i;
}

int main() {
    int n, c, x, q, m;
    int cas= 1;
    while(~scanf("%d", &n)) {
        for(int i=0; i<=n; ++i) g[i].clear();
        for(int i=1; i<n; ++i) {
            scanf("%d", &c);
            while(c--) {
                scanf("%d", &x);
                g[i].push_back(x);
            }
        }
        memset(SG, -1, sizeof SG );
        printf("Case %d:\n", cas++);
        scanf("%d", &q);
        while(q--) {
            scanf("%d", &m);
            int ans = 0;
            while(m--) {
                scanf("%d", &x);
                ans ^= mex(x);
            }
            if(ans) puts("Alice");
            else puts("Bob");
        }
    }
    return 0;
}

zoj 3666 Alice and Bob ， SG函数

原文：http://blog.csdn.net/yew1eb/article/details/38852709