首页 > 代码库 > ZOJ 3666 Alice and Bob (SG博弈)
ZOJ 3666 Alice and Bob (SG博弈)
题目：
http://acm.zju.edu.cn/onlinejudge/showProblem.do?problemCode=3666
题意：
给一个有向图，然后A和B轮流移动棋子，棋子在每一个位置可以重叠，当某人不能走时，输！
问A和B谁赢
方法：
显然每一局游戏都是独立的，对每一局游戏异或即可
每一局游戏的结果可以用SG求，记忆化搜索之
1 int dfs(int x) 2 { 3 if (sg[x] != -1) return sg[x]; 4 bool vis[maxn]; 5 memset(vis, 0, sizeof(vis)); 6 for (int i = head[x]; ~i; i = edge[i].next) 7 vis[dfs(edge[i].v)] = 1; 8 for (int i = 0;; i++) 9 if (!vis[i]) return sg[x] = i;10 }
代码：
1 /******************************************** 2 *ACM Solutions 3 * 4 *@Title: ZOJ 3666 Alice and Bob 5 *@Version: 1.0 6 *@Time: 2014-08-26 7 *@Solution: http://www.cnblogs.com/xysmlx/p/xxxxxxx.html 8 * 9 *@Author: xysmlx(Lingxiao Ma) 10 *@Blog: http://www.cnblogs.com/xysmlx 11 *@EMail: xysmlx@163.com 12 * 13 *Copyright (C) 2011-2015 xysmlx(Lingxiao Ma) 14 ********************************************/ 15 // #pragma comment(linker, "/STACK:102400000,102400000") 16 #include <cstdio> 17 #include <iostream> 18 #include <cstring> 19 #include <string> 20 #include <cmath> 21 #include <set> 22 #include <list> 23 #include <map> 24 #include <iterator> 25 #include <cstdlib> 26 #include <vector> 27 #include <queue> 28 #include <stack> 29 #include <algorithm> 30 #include <functional> 31 using namespace std; 32 typedef long long LL; 33 #define pb push_back 34 #define ROUND(x) round(x) 35 #define FLOOR(x) floor(x) 36 #define CEIL(x) ceil(x) 37 const int maxn = 10010; 38 const int maxm = 2000010; 39 const int inf = 0x3f3f3f3f; 40 const LL inf64 = 0x3f3f3f3f3f3f3f3fLL; 41 const double INF = 1e30; 42 const double eps = 1e-6; 43 const int P[4] = {0, 0, -1, 1}; 44 const int Q[4] = {1, -1, 0, 0}; 45 const int PP[8] = { -1, -1, -1, 0, 0, 1, 1, 1}; 46 const int QQ[8] = { -1, 0, 1, -1, 1, -1, 0, 1}; 47 struct Edge 48 { 49 int u, v; 50 int next; 51 Edge(int _u = 0, int _v = 0, int _next = 0): u(_u), v(_v), next(_next) {} 52 } edge[maxm]; 53 int head[maxn]; 54 int en; 55 void addse(int u, int v) 56 { 57 edge[en] = Edge(u, v, head[u]); 58 head[u] = en++; 59 } 60 int sg[maxn]; 61 int n; 62 int kase; 63 void init() 64 { 65 kase++; 66 memset(head, -1, sizeof(head)); 67 en = 0; 68 memset(sg, -1, sizeof(sg)); 69 } 70 void input() 71 { 72 for (int i = 1; i < n; i++) 73 { 74 int w; 75 scanf("%d", &w); 76 while (w--) 77 { 78 int x; 79 scanf("%d", &x); 80 addse(i, x); 81 } 82 } 83 } 84 void debug() 85 { 86 // 87 } 88 int dfs(int x) 89 { 90 if (sg[x] != -1) return sg[x]; 91 bool vis[maxn]; 92 memset(vis, 0, sizeof(vis)); 93 for (int i = head[x]; ~i; i = edge[i].next) 94 vis[dfs(edge[i].v)] = 1; 95 for (int i = 0;; i++) 96 if (!vis[i]) return sg[x] = i; 97 } 98 void solve() 99 {100 printf("Case %d:\n", kase);101 int ret = 0;102 int q;103 scanf("%d", &q);104 while (q--)105 {106 int w;107 ret = 0;108 scanf("%d", &w);109 while (w--)110 {111 int x;112 scanf("%d", &x);113 ret ^= dfs(x);114 }115 if (ret) puts("Alice");116 else puts("Bob");117 }118 }119 void output()120 {121 //122 }123 int main()124 {125 // int size = 256 << 20; // 256MB126 // char *p = (char *)malloc(size) + size;127 // __asm__("movl %0, %%esp\n" :: "r"(p));128 129 // std::ios_base::sync_with_stdio(false);130 #ifdef xysmlx131 freopen("in.cpp", "r", stdin);132 #endif133 134 kase = 0;135 while (~scanf("%d", &n))136 {137 init();138 input();139 solve();140 output();141 }142 return 0;143 }
ZOJ 3666 Alice and Bob (SG博弈)
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。