•  
  • Archives for SG函数 (6)

【POJ1067】取石子游戏 ||【NYOJ161】(威佐夫博奕(Wythoff Game))

Categories: 数据结构和算法
Comments: No Comments
Published on: 2011 年 04 月 11 日

威佐夫博奕(Wythoff Game):有两堆各若干个物品,两个人轮流从某一堆或同
时从两堆中取同样多的物品,规定每次至少取一个,多者不限,最后取光者得胜。

这种情况下是颇为复杂的。我们用(ak,bk)(ak ≤ bk ,k=0,1,2,…,n)表示
两堆物品的数量并称其为局势,如果甲面对(0,0),那么甲已经输了,这种局势我们
称为奇异局势。前几个奇异局势是:(0,0)、(1,2)、(3,5)、(4,7)、(6,
10)、(8,13)、(9,15)、(11,18)、(12,20)。
(more...)

【POJ1704】Georgia and Bob (staircase Nem 变形题)

Categories: 数据结构和算法
Comments: No Comments
Published on: 2011 年 04 月 11 日

poj的discuss里边说的题解十分到位:

这道题目可以对应一个Staircase NIM问题,只需要把两个棋子之间的间隔以及第一个棋子与左边界的间隔看作一堆石子,
则一次操作一定是从一对石子中取出若干移到右边相邻的一堆中。这就是标准的Staircase-NIM问题。
具体的做法是:将所有奇数位置上的石子个数做XOR,结果为0说明BOB胜,否则说明GEORGIA胜,Not Sure显然是不会出现的。 (more...)

【POJ2975】Nim (博弈)

Categories: 数据结构和算法
Comments: No Comments
Published on: 2011 年 04 月 11 日

n堆石子,然后问如果必胜的话有多少种移动方法(一步)。
因为答案最多只有n,令ans=a1^a2^...^an,如果需要构造出异或值为0的数,
而且由于只能操作一堆石子,所以对于某堆石子ai,现在对于ans^ai,就是除了ai以外其他的石子
的异或值,如果ans^ai< =ai,那么对于ai的话,是可以减小到ans^ai的值,然后使得所有数 的异或值为0,也即转移到了必败态。 (more...)

博弈论总结

Categories: 数据结构和算法
Comments: No Comments
Published on: 2011 年 04 月 11 日

以下是我从网上收集的关于组合博弈的资料汇总:

有一种很有意思的游戏,就是有物体若干堆,可以是火柴棍或是围棋子等等均可。两个
人轮流从堆中取物体若干,规定最后取光物体者取胜。这是我国民间很古老的一个游戏
,别看这游戏极其简单,却蕴含着深刻的数学原理。下面我们来分析一下要如何才能够
取胜。
(more...)

【HDU1536】S-Nim (博弈,SG函数)

Categories: 数据结构和算法
Comments: No Comments
Published on: 2011 年 04 月 11 日
#include<cstdio>    
#include<algorithm>    
using namespace std;    
#define N 100+10    
int knum,mnum,lnum;    
int ans[N],si[N],hi[N],sg[10010];    
int mex(int x)//求x的sg值(可作为模版应用)  
{    
    if(sg[x]!=-1) return sg[x];    
    bool vis[N];  
    memset(vis,false,sizeof(vis));    
    for(int i=0;i<knum;i++)    
    {    
        int temp=x-si[i];    
        if(temp<0) break;    
        sg[temp]=mex(temp);    
        vis[sg[temp]]=true;    
    }    
    for(int i=0;;i++)    
    {    
        if(!vis[i])    
        {    
            sg[x]=i; break;    
        }    
    }    
    return sg[x];    
}    
int main()    
{    
    while(scanf("%d",&knum) && knum)    
    {    
        for(int i=0;i<knum;i++) scanf("%d",&si[i]);    
        sort(si,si+knum);    
        memset(sg,-1,sizeof(sg));    
        sg[0]=0;    
        memset(ans,0,sizeof(ans));    
        scanf("%d",&mnum);    
        for(int i=0;i<mnum;i++)    
        {    
            scanf("%d",&lnum);    
            for(int j=0;j<lnum;j++)    
            {    
                scanf("%d",&hi[i]); ans[i]^=mex(hi[i]);//尼姆博弈  
            }    
        }    
        for(int i=0;i<mnum;i++)    
        {    
            if(ans[i]==0) printf("L");    
            else printf("W");    
        }    
        printf("\n");    
    }    
    return 0;    
}  

【HDU1097】John

Categories: 数据结构和算法
Comments: No Comments
Published on: 2011 年 04 月 11 日

有SG 定理:
对于任意的一个 Anti-SG 游戏,如果我们规定当局面中所有单一游戏的 SG 值为 0 时游戏
结束,则先手必胜当且仅当以下两个条件满足任意一个:
(1)游戏的 SG 函数不为 0,且游戏中某个单一游戏的 SG 函数大于1。
(2)游戏的 SG 函数为 0,且游戏中没有单一游戏的 SG 函数大于 1。 (more...)

page 1 of 1
文章归档
日历
2017年十一月
« 七    
 1234
567891011
12131415161718
19202122232425
2627282930  
标签云
sina weibo
我的广告可能就是你的信息

Welcome , today is 星期日, 2017 年 11 月 19 日