2011-0043

从 Trac 迁移的文章

这是从旧校内 Wiki 迁移的文章，可能存在一些样式问题，您可以向 memset0 反馈。

原文章内容如下：

[http://en.wikipedia.org/wiki/Sprague-Grundy/ SG函数]的基本应用，Alice和Bob在一个有向图上移动，最后不能移动者便输了。
{{{
#include <set>
#include <cstdio>
#include <vector>
#include <cstring>
#include <algorithm>
using namespace std;

typedef vector<int> VI;
typedef set<int> SI;

const int MAXN = 10086;

int n;
int sg[MAXN];
VI f[MAXN];

int calc_sg(int x) {
    int i, j, k;
    SI mex;
    mex.clear();

    if (sg[x] >= 0) return sg[x];
    if (x == n) return sg[x] = 0;
    for (i=0; i<f[x].size(); ++i) {
        mex.insert(calc_sg(f[x][i]));
    }
    for (i=0; ; ++i) if (mex.find(i) == mex.end()) return sg[x] = i;
}

int main() {
    int i, j, k;
    int m;
    int x, y;
    int q;
    int tot;
    int cn(0);

    while (1 == scanf("%d", &n)) {
        for (i=1; i<=n; ++i) f[i].clear();
        for (i=1; i<n; ++i) {
            scanf("%d", &m);
            for (j=0; j<m; ++j) {
                scanf("%d", &x);
                f[i].push_back(x);
            }
        }
        memset(sg, -1, sizeof(sg));
        for (i=1; i<=n; ++i) sg[i] = calc_sg(i);
        //for (i=1; i<=n; ++i) printf("%d ", sg[i]); puts("");
        printf("Case %d:\n", ++cn);
        scanf("%d", &q);
        while (q--) {
            scanf("%d", &m);
            scanf("%d", &x);
            x = sg[x];
            for (i=1; i<m; ++i) {
                scanf("%d", &y);
                x ^= sg[y];
            }
            if (x == 0) puts("Bob");
            else puts("Alice");
        }
    }

    return 0;
}
}}}

[by delta_4d]

SG函数的基本应用，Alice和Bob在一个有向图上移动，最后不能移动者便输了。

#include <set>
#include <cstdio>
#include <vector>
#include <cstring>
#include <algorithm>
using namespace std;
typedef vector<int> VI;
typedef set<int> SI;
const int MAXN = 10086;
int n;
int sg[MAXN];
VI f[MAXN];
int calc_sg(int x) {
    int i, j, k;
    SI mex;
    mex.clear();
    if (sg[x] >= 0) return sg[x];
    if (x == n) return sg[x] = 0;
    for (i=0; i<f[x].size(); ++i) {
        mex.insert(calc_sg(f[x][i]));
    }
    for (i=0; ; ++i) if (mex.find(i) == mex.end()) return sg[x] = i;
}
int main() {
    int i, j, k;
    int m;
    int x, y;
    int q;
    int tot;
    int cn(0);
    while (1 == scanf("%d", &n)) {
        for (i=1; i<=n; ++i) f[i].clear();
        for (i=1; i<n; ++i) {
            scanf("%d", &m);
            for (j=0; j<m; ++j) {
                scanf("%d", &x);
                f[i].push_back(x);
            }
        }
        memset(sg, -1, sizeof(sg));
        for (i=1; i<=n; ++i) sg[i] = calc_sg(i);
        //for (i=1; i<=n; ++i) printf("%d ", sg[i]); puts("");
        printf("Case %d:\n", ++cn);
        scanf("%d", &q);
        while (q--) {
            scanf("%d", &m);
            scanf("%d", &x);
            x = sg[x];
            for (i=1; i<m; ++i) {
                scanf("%d", &y);
                x ^= sg[y];
            }
            if (x == 0) puts("Bob");
            else puts("Alice");
        }
    }
    return 0;
}

[by delta_4d]