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锁定一个文件,如果锁定失败说明有其他订单正在处理,此时要么等待要么直接提示用户"服务器繁忙" 阻塞(等待)模式,一般都是用这个模…...
CTF show Web 红包题第六弹
提示 1.不是SQL注入 2.需要找关键源码 思路 进入页面发现是一个登录框,很难让人不联想到SQL注入,但提示都说了不是SQL注入,所以就不往这方面想了 先查看一下网页源码,发现一段JavaScript代码,有一个关键类ctfs…...
Qt/C++开发监控GB28181系统/取流协议/同时支持udp/tcp被动/tcp主动
一、前言说明 在2011版本的gb28181协议中,拉取视频流只要求udp方式,从2016开始要求新增支持tcp被动和tcp主动两种方式,udp理论上会丢包的,所以实际使用过程可能会出现画面花屏的情况,而tcp肯定不丢包,起码…...
微软PowerBI考试 PL300-选择 Power BI 模型框架【附练习数据】
微软PowerBI考试 PL300-选择 Power BI 模型框架 20 多年来,Microsoft 持续对企业商业智能 (BI) 进行大量投资。 Azure Analysis Services (AAS) 和 SQL Server Analysis Services (SSAS) 基于无数企业使用的成熟的 BI 数据建模技术。 同样的技术也是 Power BI 数据…...
【入坑系列】TiDB 强制索引在不同库下不生效问题
文章目录 背景SQL 优化情况线上SQL运行情况分析怀疑1:执行计划绑定问题?尝试:SHOW WARNINGS 查看警告探索 TiDB 的 USE_INDEX 写法Hint 不生效问题排查解决参考背景 项目中使用 TiDB 数据库,并对 SQL 进行优化了,添加了强制索引。 UAT 环境已经生效,但 PROD 环境强制索…...
C++ 求圆面积的程序(Program to find area of a circle)
给定半径r,求圆的面积。圆的面积应精确到小数点后5位。 例子: 输入:r 5 输出:78.53982 解释:由于面积 PI * r * r 3.14159265358979323846 * 5 * 5 78.53982,因为我们只保留小数点后 5 位数字。 输…...
AI书签管理工具开发全记录(十九):嵌入资源处理
1.前言 📝 在上一篇文章中,我们完成了书签的导入导出功能。本篇文章我们研究如何处理嵌入资源,方便后续将资源打包到一个可执行文件中。 2.embed介绍 🎯 Go 1.16 引入了革命性的 embed 包,彻底改变了静态资源管理的…...
Go 语言并发编程基础:无缓冲与有缓冲通道
在上一章节中,我们了解了 Channel 的基本用法。本章将重点分析 Go 中通道的两种类型 —— 无缓冲通道与有缓冲通道,它们在并发编程中各具特点和应用场景。 一、通道的基本分类 类型定义形式特点无缓冲通道make(chan T)发送和接收都必须准备好࿰…...
华为OD机试-最短木板长度-二分法(A卷,100分)
此题是一个最大化最小值的典型例题, 因为搜索范围是有界的,上界最大木板长度补充的全部木料长度,下界最小木板长度; 即left0,right10^6; 我们可以设置一个候选值x(mid),将木板的长度全部都补充到x,如果成功…...
【前端异常】JavaScript错误处理:分析 Uncaught (in promise) error
在前端开发中,JavaScript 异常是不可避免的。随着现代前端应用越来越多地使用异步操作(如 Promise、async/await 等),开发者常常会遇到 Uncaught (in promise) error 错误。这个错误是由于未正确处理 Promise 的拒绝(r…...
【SpringBoot自动化部署】
SpringBoot自动化部署方法 使用Jenkins进行持续集成与部署 Jenkins是最常用的自动化部署工具之一,能够实现代码拉取、构建、测试和部署的全流程自动化。 配置Jenkins任务时,需要添加Git仓库地址和凭证,设置构建触发器(如GitHub…...
