当前位置: 代码迷 >> 综合 >> POJ - 1082 Calendar Game(博弈,记忆化搜索)
  详细解决方案

POJ - 1082 Calendar Game(博弈,记忆化搜索)

热度:102   发布时间:2023-11-25 08:01:19.0

POJ链接, POJ - 1082,

HDU链接, HDU - 1079

题意:A 和 E 玩游戏,在 1900 年的 1 月 1 号到 2001 年的 11 月 4 号之间随机选一个日期,两人轮流增加日期, A 先手。规定只能往此日期的下一天移动或者下个月的这一天移动(如果下个月没有这一天,则不能移动,例如 1 月 30 号,只能移动到 1 月 31 号,因为 2 月没有 30 号)。最终谁先移动到 2001 年的 11 月 4 号,谁就获胜。两个人都采用最优策略,问A是否能够获胜

对于这道题目,最关键的地方,倒着来找,先到达2001.11.4的获胜,那么2001.11.3为必胜态,2001.11.2为必败态,按照这样继续推下去,不难发现当月数与天数的和为奇数时为必败态,而和为偶数时为必胜态,除此之外,每天的态是由下一天和下个月的下一天的态决定的,如果这两个都是必胜态,则这一天一定为必败态,继续推的话发现闰年也是符合这个规则的,特殊的情况只有9.30号,因为10.1为必败态但10.30为必胜态,所以9.30应该为必胜态,只有这一天是不符合上面那个规律的,所以总的来说只需要单独考虑这一条件就可以了。

#include<cstdio>
int main()
{
    int t;scanf("%d",&t);while(t--){
    int y,m,d;scanf("%d%d%d",&y,&m,&d);if((m+d)%2==0) puts("YES");else if(m==9&&d==30) puts("YES");else puts("NO"); }return 0;
}
  相关解决方案