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[102][13][32];
bool leapFlag;
int month[]={31,31,28,31,30,31,30,31,31,30,31,30,31};

bool is_leapYear(int y)   //是否为闰年
{
    if(y%4==0)
    {
        if(y%400!=0)return false;
        return true;
    }
    return false;
}

bool getDayBefore()      //获取前一天的日期
{
    bool loopFlag=true;
    if(date.d>1){date.d--;return loopFlag;}
    if(date.m==3)
    {
        date.m--;
        if(leapFlag) date.d=29;
        else date.d=28;
    }else if(date.m==1)
    {
        date.y--;
        date.m=12;
        date.d=month[12];
        loopFlag=false;
    }else
    {
        date.m--;
        date.d=month[date.m];
    }
    return loopFlag;
}

bool isValidNextMonth()  //判断下个月的这天是否有效
{
    if(date.y>=101 && ((date.m==10 && date.d>4)||(date.m>10)))return false;
    if(date.d<=month[(date.m+1)%12])return true;                //将month[0]=31 便可用 %12
    if(leapFlag && date.m==1 && date.d<30)return true;
    return false;
}

void init()
{
    memset(state,0,sizeof(state));
    date.y=101;
    date.m=11;
    date.d=3;
    Date time={101,11,4};
    bool loopFlag;
    while(date.y>=0)
    {
        leapFlag=is_leapYear(date.y+1900);
        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==12)
                    {
                        if(!state[date.y+1][1][date.d])state[date.y][date.m][date.d]=true;
                    }else if(!state[date.y][date.m+1][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=0;i<n;i++)
    {
        cin>>y>>m>>d;
        if(state[y-1900][m][d])cout<<"YES"<<endl;
        else cout<<"NO"<<endl;
    }
    return 0;
}

View Code

网上还有一种超简单的方法，分析：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)%2==0||(mm==9&&dd==30)||(mm==11&&dd==30))
        puts("YES");
        else
        puts("NO");
    }
    return 0;
}

View Code