萌新5:日历游戏(博弈论,递推找规律)
题目描述
Alice 和 Bob 在玩一个游戏,他们先从 2000.1.1 到 2024.8.1 这个日期之间(不包括2024.8.1)随意抽取一个日期出来。然后他们轮流对这个日期进行操作:
-
把日期的天数加 1,例如:2000.1.1 变到 2000.1.2
-
把月份加 1,例如:2000.1.1 变到 2000.2.1
其中如果天数超过应有天数则日期变更到下个月的第 1 天。月份超过 12 则变到下一年的1月。而且进行操作2的时候,如果有这样的日期:2000.1.31,则变成了 2000.2.31,这样的操作是非法的,我们不允许这样做。
所有的操作均要考虑历法和闰年的规定。
谁先将日期变到 2024.8.1 谁就赢了。如果超越了指定日期不算获胜。
每次游戏都是 Alice 先操作,问他有没有必胜策略?
输入描述:
第一行一个整数 T,为数据组数(1<=T<=1000)。
接下来一行 X,Y,Z 表示 X 年 Y 月 Z 日。
输出描述:
输出 YES 或者 NO 表示 Alice 是否有必胜策略。
示例1
输入
复制3 2001 11 3 2001 11 2 2001 10 3
3 2001 11 3 2001 11 2 2001 10 3
输出
复制YES NO NO
YES NO NO
做法
首先他要到8月1号,那说明 7月31是一定行的 ,然后7月1号也一定行的。然后我们发现7月29只要我先+1变成7月30,那后手就一定能变成7月31,到先手A时又是7月31了。所以这样子推下去 我们发现就是隔两天就一定能推成前面那个点。然后6月30 ,我先手变成7月30 ,他后手就必须变成7月31。然后就发现一个规律 :月份+日期是偶数是必胜态。还有润年 ,我们单独考虑2月29发现他先手不管怎么操作都只能变成3.1或3.29,也满足偶数是必胜态的规律。但有一些特殊情况,比如11月30 我先手变成12月1号就可以必胜态,9月30同理。
#include<bits/stdc++.h>
using namespace std;
int t;
int x,y,z;
int main(){
scanf("%d",&t);
while(t--){
scanf("%d%d%d",&x,&y,&z);
if((z+y)%2==0) cout<<"YES"<<endl;
else if(y==11&&z==30) cout<<"YES"<<endl;
else if(y==9&&z==30) cout<<"YES"<<endl;
else cout<<"NO"<<endl;
}
}
我之前还在想,我后手推到2024年7月30发现赢不了,我直接让他推到2024年8月30不就好了,那样谁都赢不了。不过这么做就没有什么意义了,也比不出谁赢谁输。