首页 > 代码库 > [BZOJ 1874] [BeiJing2009 WinterCamp] 取石子游戏 【博弈论 | SG函数】
[BZOJ 1874] [BeiJing2009 WinterCamp] 取石子游戏 【博弈论 | SG函数】
题目链接：BZOJ - 1874
题目分析
这个是一种组合游戏，是许多单个SG游戏的和。
就是指，总的游戏由许多单个SG游戏组合而成，每个SG游戏（也就是每一堆石子）之间互不干扰，每次从所有的单个游戏中选一个进行决策，如果所有单个游戏都无法决策，游戏失败。
有一个结论，SG(A + B + C ... ) = SG(A)^SG(B)^SG(C) ...
这道题每堆石子不超过 1000 ， 所以可以把 [0, 1000] 的 SG 值暴力求出来，使用最原始的 SG 函数的定义， SG(u) = mex(SG(v)) E(u -> v) 。
然后将每一堆的 SG 值异或起来。如果必胜，就按照顺序枚举一下所有初始方案，找到必胜的就输出并退出。
代码
#include <iostream>#include <cstdio>#include <cstdlib>#include <cstring>#include <algorithm>#include <cmath>using namespace std;const int MaxNum = 1000 + 5, MaxN = 10 + 5;int n, m, Mark_Index;int A[MaxN], B[MaxN], SG[MaxNum], Mark[MaxNum];void Calc_SG() { SG[0] = 0; Mark_Index = 0; memset(Mark, 0, sizeof(Mark)); for (int i = 1; i <= 1000; ++i) { ++Mark_Index; for (int j = 1; j <= m; ++j) { if (B[j] > i) continue; Mark[SG[i - B[j]]] = Mark_Index; } for (int j = 0; j <= 1000; ++j) { if (Mark[j] != Mark_Index) { SG[i] = j; break; } } }}int main() { scanf("%d", &n); for (int i = 1; i <= n; ++i) scanf("%d", &A[i]); scanf("%d", &m); for (int i = 1; i <= m; ++i) scanf("%d", &B[i]); Calc_SG(); int Temp = 0; for (int i = 1; i <= n; ++i) Temp ^= SG[A[i]]; if (Temp == 0) printf("NO\n"); else { printf("YES\n"); bool Flag = false; for (int i = 1; i <= n; ++i) { for (int j = 1; j <= m; ++j) { if (B[j] > A[i]) continue; if ((Temp ^ SG[A[i]] ^ SG[A[i] - B[j]]) == 0) { Flag = true; printf("%d %d\n", i, B[j]); break; } } if (Flag) break; } } return 0;}
[BZOJ 1874] [BeiJing2009 WinterCamp] 取石子游戏 【博弈论 | SG函数】
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。