Position：

http://poj.org/problem?id=2960

List

Poj2960 S-Nim
- List
- Description
- Knowledge
- Solution
- Notice
- Code

Description

大意：有n堆石子，每堆石子个数已知，两人轮流从中取石子，每次可取的石子数x满足x属于集合S(k) = {s1,s2,s3…sk-1},问先拿者是否有必胜策略？
普通Nim取石子游戏但加了一些限制条件，比如每次只能取S={s1,s2,s3……}，就把前驱的条件改一下就行。

Knowledge

Sprague-Grundy Function-SG函数–博弈论
博弈论也是最近新学的知识，上面是一个写得很好的博客。
简单脑补：对于公平博弈（一般是NIM游戏），我们有一个重要的工具————就是SG函数。
SG函数的定义：
必败态的sg值为0，其余态的sg值为其后继状态的sg值的mex和。
其中mex和操作（mex{a1,a2,a3,…,ar}）的含义是a1,a2,a3,…,ar中最小的没出现过的自然数。
而对于组合游戏（就是由若干个子游戏组合而成，每个子游戏之间状态独立，每次操作任选一个子游戏操作），其sg值为所有子游戏sg值的异或和。如果一个状态求得sg值为0，则为必败态，否则为必胜态。（证明略，大致是因为先手总能通过一步使sg不为0的状态变为0，而sg为0的状态只能变成sg不为0的状态，最后不能操作的状态sg也为0）而一般sg都是打表找规律，常用分析方法：(1) 等差分析(2) 等比分析(3) 特定数值位置分析(4) 奇偶位置分析。对于多组数据都不同就要暴力求，如本题。

Solution

分析：
1.可将问题转化为n个子问题，每个子问题分别为：
从一堆x颗石子中取石子，每次可取的石子数为集合S(k)中的一个数
2.分析(1)中的每个子问题，易得:SG(x)=mex(SG[(x-s[i]>0)])(k>=i>=1)
3.后面就是SG函数的应用，根据Sprague-Grundy Therem：g(G)=g(G1)^g(G2)^g(G3)^…^g(Gn)即游戏的和的SG函数值是它的所有子游戏的SG函数值的异或，即SG(G) = SG(x1)^SG(x2)^…^SG(xn),故若SG(G)=0那么必输。

Notice

memset:①比for快②#include - cstring
map复杂度加一个log，对于加入的数少的情况用，else flag数组。

Code

// <S-Nim.cpp> - 08/03/16 20:18:06

// This file is made by YJinpeng，created by XuYike's black technology automatically.

// Copyright (C) 2016 ChangJun High School, Inc.

// I don't know what this program is.

#include <iostream>

#include <vector>

#include <algorithm>

#include <cstring>

#include <cstdio>

#include <map>

#include <cstdlib>

#include <cmath>

#define MOD 1000000007

#define INF 1e9

#define EPS 1e-10

using namespace std;

typedef long long LL;

const int MAXN=;

const int MAXM=;

inline int max(int &x,int &y) {return x>y?x:y;}

inline int min(int &x,int &y) {return x<y?x:y;}

inline int getint() {

    register int w=,q=;register char ch=getchar();

    while((ch<''||ch>'')&&ch!='-')ch=getchar();

    if(ch=='-')q=,ch=getchar();

    while(ch>=''&&ch<='')w=w*+ch-'',ch=getchar();

    return q?-w:w;

}

int n,T,sg[MAXN],m,ans,s[MAXN];

inline int mex(int x){

    //map<int,bool>f;

    bool f[MAXN];

    memset(f,,sizeof(f));//fast <cstring>

    int temp;

    for(int i=;i<=n;i++){

        temp=x-s[i];

        if(temp>=){

            if(sg[temp]==-)sg[temp]=mex(temp);

            f[sg[temp]]=;

        }

    }

    for(int i=;;i++)if(!f[i])return i;

}

inline int SG(int x){

    if(sg[x]==-)sg[x]=mex(x);

    return sg[x];

}

int main()

{

    freopen("S-Nim.in","r",stdin);

    freopen("S-Nim.out","w",stdout);

    while(n=getint(),n){

        for(int i=;i<=n;i++)s[i]=getint();

        sg[]=;

        for(int i=;i<MAXN;i++)sg[i]=-;

        T=getint();

        while(T--){

            m=getint();ans=;

            while(m--)ans^=SG(getint());

            if(ans)printf("W");else printf("L");

        }

        printf("\n");

    }

    return ;

}

巴特西

【Poj2960】S-Nim & 博弈论

Position：

List

Description

Knowledge

Solution

Notice

Code

最新文章

热门文章