转移到子游戏
模板;const int MAX = 100007;const int MAX_S = 128;const int MAX_X = MAX;int sg[MAX], stone[MAX_S];int vis[MAX];int X[MAX_S];void get_sg(){sg[0] = 0;for (int i = 1; i < MAX_X; ++i){for (int j = 1; j <= MAX_S; ++j){if (i >= stone[j]){vis[sg[i – stone[j]]] = i;}}int g = -1;while (vis[++g] == i);sg[i] = g;}}void gao(){get_sg();int res = 0;for (int i = 1; i <= MAX_S; ++i){res ^= sg[X[i]];}puts(res ? “player1 wins.” : “player2 wins.”);}int main(){return 0;};const int MAX = 100007;const int MAX_S = 107;int vis[MAX];int X[MAX_S][MAX_S];int max_xx[MAX_S];int I[MAX_S];int sg[MAX];int s[MAX_S];int main(){int k, m;while (~scanf(” %d”, &k) && k){for (int i = 1; i <= k; ++i){scanf(” %d”, s + i);}scanf(” %d”, &m);for (int i = 1; i <= m; ++i){scanf(” %d”, I + i);max_xx[i] = 0;for (int j = 1; j <= I[i]; ++j){scanf(” %d”, &X[i][j]);if (X[i][j] > max_xx[i]){max_xx[i] = X[i][j];}}}sg[0] = 0;int max_x = 0;for (int i = 1; i <= m; ++i){if (max_x < max_xx[i]){max_x = max_xx[i];}}memset(vis, 0, sizeof(vis));for (int i = 1; i <= max_x; ++i){for (int j = 1; j <= k; ++j){if (s[j] <= i){vis[sg[i – s[j]]] = i;}}int g = 0;while (vis[g] == i){++g;}sg[i] = g;}for (int i = 1; i <= m; ++i){int res = 0;for (int j = 1; j <= I[i]; ++j){res ^= sg[X[i][j]];}putchar(res ? ‘W’ : ‘L’);}putchar(‘\n’);}return 0;}在所给图中随便搞一下，任何状态都可以转移到拓扑序更小的状态，后者即为子状态当前状态的值需要后更新，因此后续遍历即可;const int MAX = 1024;vector<int> G[MAX];int sg[MAX];bool used[MAX];bool vis[MAX][MAX];//set<int> vis[MAX];void dfs(int v){used[v] = true;for (int i = 0; i < G[v].size(); ++i){if (!used[G[v][i]]){dfs(G[v][i]);}vis[v][sg[G[v][i]]] = true;//vis[v].insert(sg[G[v][i]]);}int g = -1;while (vis[v][++g]);sg[v] = g;}inline void read(int& x){char c;while ((c = getchar()) < ‘0’ || c > ‘9’);x = c – ‘0’;while ((c = getchar()) >= ‘0’ && c <= ‘9’){x = (x << 3) + (x << 1) + c – ‘0’;}}int main(){int n;while (~scanf(” %d”, &n)){for (int i = 0; i < n; ++i){G[i].clear();}memset(vis, false, sizeof(vis));int m, v;for (int i = 0; i < n; ++i){read(m);//scanf(” %d”, &m);while (m–){read(v);//scanf(” %d”, &v);G[i].push_back(v);}}memset(used, false, sizeof(used));for (int i = 0; i < n; ++i){if (!used[i]){dfs(i);}}/*for (int i = 0; i < n; ++i){printf(“sg[%d] = %d\n”, i, sg[i]);}*/while (true){read(m);if (m == 0){break;}int res = 0;while (m–){read(v);//scanf(” %d”, &v);res ^= sg[v];//printf(“res = %d\n”, res);}puts(res ? “WIN” : “LOSE”);}}return 0;}当前两个状态。;const int MAX = 1024;int sg[MAX];int get_sg(int n, int m){if (n < m){return sg[n] = 0;}else if (sg[n] != -1){return sg[n];}bool vis[MAX] = {0};for (int i = 0; i <= n – m; ++i){vis[get_sg(i, m) ^ get_sg(n – m – i, m)] = true;}int g = -1;while (vis[++g]);return sg[n] = g;}int main(){int T, n, m;scanf(” %d”, &T);while (T–){scanf(” %d %d”, &n, &m);memset(sg, -1, sizeof(sg));static int __ = 1;printf(“Case #%d: %s\n”, __++, (n >= m && !get_sg(n – m, m)) ? “aekdycoin” : “abcdxyzk”);}return 0;}
，可你仍然感谢天地和人世所带来的这些变化和发生。
