本文主要是介绍poj 1082 / hdu 1079 Calendar Game,希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!
题意:从一个日期开始,轮流改变时间,可以变为下一天或者是同一年的下一个月的当天。先到2001年11月4日的获胜。
基础博弈问题
任意能到达必败状态的位置为必胜状态,倒着递推一下。
#include<iostream>
#include<cstdio>
#include<cmath>
#include<algorithm>
#include<cstring>
#include<queue>
using namespace std;
int dp[120][15][35];
struct node{int y, m, d;
};
node get_preday(node date){if(date.m ==1 &&date.d==1){date.y--;date.m=12;date.d=31;}else if(date.d==1){if((date.m%2==0&&date.m<9)||(date.m%2==1&&date.m>=9))date.d = 31;else if(date.m!=3)date.d = 30;else if(((date.y+1900)%4==0&&(date.y+1900)%100!=0)||((date.y+1900)%400==0))date.d = 29;else date.d = 28;date.m--;}else date.d--;return date;
}int get_monthday(node date){if((date.m%2==1&&date.m<8)||(date.m%2==0&&date.m>=8))return 31;else if(date.m!=2)return 30;else if(((date.y+1900)%4==0&&(date.y+1900)%100!=0)||((date.y+1900)%400==0))return 29;else return 28;
}void solve(){memset(dp, -1, sizeof(dp));dp[101][11][4]=0;node head, next;head.y=101;head.m=11;head.d=4;next=get_preday(head);while(next.y>=0){node tmp=next;tmp.m++;if(next.m!=12&&next.d<=get_monthday(tmp)&&dp[tmp.y][tmp.m][tmp.d]==0)dp[next.y][next.m][next.d]=1;else if(dp[head.y][head.m][head.d]==0)dp[next.y][next.m][next.d]=1;else dp[next.y][next.m][next.d]=0;head=next;next=get_preday(next);}
}int main(){//freopen("1.txt", "r", stdin);int T, y, m ,d;solve();scanf("%d", &T);while(T--){scanf("%d%d%d", &y, &m, &d);if(dp[y-1900][m][d])printf("YES\n");else printf("NO\n");}return 0;
}
找规律的结论:月与日同奇偶或9月30、11月30为必胜状态
#include<iostream>
#include<cstdio>
int main(){int T, y, m, d;scanf("%d", &T);while(T--){scanf("%d%d%d", &y, &m, &d);!((m^d)&1)||d==30&&(m==9||m==11)?printf("YES\n"):printf("NO\n");}return 0;
}
这篇关于poj 1082 / hdu 1079 Calendar Game的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!