题目分析

问题描述

Adam和Eve玩日历游戏，轮流移动日期：

1. 初始日期在1900.1.1-2001.11.4之间
2. 每次操作可以：
   • 移动到下一天（日历日期）
   • 移动到下个月的同一天（若无效则只能选第一种）
3. 移动到2001.11.4的玩家获胜
4. 超过2001.11.4则输

输入输出

• 输入：日期$Y/M/D$
• 输出：Adam是否有必胜策略（YES/NO）

解题思路

1. 博弈论分析

将问题建模为有限状态博弈：

• 每个日期对应一个游戏状态
• 终态：2001.11.4（胜态）
• 转移规则：
  • $(Y,M,D) \rightarrow (Y,M,D+1)$
  • $(Y,M,D) \rightarrow (Y+(M==12), M\%12+1, D)$（若下个月有D日）

2. 必胜策略

发现模式规律：

• 当$(M+D)$为偶数时先手必胜
• 例外情况：9.30和11.30也是必胜态

数学表达：

$$\text{必胜条件} = \begin{cases} \text{true} & \text{if } (M+D) \equiv 0 \pmod{2} \\ \text{true} & \text{if } (M,D) \in \{(9,30),(11,30)\} \\ \text{false} & \text{otherwise} \end{cases} $$

3. 算法选择

直接应用发现的模式规律：

• 计算$M+D$的奇偶性
• 检查特殊日期

数学证明

1. 终态性质：

   • 2001.11.4：$11+4=15$（奇数）是必败态

2. 状态转移：

   • 从奇数日只能转移到偶数日
   • 从偶数日可以强制转移到奇数日
   • 因此控制对手处于奇数日即可获胜

3. 例外处理：

   • 9.30和11.30可以转移到必败态

复杂度分析

• 时间复杂度：$O(1)$（直接计算）
• 空间复杂度：$O(1)$

代码实现

#include<stdio.h>
int main(void)
{
	int n,y,m,d;
	scanf("%d",&n);
	for(int i=1;i<=n;i++)
	{
		scanf("%d %d %d",&y,&m,&d);
		if((m+d)%2==0 || m==9&&d==30 || m==11&&d==30)
			printf("YES\n");
		else
			printf("NO\n");
	}
	return 0;
 }