HDU1079 Calendar Game（基础博弈）-白红宇

HDU1079 Calendar Game（基础博弈）

阅读量：7228 次

发布时间：2019-06-29

本文共 1976 字，大约阅读时间需要 6 分钟。

题意：

两个人轮流走，可以走到下一天或者下个月的今天（如果有的话）

给你一个日期（>=1990.1.1）先走到2001.11.4的人胜利，问先手胜负情况

思路：

np预处理出每一天的胜负情况，如果走到的都是必胜态，当前为必败态，否则为必胜态

/* ***********************************************Author        :devil************************************************ */#include 
     
      #include 
      
       #include 
       
        #include 
        
         #include 
         
          #include 
          
           #include 
           
            #include 
            
             #include 
             #include 
              
               #include 
               
                #include 
                
                 #include 
                 
                  #include 
                  
                   #define LL long long#define rep(i,a,b) for(int i=a;i<=b;i++)#define dep(i,a,b) for(int i=a;i>=b;i--)#define ou(a) printf("%d\n",a)#define pb push_back#define pii pair
                   
                    #define mkp make_pair#define IN freopen("in.txt","r",stdin);#define OUT freopen("out.txt","w",stdout);using namespace std;const int inf=0x3f3f3f3f;const int mod=1e9+7;const int N=4e4+10;unordered_map
                    
                     mp;bool f[N];int nxt[N];bool isrun(int year){ return (year%4==0&&year%100||year%400==0);}void getnext(int &x){ int y=x/10000,m=x%10000/100,d=x%100; if(d<28) {x++;return;} if(d==28) { if(m!=2||m==2&&isrun(y)) {x++;return;} x=y*10000+301;return; } if(d==29) { if(m==2&&isrun(y)) {x=y*10000+301;return;} x++;return; } if(d==30) { if(m==1||m==3||m==5||m==7||m==8||m==10||m==12) {x++;return;} x=y*10000+(m+1)*100+1;return; } if(m<12) {x=y*10000+(m+1)*100+1;return;} x=(y+1)*10000+101;return;}int getm(int x){ if(x>20011004) return 0; int y=x/10000,m=x%10000/100,d=x%100; if(m==1&&d-isrun(y)>28) return 0; if((m==3||m==5||m==8||m==10)&&d==31) return 0; if(m==12) return x+8900; return x+100;}int main(){ int date=19000101,n=0; while(date<=20011104) { mp[date]=++n; getnext(date); } for(auto i=mp.begin();i!=mp.end();i++) nxt[mp[i->first]]=getm(i->first); f[mp[20011103]]=1; for(int i=n-1;i;i--) if(!f[i+1]||nxt[i]&&!f[mp[nxt[i]]]) f[i]=1; int t,y,m,d; scanf("%d",&t); while(t--) { scanf("%d%d%d",&y,&m,&d); y=y*10000+m*100+d; printf("%s\n",f[mp[y]]?"YES":"NO"); } return 0;}