首页 > 代码库 > [BZOJ 1188] [HNOI2007] 分裂游戏 【博弈论|SG函数】
[BZOJ 1188] [HNOI2007] 分裂游戏 【博弈论|SG函数】
题目链接：BZOJ - 1188
题目分析
我们把每一颗石子看做一个单个的游戏，它的 SG 值取决于它的位置。
对于一颗在 i 位置的石子，根据游戏规则，它的后继状态就是枚举符合条件的 j, k。然后后继状态就是 j 与 k 这两个游戏的和。
游戏的和的 SG 值就是几个单一游戏的 SG 值的异或和。
那么还是根据 SG 函数的定义 ， 即 SG(u) = mex(SG(v)) ，预处理求出每个位置的 SG 值。一个位置的 SG 值与它后面的位置有关，是取决于它是倒数第几个位置，那么我们预处理求出的 SG[i] 是指倒数第 i 个位置的 SG 值。
还有一个十分重要的性质，我们不需要考虑每个位置上石子的数量，只需要考虑数量的奇偶，因为如果有偶数个石子，那么这个位置的 SG 值会被异或到整个状态的 SG 中共偶数次，就会抵消，相当于没有。
奇数就是相当于偶数 + 1，因此只要异或一次即可。
组合游戏真是有许多神奇的性质Orz。
代码
#include <iostream>#include <cstdlib>#include <cstring>#include <cstdio>#include <algorithm>#include <cmath>using namespace std;const int MaxN = 25, N = 21;int T, n, Mark_Index;int A[MaxN], SG[MaxN], Mark[MaxN * MaxN];void Prepare_SG() { Mark_Index = 0; memset(Mark, 0, sizeof(Mark)); for (int i = 1; i <= N; ++i) { ++Mark_Index; for (int j = i - 1; j >= 1; --j) for (int k = j; k >= 1; --k) Mark[SG[j] ^ SG[k]] = Mark_Index; for (int j = 0; j <= N * N; ++j) { if (Mark[j] != Mark_Index) { SG[i] = j; break; } } }}int main() { scanf("%d", &T); Prepare_SG(); for (int Case = 1; Case <= T; ++Case) { scanf("%d", &n); for (int i = 1; i <= n; ++i) scanf("%d", &A[i]); int Temp = 0, Tot = 0; for (int i = 1; i <= n; ++i) if (A[i] & 1) Temp ^= SG[n - i + 1]; for (int i = 1; i <= n; ++i) { if (A[i] == 0) continue; for (int j = i + 1; j <= n; ++j) { for (int k = j; k <= n; ++k) { if ((Temp ^ SG[n - i + 1] ^ SG[n - j + 1] ^ SG[n - k + 1]) != 0) continue; ++Tot; if (Tot == 1) printf("%d %d %d\n", i - 1, j - 1, k - 1); } } } if (Tot == 0) printf("-1 -1 -1\n"); printf("%d\n", Tot); } return 0;}
[BZOJ 1188] [HNOI2007] 分裂游戏 【博弈论|SG函数】
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。