Vijos 1004 — 伊甸园日历游戏

描述

Adam和Eve玩一个游戏,他们先从1900.1.1到2001.11.4这个日期之间随意抽取一个日期出来。然后他们轮流对这个日期进行操作:

1 : 把日期的天数加1,例如1900.1.1变到1900.1.2
2 : 把月份加1,例如:1900.1.1变到1900.2.1

其中如果天数超过应有天数则日期变更到下个月的第1天。月份超过12则变到下一年的1月。而且进行操作二的时候,如果有这样的日期:1900.1.31,则变成了1900.2.31,这样的操作是非法的,我们不允许这样做。而且所有的操作均要考虑历法和闰年的规定。

谁先将日期变到2001.11.4谁就赢了。
每次游戏都是Adam先操作,问他有没有必胜策略?

题目链接

https://vijos.org/p/1004

输入格式

一个测试点。多组数据。
第一行为数据组数。
接下来一行X Y Z表示X年Y月Z日

输出格式

输出“YES”or“NO”表示亚当是否有必胜策略。

样例输入

3
2001 11 3
2001 11 2
2001 10 3

样例输出

YES
NO
NO

提示

建议先把所有情况都算出来^_^

题目分析

动态规划(记忆化搜索)

首先,我们将某一天存在必胜策略称为这一天必胜。
对于某一天 X ,下一步有两种情况,月份加一或者日期加一。如果下一步的两种情况都是必胜的,那么 X 不必胜,因为无论转移到哪种情况,对手都是有必胜的策略的;如果两种情况至少有一种是不必胜的,那么 X 必胜,因为可以转移到不必胜的情况,让对手失败。
当然,如果月份加一是不合法的,下一步就只能令日期加一。这时,如果日期加一必胜,则 X 不必胜;反之则 X 必胜。
X 是否必胜,取决于 X+1 天和 X+1 月是否必胜。
因此,只要从 2001.11.4 往前推,将所有日期的答案都计算出来即可。临界条件是:2001.11.4 是必败的;大于 2001.11.4 的日期都是必胜的,因为谁先转移到超过 2001.11.4 的日期谁就失败,相当于谁当前是大于 2001.11.4 的日期,谁就必胜。

找规律

设年 x,月 y,日 z
当 (y+z)%2 == 0 时,必胜;反之必败。
特殊情况:9月30日和11月30日,必胜。
对于这个规律,网上很多大牛进行了分析。不过我并没看懂。
或许是我太菜了。
当然,先按照上一种方法计算所有答案,然后输出,也能找出这个规律。
题目本意应该就是让记忆化搜索。

AC代码1

#include <bits/stdc++.h>
using namespace std;

int ans[3000][13][32] = {0};
int num[] = {31, 31, 28, 31, 30, 31, 30, 31, 31, 30, 31, 30, 31}; //每月的天数,0月份和12月份一样,方便程序
int x2, y2, z2;

void convert(int x, int y, int z) //将xyz转化成正常的年月日并保存在变量x2 y2 z2中
{
    x2 = x, y2 = y, z2 = z;
    if (z2 == 0) //日期减一的情况
    {
        if (!(((x2 % 4 == 0 && x2 % 100 != 0) || (x2 % 400 == 0)) && y2 == 3 && z2 == 0)) //不是闰年3月0日
        {
            y2 = y2 - 1;
            if (y2 == 0)
            {
                x2--;
                y2 = 12;
            }
            z2 = num[y2];
        }
        else
        {
            y2 = 2;
            z2 = 29;
        }
    }
    if (!(((x2 % 4 == 0 && x2 % 100 != 0) || (x2 % 400 == 0)) && y2 == 2 && z2 == 29)) //不是闰年2月29日
    {
        if (z2 > num[y2])
        {
            y2 = y2 + 1;
            z2 = 1;
        }
    }
    if (y2 == 13)
    {
        y2 = 1;
        x2 = x2 + 1;
    }
}

int f(int x, int y, int z) //返回是否必胜,1为必胜,-1为不必胜
{
    if (x > 2001 || (x == 2001 && y > 11) || (x == 2001 && y == 11 && z > 4)) //超过 2001.11.4 则返回1,因为谁先出界谁就输
        return 1;
    if (x == 2001 && y == 11 && z == 4)
        return -1;

    int t1, t2; //两种转换的结果

    //日期加一
    convert(x, y, z + 1);
    t1 = ans[x2][y2][z2];

    //月份加一,不能用convert函数,因为不是每个月份加1都是合法的
    y++;
    if (y == 13)
    {
        x++;
        y = 1;
    }
    x2 = x, y2 = y, z2 = z;
    t2 = ans[x2][y2][z2]; //如果日期不合法则t2=0

    if (t1 == 1 && t2 == 1)
        return -1;
    if (t1 == 1 && t2 == 0) // t2等于0且t1==1,此时日期是不合法的。
        return -1;
    return 1;
}

int main()
{
    int t, x, y, z;
    x = 2001, y = 12, z = 4; //从2001年12月开始搜索,而不是2001年
    while (!(x == 1899 && y == 12 && z == 31))
    {
        ans[x][y][z] = f(x, y, z);
        convert(x, y, z - 1); //日期减一
        x = x2, y = y2, z = z2;
    }
    cin >> t;
    while (t--)
    {
        cin >> x >> y >> z;
        if (ans[x][y][z] == 1)
            cout << "YES" << endl;
        else
            cout << "NO" << endl;
    }
    return 0;
}

AC代码2

#include <bits/stdc++.h>
using namespace std;

int main()
{
    int t;
    cin >> t;
    while (t--)
    {
        int x, y, z;
        cin >> x >> y >> z;
        if ((y == 9 && z == 30) || (y == 11 && z == 30))//特殊情况
            cout << "YES" << endl;
        else if ((y + z) % 2 == 0)
            cout << "YES" << endl;
        else
            cout << "NO" << endl;
    }
    return 0;
}

发表评论

电子邮件地址不会被公开。 必填项已用*标注

开始在上面输入您的搜索词,然后按回车进行搜索。按ESC取消。

返回顶部