题意:
给出一系列石子堆,现在每次只能从一个堆中拿出固定石子数,问输赢结果。
要点:
跟Nim博弈很像,但是这次每次只能拿固定个数,所以要用sg函数,下面是sg函数的具体定义:
sg(x) = mex ( sg(y) |y是x的后继结点 )
其中mex(x)(x是一个自然是集合)函数是x关于自然数集合的补集中的最小值,比如x={0,1,2,4,6} 则mex(x)=3;
什么是后继结点?
所谓后继结点就是当前结点经过一个操作可以变成的状态。比如对于娶4石子游戏,假如每次可以取的数目是1,2,4,当前的石子数目也就是当前状态是5,那么5的后继结点就是{5-1, 5-2, 5-4}={4,3,1};
如果5的三个后继结点的SG函数值分别为0,1,3,那么5的SG值就是集合{0,1,3}的补集的最小元素,也就是2。
关于整个游戏的sg值之和sum,定义sum=sg1 ^ sg2 ^ sg3 ^ ……sgn. 其中^表示按位异或运算。
结论:一个游戏的初始局面是必败态当且仅当sum=0时必败。
| 16125861 | Seasonal | 2960 | Accepted | 268K | 1141MS | C++ | 833B | 2016-09-26 21:02:38 |
#include<iostream>
#include<cstring>
#include<string>
#include<algorithm>
using namespace std;
const int N = 10003;
int sg[N], vis[N];
int s[108];void GetSg(int n)//sg函数模板
{int i, j;memset(sg, 0, sizeof(sg));for (i = 1; i <= N; i++){memset(vis, 0, sizeof(vis));for (j = 0; j < n; j++){if (i - s[j] >= 0)vis[sg[i - s[j]]] = 1;//说明后继点对应的sg值已经在集合中,后面不能取}for (j = 0; j <= N; j++)if (!vis[j])break;sg[i] = j;}
}int main()
{int n,m,h,num;while (scanf("%d", &n) && n != 0){string str = "";for (int i = 0; i < n; i++)scanf("%d", &s[i]);GetSg(n);scanf("%d", &m);for (int i = 0; i < m; i++){scanf("%d", &num);int ans = 0;while (num--){scanf("%d", &h);ans ^= sg[h];}str += ans ? 'W' : 'L';//ans值若为0说明输了,不为0则赢}cout << str << endl;}return 0;
}