2024河南萌新联赛第五场 A日历游戏(SG函数)

2024-08-23 20:44

本文主要是介绍2024河南萌新联赛第五场 A日历游戏(SG函数),希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!

题目链接

SG函数讲解


思路:

两个人对弈,然后还不满足一些常见的博弈模型,直接上SG函数。简单总结一下:

博弈论里的局面,表示的是某个人在做出决策前面临的一个情形,必胜与必败态指的就是这个人在某个局面下做出最优选择能否获胜。

显然游戏结束时是必败态,因为这时候面临局面的人还没有做出决策就比赛结束了, 说明对方在上一回合做出决定后就已经获胜了。必胜态必定存在一个必败态,必败态后面全为必胜态,因为我们肯定要把必败态留给对方,如果能做到,那么当前状态就是必胜态,因此必胜态后面一定有一个必败态。同理,如果做不到,说明当前状态无论怎么选,都一定会把必胜态留给对手, 当前状态就是必败态,因此必败态后面全为必胜态。

m e x ( S ) mex(S) mex(S) 运算表示在一个自然数集合 S S S 中取出被包含在 S S S 中的最小的自然数,比如 m e x ( { 1 , 2 , 3 } ) = 0 , m e x ( { 0 , 1 , 3 } ) = 2 mex(\{1,2,3\})=0,mex(\{0,1,3\})=2 mex({1,2,3})=0,mex({0,1,3})=2。SG函数的函数值是将后继所有局面的SG函数值做 m e x mex mex 运算得到的 。必败态SG函数值为 0 0 0,必胜态SG函数非 0 0 0。对于同时进行的多个局面(也就是同时面临多个局面,每次只能选一个局面进行操作,最后要求所有局面都结束才算游戏结束),SG值等于这几个局面的SG函数值做异或运算(证明和 N I M NIM NIM 游戏有关)。


在这个题里,可以从后向前递推SG函数值,也可以从前往后记忆化搜索,后者稍微好写一点。在dfs的时候注意优先月份向后搜索,这样很快就能搜到结束状态并返回,从而释放空间,要不然会爆空间。

code:

#include <iostream>
#include <cstdio>
#include <set>
#include <vector>
using namespace std;vector<int> month{0,31,28,31,30,31,30,31,31,30,31,30,31};bool vis[30][20][40];
int win[30][20][40];
int SG(int y,int m,int d){if(y==24 && m==8 && d==1)return 0;//必败局面 if(vis[y][m][d])return win[y][m][d];else vis[y][m][d]=true;vector<int> mon=month;set<int> sg;if(y%4==0)mon[2]++;//	printf("%d %d %d\n",y,m,d);if(!(y==24 && m==7 && d>1) && d<=mon[m%12+1]){sg.insert(SG(y+(m==12),m%12+1,d));}if(d+1<=mon[m])sg.insert(SG(y,m,d+1));else if(m+1<=12)sg.insert(SG(y,m+1,1));else sg.insert(SG(y+1,1,1));for(int i=0;;i++)if(sg.find(i)==sg.end())return win[y][m][d]=i;
}int T,x,y,z;int main(){SG(0,1,1);cin>>T;while(T--){cin>>x>>y>>z;x-=2000;if(SG(x,y,z)==0)cout<<"NO\n";else cout<<"YES\n";}return 0;
}

这篇关于2024河南萌新联赛第五场 A日历游戏(SG函数)的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!



http://www.chinasem.cn/article/1100451

相关文章

shell编程之函数与数组的使用详解

《shell编程之函数与数组的使用详解》:本文主要介绍shell编程之函数与数组的使用,具有很好的参考价值,希望对大家有所帮助,如有错误或未考虑完全的地方,望不吝赐教... 目录shell函数函数的用法俩个数求和系统资源监控并报警函数函数变量的作用范围函数的参数递归函数shell数组获取数组的长度读取某下的

MySQL高级查询之JOIN、子查询、窗口函数实际案例

《MySQL高级查询之JOIN、子查询、窗口函数实际案例》:本文主要介绍MySQL高级查询之JOIN、子查询、窗口函数实际案例的相关资料,JOIN用于多表关联查询,子查询用于数据筛选和过滤,窗口函... 目录前言1. JOIN(连接查询)1.1 内连接(INNER JOIN)1.2 左连接(LEFT JOI

MySQL中FIND_IN_SET函数与INSTR函数用法解析

《MySQL中FIND_IN_SET函数与INSTR函数用法解析》:本文主要介绍MySQL中FIND_IN_SET函数与INSTR函数用法解析,本文通过实例代码给大家介绍的非常详细,感兴趣的朋友一... 目录一、功能定义与语法1、FIND_IN_SET函数2、INSTR函数二、本质区别对比三、实际场景案例分

C++ Sort函数使用场景分析

《C++Sort函数使用场景分析》sort函数是algorithm库下的一个函数,sort函数是不稳定的,即大小相同的元素在排序后相对顺序可能发生改变,如果某些场景需要保持相同元素间的相对顺序,可使... 目录C++ Sort函数详解一、sort函数调用的两种方式二、sort函数使用场景三、sort函数排序

C语言函数递归实际应用举例详解

《C语言函数递归实际应用举例详解》程序调用自身的编程技巧称为递归,递归做为一种算法在程序设计语言中广泛应用,:本文主要介绍C语言函数递归实际应用举例的相关资料,文中通过代码介绍的非常详细,需要的朋... 目录前言一、递归的概念与思想二、递归的限制条件 三、递归的实际应用举例(一)求 n 的阶乘(二)顺序打印

C/C++错误信息处理的常见方法及函数

《C/C++错误信息处理的常见方法及函数》C/C++是两种广泛使用的编程语言,特别是在系统编程、嵌入式开发以及高性能计算领域,:本文主要介绍C/C++错误信息处理的常见方法及函数,文中通过代码介绍... 目录前言1. errno 和 perror()示例:2. strerror()示例:3. perror(

Kotlin 作用域函数apply、let、run、with、also使用指南

《Kotlin作用域函数apply、let、run、with、also使用指南》在Kotlin开发中,作用域函数(ScopeFunctions)是一组能让代码更简洁、更函数式的高阶函数,本文将... 目录一、引言:为什么需要作用域函数?二、作用域函China编程数详解1. apply:对象配置的 “流式构建器”最

Android Kotlin 高阶函数详解及其在协程中的应用小结

《AndroidKotlin高阶函数详解及其在协程中的应用小结》高阶函数是Kotlin中的一个重要特性,它能够将函数作为一等公民(First-ClassCitizen),使得代码更加简洁、灵活和可... 目录1. 引言2. 什么是高阶函数?3. 高阶函数的基础用法3.1 传递函数作为参数3.2 Lambda

C++中::SHCreateDirectoryEx函数使用方法

《C++中::SHCreateDirectoryEx函数使用方法》::SHCreateDirectoryEx用于创建多级目录,类似于mkdir-p命令,本文主要介绍了C++中::SHCreateDir... 目录1. 函数原型与依赖项2. 基本使用示例示例 1:创建单层目录示例 2:创建多级目录3. 关键注

C++中函数模板与类模板的简单使用及区别介绍

《C++中函数模板与类模板的简单使用及区别介绍》这篇文章介绍了C++中的模板机制,包括函数模板和类模板的概念、语法和实际应用,函数模板通过类型参数实现泛型操作,而类模板允许创建可处理多种数据类型的类,... 目录一、函数模板定义语法真实示例二、类模板三、关键区别四、注意事项 ‌在C++中,模板是实现泛型编程