SG生成函数(Grundy函数)小结
#include #include #include using namespace std;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;}
POJ2960
#include #include #include #include using namespace std;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;}
poj2425
- 在所给图中随便搞一下，不论什么状态都能够转移到拓扑序更小的状态，后者即为子状态
- 当前状态的sg值须要后更新。因此兴许遍历就可以
#include #include #include #include #include using namespace std;const int MAX = 1024;vector G[MAX];int sg[MAX];bool used[MAX];bool vis[MAX][MAX];//set 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;}
hdu3980
- 当前(n,m)状态能够拿掉m个弹珠，枚举拿的位置x，于是分成x, n−m−x两个状态。
#include #include #include using namespace std;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;}