poj1082 Calendar Game （博弈）

题意是：Adam和Eve两人做游戏，开始给出一个日期，截止日期是2011.11.4，游戏规则如下：

每个人只能将天数增加一天或者将月份增加一天。如果下个月没有这一天，那么只能增加天数。

游戏胜利定义为：先到截止日期的为胜。

每次都是Adam先开始。

分析：

典型的博弈论，算法思路为在初始化的过程中便获得2001.11.4到1990.1.1期间所有日期的胜败情况。对于y-m-d日期，若其下一天和下一月中有一个为必败情况，则今天为必胜（下一步是对手的状态，对手为败，我为胜，所有我优先选择样对手输的状态）。若两者均为必胜，则今天为必败（无论我那个选择，对手都是胜利，那我就凉了）。主要难度在于前一日（getDayBefore）和后一月（isValidNextMonth）日期的判定，要注意闰年情况的特殊性。

#include <iostream>

#include<string.h>

using namespace std;

struct Date

{

    int y,m,d;

}date;

bool state[][][];

bool leapFlag;

int month[]={,,,,,,,,,,,,};

bool is_leapYear(int y)   //是否为闰年

{

    if(y%==)

    {

        if(y%!=)return false;

        return true;

    }

    return false;

}

bool getDayBefore()      //获取前一天的日期

{

    bool loopFlag=true;

    if(date.d>){date.d--;return loopFlag;}

    if(date.m==)

    {

        date.m--;

        if(leapFlag) date.d=;

        else date.d=;

    }else if(date.m==)

    {

        date.y--;

        date.m=;

        date.d=month[];

        loopFlag=false;

    }else

    {

        date.m--;

        date.d=month[date.m];

    }

    return loopFlag;

}

bool isValidNextMonth()  //判断下个月的这天是否有效

{

    if(date.y>= && ((date.m== && date.d>)||(date.m>)))return false;

    if(date.d<=month[(date.m+)%])return true;                //将month[0]=31 便可用 %12

    if(leapFlag && date.m== && date.d<)return true;

    return false;

}

void init()

{

    memset(state,,sizeof(state));

    date.y=;

    date.m=;

    date.d=;

    Date time={,,};

    bool loopFlag;

    while(date.y>=)

    {

        leapFlag=is_leapYear(date.y+);

        loopFlag=true;

        while(loopFlag)

        {

            if(!state[time.y][time.m][time.d])

            {

                state[date.y][date.m][date.d]=true;

            }else

            {

                if(isValidNextMonth())

                {

                    if(date.m==)

                    {

                        if(!state[date.y+][][date.d])state[date.y][date.m][date.d]=true;

                    }else if(!state[date.y][date.m+][date.d])state[date.y][date.m][date.d]=true;

                }

            }

            time=date;

            loopFlag=getDayBefore();

        }

    }

}

int main()

{

    int i,n;

    int y,m,d;

    cin>>n;

    init();

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

    {

        cin>>y>>m>>d;

        if(state[y-][m][d])cout<<"YES"<<endl;

        else cout<<"NO"<<endl;

    }

    return ;

}

网上还有一种超简单的方法，分析：2种操作，日+1，或月+1，（除了几个特殊日期外）均能改变月+日的奇偶性，而目标11.4，月+日为奇数，所以只要起始日期的月+日为偶数,Adam,the first mover,就可能赢。而两个特殊日期（9.30，11.30），尽管月+日为奇数，但下一步仍然可以得到奇数，这是一种大局的看法，尽然目标11+4，是奇数，而加月或日都可以改变奇偶性，那我只要保证让对手达到偶的性质，那肯定不能WIN ; 有个特殊的月份9.30和11.30

虽然都是奇数，但是他的下一步也是奇数，故满足

#include<stdio.h>

using namespace std;

int main()

{

    int yy,mm,dd;

    int t;

    scanf("%d",&t);

    while(t--)

    {

       scanf("%d%d%d",&yy,&mm,&dd);

        if((mm+dd)%==||(mm==&&dd==)||(mm==&&dd==))

        puts("YES");

        else

        puts("NO");

    }

    return ;

}

巴特西

poj1082 Calendar Game （博弈）

最新文章

热门文章