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游戏
给定 n 堆石子以及一个由 k 个不同正整数构成的数字集合 S 。 现在有两位玩家轮流操作,每次操作可以从任意一堆石子中拿取石子,每次拿取的石子数量必须包含于集合 S ,最后无法进行操作的人视为失败。 问如果两人都采用最优策略,…...
学者观察 | 区块链技术理论研究与实践观察——中央财经大学朱建明
导语 当下区块链研究成果质量越来越高,技术应用越来越成熟。在现阶段的研究中存在哪些短板需要弥补,如何将研究成果转化为推动数字经济高质量发展的实际应用,区块链技术与其他新技术结合发展将带来哪些新的机遇? 中央财经大学朱…...
使用Promethues+Grafana监控Elasticsearch
PromethuesGrafana监控Elasticsearch 监控选用说明指标上报流程说明实现监控的步骤搭建elasticsearch-exporter服务搭建promethues和grafana服务 监控选用说明 虽然用Kibana来监控ES,能展示一些关键指标,但ES本身收集的指标并不全面,还需要在…...
研学活动报名平台源码开发方案
一、项目背景与目标 (一)项目背景 研学活动报名平台旨在为活动组织者提供方便快捷的研学活动管理工具,同时为用户提供全面的活动搜索、报名和支付等功能。通过该系统,活动组织者能够更好地管理活动报名信息,用户也可…...
一篇文章,彻底理解数据库操作语言:DDL、DML、DCL、TCL
最近与开发和运维讨论数据库账号及赋权问题时,发现大家对DDL和DML两个概念并不了解。于是写一篇文章,系统的整理一下在数据库领域中的DDL、DML、DQL、DCL的使用及区别。 通常,数据库SQL语言共分为四大类:数据定义语言DDL…...
Linux编辑器之vim的使用
文章目录 一、vim简介二、vim的基本概念三、vim的基本操作四、vim正常模式命令集移动光标删除文字复制替换撤销上一次操作更改跳至指定的行vim末行模式命令集列出行号跳到文件中的某一行查找字符保存文件离开vim 五、进阶vim玩法打开文件批量注释代码执行shell命令指定注释窗口…...
制作OpenSSH 9.6 for openEuler 22.03 LTS的rpm升级包
OpenSSH作为操作系统底层管理平台软件,需要保持更新以免遭受安全攻击,编译生成rpm包是生产环境中批量升级的最佳途径。本文在国产openEuler 22.03 LTS系统上完成OpenSSH 9.6的编译工作。 一、编译环境 1、准备环境 基于vmware workstation发布的x86虚…...
DNS配置文件讲解
1. 概述 BIND:Berkeley Internet Name Domain ,伯克利因特网域名解析服务是一种全球使用最广泛的、 最高效的、最安全的域名解析服务程序 2. 安装软件 [rootserver ~]# yum install bind -y 3. bind服务中三个关键文件 /etc/named.conf : 主配置文件…...
142:vue+leaflet 加载tomtom地图(多种形式)
第142个 点击查看专栏目录 本示例介绍如何在vue+leaflet中添加tomtom地图,这里包含了多种形式,诸如中文标记、英文标记、白天地图、晚上地图、卫星影像图,高山海拔地形图等。 直接复制下面的 vue+leaflet源代码,操作2分钟即可运行实现效果 文章目录 示例效果配置方式示例…...
Android Mac电脑更改aar中的文件再打包
一 问题 要在Mac电脑上替换AAR中的文件并重新打包。 二 解决方案 1.解压AAR文件 将AAR文件重命名为.zip,并解压缩它,得到一个文件夹。 2.替换文件 在解压后的文件夹中找到您想替换的文件,将其替换为新文件。 3.重新打包 打开终端&…...
Jmeter脚本录制:抓取IOS手机请求包!
现在移动端的项目越来越多,今天给大家介绍一下,在IOS下Jmeter如何抓包。 1、电脑连上wifi; 2、Jmeter中配置“HTTP代理服务器” 1)启动Jmeter; 2)“测试计划”中添加“线程组”; 3)“测试计划”中添加“HTTP代理服务器”&#…...
大数据分析案例-基于随机森林算法构建电影票房预测模型
🤵♂️ 个人主页:艾派森的个人主页 ✍🏻作者简介:Python学习者 🐋 希望大家多多支持,我们一起进步!😄 如果文章对你有帮助的话, 欢迎评论 💬点赞Ǵ…...
关于Gitlab用户登录提示无限重定向循环ERR_TOO_MANY_REDIRECTS
#工作笔记# 查阅了网上所有相关的记录,都没有解决gitlab登录/users/sign_up/welcome提示ERR_TOO_MANY_REDIRECTS,好在最终解决了,记录在此。 先说下起因: github哼哼不想用了,原因太多,所以内部讨论用git…...
突破瓶颈,提升开发效率:Spring框架进阶与最佳实践-IOC
IOC相关内容 1.1 bean基础配置1.1.1 bean基础配置(id与class)1.1.2 bean的name属性步骤1:配置别名步骤2:根据名称容器中获取bean对象步骤3:运行程序 1.1.3 bean作用范围scope配置1.1.3.1 验证IOC容器中对象是否为单例验证思路具体实现 1.1.3.2 配置bean为非单例1.1.…...
西方网络安全人才培养的挑战及对策
文章目录 前言一、网络安全人才力量发展现状(一)注重从战略上重视网络安全人才培养和发展。(二)注重从多渠道多路径招募网络安全人才。(三)注重分层次分阶段系统规划网络安全人才培养模式。(四)注重通过实践锻炼进一步提升网络攻防实战能力。二、网络安全人才面临的形势…...
计算机网络之三次握手,四次挥手
TCP(传输控制协议)是一种面向连接的、可靠的传输层协议,用于在网络中的两个应用程序之间建立可靠的通信连接。TCP的核心特征之一是它使用“三次握手”过程来建立连接,以及“四次挥手”过程来终止连接。 三次握手(建立…...
深度强化学习(王树森)笔记09
深度强化学习(DRL) 本文是学习笔记,如有侵权,请联系删除。本文在ChatGPT辅助下完成。 参考链接 Deep Reinforcement Learning官方链接:https://github.com/wangshusen/DRL 源代码链接:https://github.c…...
调试OpenHarmony应用/服务
调试流程 DevEco Studio提供了丰富的OpenHarmony应用/服务调试能力,帮助开发者更方便、高效的调试应用/服务。 OpenHarmony应用/服务调试支持使用真机设备调试。使用真机设备进行调试前,需要对HAP进行签名后进行调试。详细的调试流程如下图所示&#x…...
【NGINX】NGINX如何阻止指定ip的请求
业务场景: web页面做了一个功能,在websocket请求失败的情况,会定时向服务端进行重试进行建立连接。 存在的问题是即使这个web系统没人操作的情况下,只要页面没有关闭,即使系统超时了页面也没有发生跳转,这…...
PHP抽奖设置中奖率,以及防高并发
一、中奖率,先在后台设定好奖项名称,抽奖份数,以及中奖百分比 奖品表draw 二、 借助文件排他锁,在处理下单请求的时候,用flock锁定一个文件,如果锁定失败说明有其他订单正在处理,此时要么等待要么直接提示用户"服务器繁忙" 阻塞(等待)模式,一般都是用这个模…...
蓝桥杯 2024 15届国赛 A组 儿童节快乐
P10576 [蓝桥杯 2024 国 A] 儿童节快乐 题目描述 五彩斑斓的气球在蓝天下悠然飘荡,轻快的音乐在耳边持续回荡,小朋友们手牵着手一同畅快欢笑。在这样一片安乐祥和的氛围下,六一来了。 今天是六一儿童节,小蓝老师为了让大家在节…...
【大模型RAG】Docker 一键部署 Milvus 完整攻略
本文概要 Milvus 2.5 Stand-alone 版可通过 Docker 在几分钟内完成安装;只需暴露 19530(gRPC)与 9091(HTTP/WebUI)两个端口,即可让本地电脑通过 PyMilvus 或浏览器访问远程 Linux 服务器上的 Milvus。下面…...
深入理解JavaScript设计模式之单例模式
目录 什么是单例模式为什么需要单例模式常见应用场景包括 单例模式实现透明单例模式实现不透明单例模式用代理实现单例模式javaScript中的单例模式使用命名空间使用闭包封装私有变量 惰性单例通用的惰性单例 结语 什么是单例模式 单例模式(Singleton Pattern&#…...
相机Camera日志分析之三十一:高通Camx HAL十种流程基础分析关键字汇总(后续持续更新中)
【关注我,后续持续新增专题博文,谢谢!!!】 上一篇我们讲了:有对最普通的场景进行各个日志注释讲解,但相机场景太多,日志差异也巨大。后面将展示各种场景下的日志。 通过notepad++打开场景下的日志,通过下列分类关键字搜索,即可清晰的分析不同场景的相机运行流程差异…...
【HarmonyOS 5 开发速记】如何获取用户信息(头像/昵称/手机号)
1.获取 authorizationCode: 2.利用 authorizationCode 获取 accessToken:文档中心 3.获取手机:文档中心 4.获取昵称头像:文档中心 首先创建 request 若要获取手机号,scope必填 phone,permissions 必填 …...
tomcat入门
1 tomcat 是什么 apache开发的web服务器可以为java web程序提供运行环境tomcat是一款高效,稳定,易于使用的web服务器tomcathttp服务器Servlet服务器 2 tomcat 目录介绍 -bin #存放tomcat的脚本 -conf #存放tomcat的配置文件 ---catalina.policy #to…...
go 里面的指针
指针 在 Go 中,指针(pointer)是一个变量的内存地址,就像 C 语言那样: a : 10 p : &a // p 是一个指向 a 的指针 fmt.Println(*p) // 输出 10,通过指针解引用• &a 表示获取变量 a 的地址 p 表示…...
【把数组变成一棵树】有序数组秒变平衡BST,原来可以这么优雅!
【把数组变成一棵树】有序数组秒变平衡BST,原来可以这么优雅! 🌱 前言:一棵树的浪漫,从数组开始说起 程序员的世界里,数组是最常见的基本结构之一,几乎每种语言、每种算法都少不了它。可你有没有想过,一组看似“线性排列”的有序数组,竟然可以**“长”成一棵平衡的二…...
python基础语法Ⅰ
python基础语法Ⅰ 常量和表达式变量是什么变量的语法1.定义变量使用变量 变量的类型1.整数2.浮点数(小数)3.字符串4.布尔5.其他 动态类型特征注释注释是什么注释的语法1.行注释2.文档字符串 注释的规范 常量和表达式 我们可以把python当作一个计算器,来进行一些算术…...
【多线程初阶】单例模式 指令重排序问题
文章目录 1.单例模式1)饿汉模式2)懒汉模式①.单线程版本②.多线程版本 2.分析单例模式里的线程安全问题1)饿汉模式2)懒汉模式懒汉模式是如何出现线程安全问题的 3.解决问题进一步优化加锁导致的执行效率优化预防内存可见性问题 4.解决指令重排序问题 1.单例模式 单例模式确保某…...
