博弈–ZOJ 3084 S-Nim（SG）

开发者一涵技术 2022年11月12日

0 收藏 572 点赞 3,901 浏览 1555 个字

题意：首先输入K 表示一个集合的大小之后输入集合表示对于这对石子只能去这个集合中的元素的个数之后输入一个m 表示接下来对于这个集合要进行m次询问之后m行每行输入一个n 表示有n个堆每堆有n1个石子问这一行所表示的状态是赢还是输如果赢输入W否则L 思路：对于n堆石子可以分成n个游戏之后把n个游戏合起来就好了模板一：递归

#include<stdio.h>
#include<string.h>
#include<algorithm>
using namespace std; //记得加int SG[10100],n,m,fib[102],k;//k是集合s的大小 S[i]是定义的特殊取法规则的数组
int dfs(int x)//求SG[x]模板
{  int i;
    if(SG[x]!=-1) return SG[x];
    bool vis[110];
    memset(vis,0,sizeof(vis));      for(i=0;i<k;i++)
    {
        if(x>=fib[i])
        {
           dfs(x-fib[i]);
           vis[SG[x-fib[i]]]=1;
         }
    }
    int e;
    for(i=0;;i++)
      if(!vis[i])
      {
        e=i;
        break;
      }
    return SG[x]=e;
}  int main()
{while(scanf("%d",&k)!=EOF){
if(k==0)break;
 memset(SG,-1,sizeof(SG));
 for(int i2=0;i2<k;i2++){
scanf("%d",&fib[i2]);
}
   sort(fib,fib+k);
int mg;
scanf("%d",&mg);
while(mg--){
    //memset(a,0,sizeof(a));
int t2;
scanf("%d",&t2);int ans = 0;int num;
while(t2--){
scanf("%d",&num);
ans^= dfs(num);
}if(ans==0) printf("L");
        else    printf("W");}
printf("\n");
}
    return 0;}

模板二：SG打表

#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
const int K=101;
const int H=10001;//H是我们要打表打到的最大值
int k,m,l,h,s[K],sg[H],mex[K];///k是集合元素的个数 s[]是集合  mex大小大约和集合大小差不多
///注意s的排序
void sprague_grundy()
{
    int i,j;
    sg[0]=0;
    for (i=1;i<H;i++){
        memset(mex,0,sizeof(mex));
        j=1;
        while (j<=k && i>=s[j]){
            mex[sg[i-s[j]]]=1;
            j++;
        }
        j=0;
        while (mex[j]) j++;
        sg[i]=j;
    }
}int main(){
    int tmp,i,j;    scanf("%d",&k);
    while (k!=0){
        for (i=1;i<=k;i++)
            scanf("%d",&s[i]);
        sort(s+1,s+k+1);            //这个不能少
        sprague_grundy();
        scanf("%d",&m);
        for (i=0;i<m;i++){
            scanf("%d",&l);
            tmp=0;
            for (j=0;j<l;j++){
                scanf("%d",&h);
                tmp=tmp^sg[h];
            }
            if (tmp)
                putchar('W');
            else
                putchar('L');
        }
        putchar('\n');
        scanf("%d",&k);
    }
    return 0;}