题解 | #日历游戏#

一个最无脑直给的暴力计算 SG 函数解法，每个日期向其合法的前驱日期连边，递推计算所有日期的 SG 函数即可。赛时没敢交，发现能过~

from datetime import datetime, timedelta

start = datetime(2000, 1, 1)
end = datetime(2024, 8, 1)
tot = (end - start).days + 1

def date_to_int(date):
    return (date - start).days

def int_to_date(value):
    return start + timedelta(days=value)

def is_valid_date(year, month, day):
    try:
        date = datetime(year, month, day)
        if start <= date <= end: return True
        return False
    except:
        return False

def MEX(H):
    i = 0
    while True:
        if i not in H:
            return i
        i += 1

def cal_SG():

    g = [[] for _ in range(tot)]
    in_deg = [0] * tot

    for i in range(1, tot):
        cur = int_to_date(i)
        cur_y, cur_m, cur_d = cur.year, cur.month, cur.day
        # 减去一天
        pre1 = cur - timedelta(days=1)
        if pre1 >= start:
            pre1_int = date_to_int(pre1)
            g[i].append(pre1_int)
            in_deg[pre1_int] += 1
        # 减去一月
        pre2_y, pre2_m, pre2_d = cur_y, cur_m - 1, cur_d
        if pre2_m < 1:
            pre2_m = 12
            pre2_y = cur_y - 1
        if is_valid_date(pre2_y, pre2_m, pre2_d):
            pre2 = datetime(pre2_y, pre2_m, pre2_d)
            pre2_int = date_to_int(pre2)
            g[i].append(pre2_int)
            in_deg[pre2_int] += 1
            
    # 从最终状态开始，递推计算 SG 函数
    sg = [0] * tot
    sg_set = defaultdict(set)
    q = deque([tot - 1])
    
    while q:
        node = q.popleft()
        for pre in g[node]:
            sg_set[pre].add(sg[node])
            in_deg[pre] -= 1
            if in_deg[pre] == 0:
                sg[pre] = MEX(sg_set[pre])
                q.append(pre)

    return sg

if __name__ == '__main__':
    # 预处理 SG 函数
    sg = cal_SG()
    T = ii()
    for _ in range(T):
        y, m, d = mii()
        v = sg[date_to_int(datetime(y, m, d))]
        # 当 SG 函数不为 0 时有必胜策略
        if v != 0:
            print("YES")
        else:
            print("NO")