C++ 数论相关题目,博弈论,SG函数,集合-Nim游戏

2024-01-31 23:12

本文主要是介绍C++ 数论相关题目,博弈论,SG函数,集合-Nim游戏,希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!

给定 n
堆石子以及一个由 k
个不同正整数构成的数字集合 S

现在有两位玩家轮流操作,每次操作可以从任意一堆石子中拿取石子,每次拿取的石子数量必须包含于集合 S
,最后无法进行操作的人视为失败。

问如果两人都采用最优策略,先手是否必胜。

输入格式
第一行包含整数 k
,表示数字集合 S
中数字的个数。

第二行包含 k
个整数,其中第 i
个整数表示数字集合 S
中的第 i
个数 si

第三行包含整数 n

第四行包含 n
个整数,其中第 i
个整数表示第 i
堆石子的数量 hi

输出格式
如果先手方必胜,则输出 Yes。

否则,输出 No。

数据范围
1≤n,k≤100
,
1≤si,hi≤10000
输入样例:
2
2 5
3
2 4 7
输出样例:
Yes

SG函数:表示当前状态所不能到达状态中最小的自然数。
必胜状态:SG不等于0;
必败状态:SG等于0。
在这里插入图片描述
如果有多个图,将每个初始的SG值异或,等于0必败,不等于0必胜。
在这里插入图片描述

#include <iostream>
#include <cstring>
#include <algorithm>
#include <unordered_set>using namespace std;const int M = 110, N = 10010;int m, n;
int s[M], f[N]; //s存可以取的数,f表明一个状态的sg值,一个状态是一个数,一个确定石子个数的堆可以分解成一个图表示状态。int sg(int x)
{if(f[x] != -1) return f[x]; //避免重复计算,如果x状态算过的话,就直接返回这个状态的sg值unordered_set<int> S;//存能到达的状态的sg值。for(int i = 0; i < m; i ++ ) //遍历每一个图(堆,石子堆)if(x >= s[i])S.insert(sg(x - s[i]));for(int i = 0; ; i ++ )if(!S.count(i)) //找到最小的不存在的状态自然数,说明当前状态的sg值就是i这个数return f[x] = i;}int main ()
{cin>>m;for(int i = 0; i < m; i ++ ) cin>>s[i];cin>>n;memset(f, -1, sizeof f);int res = 0;while(n -- ){int x;cin>>x;res ^= sg(x);}if(res) puts("Yes");else puts("No");return 0;
}

这篇关于C++ 数论相关题目,博弈论,SG函数,集合-Nim游戏的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!



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

相关文章

java中BigDecimal里面的subtract函数介绍及实现方法

《java中BigDecimal里面的subtract函数介绍及实现方法》在Java中实现减法操作需要根据数据类型选择不同方法,主要分为数值型减法和字符串减法两种场景,本文给大家介绍java中BigD... 目录Java中BigDecimal里面的subtract函数的意思?一、数值型减法(高精度计算)1.

C/C++ chrono简单使用场景示例详解

《C/C++chrono简单使用场景示例详解》:本文主要介绍C/C++chrono简单使用场景示例详解,本文通过实例代码给大家介绍的非常详细,对大家的学习或工作具有一定的参考借鉴价值,需要的朋友... 目录chrono使用场景举例1 输出格式化字符串chrono使用场景China编程举例1 输出格式化字符串示

C++/类与对象/默认成员函数@构造函数的用法

《C++/类与对象/默认成员函数@构造函数的用法》:本文主要介绍C++/类与对象/默认成员函数@构造函数的用法,具有很好的参考价值,希望对大家有所帮助,如有错误或未考虑完全的地方,望不吝赐教... 目录名词概念默认成员函数构造函数概念函数特征显示构造函数隐式构造函数总结名词概念默认构造函数:不用传参就可以

C++类和对象之默认成员函数的使用解读

《C++类和对象之默认成员函数的使用解读》:本文主要介绍C++类和对象之默认成员函数的使用方式,具有很好的参考价值,希望对大家有所帮助,如有错误或未考虑完全的地方,望不吝赐教... 目录一、默认成员函数有哪些二、各默认成员函数详解默认构造函数析构函数拷贝构造函数拷贝赋值运算符三、默认成员函数的注意事项总结一

C/C++中OpenCV 矩阵运算的实现

《C/C++中OpenCV矩阵运算的实现》本文主要介绍了C/C++中OpenCV矩阵运算的实现,包括基本算术运算(标量与矩阵)、矩阵乘法、转置、逆矩阵、行列式、迹、范数等操作,感兴趣的可以了解一下... 目录矩阵的创建与初始化创建矩阵访问矩阵元素基本的算术运算 ➕➖✖️➗矩阵与标量运算矩阵与矩阵运算 (逐元

C/C++的OpenCV 进行图像梯度提取的几种实现

《C/C++的OpenCV进行图像梯度提取的几种实现》本文主要介绍了C/C++的OpenCV进行图像梯度提取的实现,文中通过示例代码介绍的非常详细,对大家的学习或者工作具有一定的参考学习价值,需要的... 目录预www.chinasem.cn备知识1. 图像加载与预处理2. Sobel 算子计算 X 和 Y

C/C++和OpenCV实现调用摄像头

《C/C++和OpenCV实现调用摄像头》本文主要介绍了C/C++和OpenCV实现调用摄像头,文中通过示例代码介绍的非常详细,对大家的学习或者工作具有一定的参考学习价值,需要的朋友们下面随着小编来一... 目录准备工作1. 打开摄像头2. 读取视频帧3. 显示视频帧4. 释放资源5. 获取和设置摄像头属性

c/c++的opencv图像金字塔缩放实现

《c/c++的opencv图像金字塔缩放实现》本文主要介绍了c/c++的opencv图像金字塔缩放实现,通过对原始图像进行连续的下采样或上采样操作,生成一系列不同分辨率的图像,具有一定的参考价值,感兴... 目录图像金字塔简介图像下采样 (cv::pyrDown)图像上采样 (cv::pyrUp)C++ O

c/c++的opencv实现图片膨胀

《c/c++的opencv实现图片膨胀》图像膨胀是形态学操作,通过结构元素扩张亮区填充孔洞、连接断开部分、加粗物体,OpenCV的cv::dilate函数实现该操作,本文就来介绍一下opencv图片... 目录什么是图像膨胀?结构元素 (KerChina编程nel)OpenCV 中的 cv::dilate() 函

C++ RabbitMq消息队列组件详解

《C++RabbitMq消息队列组件详解》:本文主要介绍C++RabbitMq消息队列组件的相关知识,本文给大家介绍的非常详细,对大家的学习或工作具有一定的参考借鉴价值,需要的朋友参考下吧... 目录1. RabbitMq介绍2. 安装RabbitMQ3. 安装 RabbitMQ 的 C++客户端库4. A