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

相关文章

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

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

C++ 中的 if-constexpr语法和作用

《C++中的if-constexpr语法和作用》if-constexpr语法是C++17引入的新语法特性,也被称为常量if表达式或静态if(staticif),:本文主要介绍C++中的if-c... 目录1 if-constexpr 语法1.1 基本语法1.2 扩展说明1.2.1 条件表达式1.2.2 fa

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

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

JavaScript Array.from及其相关用法详解(示例演示)

《JavaScriptArray.from及其相关用法详解(示例演示)》Array.from方法是ES6引入的一个静态方法,用于从类数组对象或可迭代对象创建一个新的数组实例,本文将详细介绍Array... 目录一、Array.from 方法概述1. 方法介绍2. 示例演示二、结合实际场景的使用1. 初始化二

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

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

C++从序列容器中删除元素的四种方法

《C++从序列容器中删除元素的四种方法》删除元素的方法在序列容器和关联容器之间是非常不同的,在序列容器中,vector和string是最常用的,但这里也会介绍deque和list以供全面了解,尽管在一... 目录一、简介二、移除给定位置的元素三、移除与某个值相等的元素3.1、序列容器vector、deque

C++常见容器获取头元素的方法大全

《C++常见容器获取头元素的方法大全》在C++编程中,容器是存储和管理数据集合的重要工具,不同的容器提供了不同的接口来访问和操作其中的元素,获取容器的头元素(即第一个元素)是常见的操作之一,本文将详细... 目录一、std::vector二、std::list三、std::deque四、std::forwa

C++字符串提取和分割的多种方法

《C++字符串提取和分割的多种方法》在C++编程中,字符串处理是一个常见的任务,尤其是在需要从字符串中提取特定数据时,本文将详细探讨如何使用C++标准库中的工具来提取和分割字符串,并分析不同方法的适用... 目录1. 字符串提取的基本方法1.1 使用 std::istringstream 和 >> 操作符示

C++原地删除有序数组重复项的N种方法

《C++原地删除有序数组重复项的N种方法》给定一个排序数组,你需要在原地删除重复出现的元素,使得每个元素只出现一次,返回移除后数组的新长度,不要使用额外的数组空间,你必须在原地修改输入数组并在使用O(... 目录一、问题二、问题分析三、算法实现四、问题变体:最多保留两次五、分析和代码实现5.1、问题分析5.

C++ 各种map特点对比分析

《C++各种map特点对比分析》文章比较了C++中不同类型的map(如std::map,std::unordered_map,std::multimap,std::unordered_multima... 目录特点比较C++ 示例代码 ​​​​​​代码解释特点比较1. std::map底层实现:基于红黑