POJ 1082 Calendar Game 题解《挑战程序设计竞赛》

POJ 1082 Calendar Game 

翻黄历：Adam和Eve玩游戏，在1900年的1月1号到2001年的11月4号之间随机选一个日期，两人轮流增加日期，Adam先手。规定只能往此日期的下一天移动或者下个月的这一天移动（如果下个月没有这一天，则不能移动）。最终谁先移动到2001年的11月4号，谁就获胜。现给定日期，判断Adam是否有取胜策略。

4.2找出游戏的必胜策略 

推理与动态规划算法 

如果抽到最后一天肯定是必败的，那就用这个必败态往前面递推。状态按照日期先后排列，每个current状态取决于两个next状态。只要两个next状态中有一个为必败态，则Adam可以选择移动到该next状态，让Eve落败；否则Adam没有选择，只能移动到成功态，将胜利的果实拱手让给Eve。

那么只需将这102年的日期都算出来，每个日期的状态都预先算好，就可以应对题目的多case了。

#include <cstdio>
#include <algorithm>
#include <cstring>

using namespace std;

const int MAX_D = 365 * 105;
const int ds[] = { 31, 28, 31, 30, 31, 30, 31, 31, 30, 31, 30, 31 };

bool is_leap_year(int year)
{
    return year % 400 == 0 || (year % 100 != 0 && year % 4 == 0);
}

struct date
{
    int y, m, d;
    date() { }
    date(int y, int m, int d) : y(y), m(m), d(d) { }
    bool operator<(const date &other) const
    {
        return y != other.y ? y < other.y : m != other.m ? m < other.m : d < other.d;
    }
};

int D;
date days[MAX_D];
bool win[MAX_D];

void init_calendar()
{
    for (int y = 1900; y <= 2001; y++)
    {
        for (int m = 0; m < 12; m++)
        {
            for (int d = 0, ed = ds[m] + ((m == 1 && is_leap_year(y)) ? 1 : 0); d < ed; d++)
            {
                days[D++] = date(y, m, d);
            }
        }
    }
}

void solve()
{
    memset(win, true, sizeof(win));
    int start = lower_bound(days, days + D, date(2001, 10, 3)) - days;
    win[start] = false;
    for (int i = start - 1; i >= 0; --i)
    {
        win[i] = false;
        if (!win[i + 1])        // 如果两个next状态中有一个必败状态
        {
            win[i] = true;      // 则current状态为必胜状态
            continue;
        }
        else
        {
            date nxt = days[i];
            nxt.m++;
            if (nxt.m == 12)
            {
                nxt.y++;
                nxt.m = 0;
            }
            if (binary_search(days, days + D, nxt) &&
                    !win[lower_bound(days, days + D, nxt) - days])// 如果两个next状态中有一个必败状态
            {
                win[i] = true;  // 则current状态为必胜状态
            }
        }
    }
}

///////////////////////////SubMain//////////////////////////////////
int main(int argc, char *argv[])
{
#ifndef ONLINE_JUDGE
    freopen("in.txt", "r", stdin);
#endif
    init_calendar();
    solve();
    int T;
    scanf("%d", &T);
    while (T--)
    {
        int y, m, d;
        scanf("%d%d%d", &y, &m, &d);
        m--;
        d--;
        puts(win[lower_bound(days, days + D, date(y, m, d)) - days] ? "YES" : "NO");
    }
#ifndef ONLINE_JUDGE
    fclose(stdin);
#endif
    return 0;
}
///////////////////////////End Sub//////////////////////////////////

另外，看到讨论区有人给出了一个简洁的规律“月与号和为偶数的天状态为必胜，为奇数的天状态为必败。特殊情况为09.30和11.30，这两天的状态也为必胜”。花点时间也可以证明，不过这些机械工作还是交给计算机比较好。

Reference

http://d.hatena.ne.jp/komiyam/20120331/1333125295

http://blog.csdn.net/crescent__moon/article/details/18558109

 知识共享署名-非商业性使用-相同方式共享：码农场 » POJ 1082 Calendar Game 题解《挑战程序设计竞赛》