hdu1404,hdu1517 (博弈论入门)

SG定理：

根据Sprague-Grundy定理（SG定理），对于某些博弈论问题可以这样思考：

首先可以确定一个必败状态（记为P）或必胜状态（记为N）；

这样一来，若某一状态X若可以直接转移到P，则可以确定X为必胜状态；

若某一状态X 只能转移到N，则可以确定X为必败状态。

以此通过递推可确定先手必胜或必败。

代码：

#include<iostream>

#include<cstring>

#include<cmath>

#include<cstdlib>

#include<cstdio>

using namespace std;

const int maxn = 1e7+6;

bool sg[maxn];

int intlen(int x)

{

    for (int i=6;i>0;i--)

    {

        int k=pow(10,(i-1));

        if (x / k) return i;

    }

}

void GetSG(int x)

{

    //cout<<x<<endl;

    int len=intlen(x);

    for(int i=0; i<len; ++i)

    {

        int k=pow(10, i);

        int q=x/k%10;

        int y=x;

        for(int j=q; j<9; ++j)

        {

            y+=k;

            sg[y]=true;//可一步到达必败状态则为必胜

        }

    }

    int y=x, k=1;

    while(len<6)

    {

        y*=10;

        for(int i=0; i<k; ++i)

            sg[y+i]=true;

        k*=10;

        len++;

    }

}

int main()

{

    memset(sg, false, sizeof(sg));

    sg[0]=true;

    for(int i=1; i<1000000; ++i)

        if(!sg[i])//必败则进入

            GetSG(i);

    char n[10];

    while(gets(n))

    {

        if(n[0]=='0')

        {

            puts("Yes");

            continue;

        }

        int m=atoi(n);

        if(sg[m]) puts("Yes");

        else puts("No");

    }

    return 0;

}

题二：hdu1404

代码：

#include<iostream>

#include<cstdio>

#include<cmath>

using namespace std;

int main()

{

    long long n;

    while(cin>>n)

    {

        int x=0;

        for(; n>1; ++x)

        {

            if(x&1)

                n = ceil(n*1.0/2);

            else

                n = ceil(n*1.0/9);

        }

        if(x&1) puts("Stan wins.");

        else puts("Ollie wins.");

    }

    return 0;

}

巴特西

hdu1404,hdu1517 (博弈论入门)

最新文章

热门文章