ZOJ3084_S-Nim

时间:2022-02-06 22:19:14

题目的意思是这样的,给定你若干堆石子,每次你可以从任一堆取出某些固定数量的石子,每次取完后必须保证没堆石子的数量不为0,谁无法操作了就算fail。

刚刚开始看题目的时候有点也没有思路,甚至连Sg函数也没有听过。后来学习了一番,说说自己的想法吧。

_________________有关SG函数的由来,性质及其我个人对sg函数的了解见下一篇日志。

这个题目可以这样考虑,由于每次可取的数字是一个给定的集合,我们可以求出所有的数所对应的sg的函数值(我用的是dp,不过好像跟多人喜欢用记忆化搜)。

由于博弈论里面的许多奇奇怪怪的定理,最终我们只要求出每一堆的石子数所对应的sg值的总共异或值ans,如果ans不等于0,那么说明先手有必胜的策略,否则后手有必胜的策略。

另外说明一下,sg函数值对应的是在当前状态能转化到的所有后继状态sg值中的第一个没有出现的非负整数。很神奇吧。

 #include <cstdio>
#include <cstring>
#include <algorithm>
#define maxn 10005
using namespace std; bool vis[];
int a[],sg[maxn],n,m,k,ans; void getSG()
{
for (int i=; i<maxn; i++)
{
memset(vis,false,sizeof vis);
for (int j=; j<=n && a[j]<=i; j++) vis[sg[i-a[j]]]=true;
for (int j=; ; j++)
if (!vis[j])
{
sg[i]=j;
break;
}
}
} int main()
{
while (scanf("%d",&n) && n)
{
for (int i=; i<=n; i++) scanf("%d",&a[i]);
sort(a+,a++n);
getSG();
scanf("%d",&m);
while (m--)
{
scanf("%d",&n);
ans=;
while (n--) scanf("%d",&k),ans^=sg[k];
if (ans) printf("W");
else printf("L");
}
printf("\n");
} return ;
}

相关文章