首页 > 代码库 > HDOJ 5724 博弈SG函数
HDOJ 5724 博弈SG函数
链接：
http://blog.csdn.net/tc_to_top/article/details/51958964
题意：
n行20列的棋盘，对于每行，如果当前棋子右边没棋子，那可以直接放到右边，如果有就跳过放到其后面的第一个空位子，A先操作，最后谁无法操作则输，给定每行棋子状态，问先手是否必胜
题解：
组合博弈问题，直接sg函数，因为列只有20，可以状压搞，枚举每个状态，找到该状态下可行的操作然后标记
代码：
31 int sg[1 << 21];32 int vis[21];33 34 int grundy(int x) {35 memset(vis, 0, sizeof(vis));36 per(i, 0, 21) if (x&(1 << i)) {37 per(j, 0, i) if ((x&(1 << j)) == 0) {38 int y = (x ^ (1 << i) ^ (1 << j));39 vis[sg[y]] = 1;40 break;41 }42 }43 rep(i, 0, 21) if (!vis[i]) return i;44 return 0;45 }46 47 int main() {48 ios::sync_with_stdio(false), cin.tie(0);49 rep(i, 0, (1 << 20)) sg[i] = grundy(i);50 int T;51 cin >> T;52 while (T--) {53 int n;54 cin >> n;55 int ans = 0;56 while (n--) {57 int m;58 cin >> m;59 int cnt = 0;60 while (m--) {61 int x;62 cin >> x;63 x = 20 - x;64 cnt |= (1 << x);65 }66 int t = sg[cnt];67 ans ^= t;68 }69 if (ans) cout << "YES" << endl;70 else cout << "NO" << endl;71 }72 return 0;73 }
HDOJ 5724 博弈SG函数
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。