| by XianKa | No comments

【博弈】HDU 1079 Calendar Game

传送门

题意是说,给定一个日期,每个人可以轮流操作,要么将日期+1变为下一天,要么将日期变为下个月的同一天。

当下个月没有同一天的时候,只能讲日期变为下一天。

谁把日期变为2001.11.4即胜利。

是用sg函数做的。

当局面的sg>=1的时候必胜。

//#pragma GCC optimize(3)
#include<bits/stdc++.h>
using namespace std;
int gap[2020];
int ms[] = {0,31,28,31,30,31,30,31,31,30,31,30,31};
int sg[2010][13][33];
bool check(int y, int m, int d)
{
    if(y > 2001) return 0;
    else if(y == 2001 && m > 11)  return 0;
    else if(y == 2001 && m==11 && d > 4) return 0;
    return 1;
}
int getsg(int y, int m, int d)
{
    //cerr << y << ":" << m << ":" << d << endl;

    if(sg[y][m][d] != -1) return sg[y][m][d];

    int vis[4]; memset(vis, 0, sizeof vis);

    int ty,tm,td, f1, f2;
    // int ny = y, nm = m, nd = d+1;
    ty = y, tm = m, td = d + 1;
    int t = 0;
    if(m == 2) t += gap[y];
    if(td > ms[tm] + t) tm ++, td = 1;
    if(tm > 12) ty++, tm = 1;
    if(check(ty, tm, td))
        vis[getsg(ty, tm, td)] = 1;

    ty = y, tm = m+1, td = d;

    if(tm > 12) ty++, tm = 1;
    t = 0;
    if(tm == 2) t += gap[ty];
    if(td <= ms[tm] + t)
        if(check(ty, tm, td))
            vis[getsg(ty, tm, td)] = 1;

    int i; for(i = 0; i < 4; i++) if(!vis[i]) break;
    return sg[y][m][d] = i;
}
int main()
{
    memset(sg, -1, sizeof sg);
    for(int i = 1900; i <= 2001; i++)
    {
        if(i % 400 == 0 || (i % 100 != 0 && i % 4 == 0)) gap[i] = 1; 
    }    
    sg[2001][11][4] = 0;

    int T; cin >> T;
    while(T--)
    {
        int y, m, d;
        scanf("%d%d%d", &y, &m, &d);
        int ans = getsg(y, m, d);
        //cout << ans << endl;
        if(ans >= 1) cout << "YES" << endl;
        else cout << "NO" << endl;
    }
}

实际上可以再优化一下代码。因为每个局面最多只有两个后继局面。当后继局面有必败态的时候当前局面为必胜态。(进而可以发现大部分情况下,m+d是偶数必胜,但要特判9月30和11月30)

//#pragma GCC optimize(3)
#include<bits/stdc++.h>
using namespace std;
int gap[2020];
int ms[] = {0,31,28,31,30,31,30,31,31,30,31,30,31};
int sg[2010][13][33];
int getsg(int y, int m, int d)
{
    //cerr << y << ":" << m << ":" << d << endl;

    if(sg[y][m][d] != -1) return sg[y][m][d];

    if(y > 2001)return sg[y][m][d] = 1;
    else if(y == 2001 && m > 11)  return sg[y][m][d] = 1;
    else if(y == 2001 && m==11 && d > 4)return sg[y][m][d] = 1;
    int ty,tm,td;
    // int ny = y, nm = m, nd = d+1;
    ty = y, tm = m, td = d + 1;
    int t = 0;
    if(m == 2) t += gap[y];
    if(td > ms[tm] + t) tm ++, td = 1;
    if(tm > 12) ty++, tm = 1;
    if(getsg(ty, tm, td) == 0) return sg[y][m][d] = 1;

    ty = y, tm = m+1, td = d;

    if(tm > 12) ty++, tm = 1;
    t = 0;
    if(tm == 2) t += gap[ty];
    if(td <= ms[tm] + t)
        if(getsg(ty, tm, td) == 0) return sg[y][m][d] = 1;

    return sg[y][m][d] = 0;
}
int main()
{
    memset(sg, -1, sizeof sg);
    for(int i = 1900; i <= 2001; i++)
    {
        if(i % 400 == 0 || (i % 100 != 0 && i % 4 == 0)) gap[i] = 1; 
    }    
    sg[2001][11][4] = 0;
    // for(int i = 1900; i <= 2001; i++) gap[i] += gap[i - 1];
    // for(int i = 1; i <= 12; i++) ms[i] += ms[i - 1];
    // int totd = 2000 * 365 + 4 + 25;
    int T; cin >> T;
    while(T--)
    {
        int y, m, d;
        scanf("%d%d%d", &y, &m, &d);
        int ans = getsg(y, m, d);
        //cout << ans << endl;
        if(ans % 2 == 1) cout << "YES" << endl;
        else cout << "NO" << endl;
    }
}

发表评论