C++ 数论相关题目 博弈论:拆分-Nim游戏

给定 n
堆石子,两位玩家轮流操作,每次操作可以取走其中的一堆石子,然后放入两堆规模更小的石子(新堆规模可以为 0
,且两个新堆的石子总数可以大于取走的那堆石子数),最后无法进行操作的人视为失败。

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

输入格式
第一行包含整数 n

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

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

否则,输出 No。

数据范围
1≤n,ai≤100
输入样例:
2
2 3
输出样例:
Yes
在这里插入图片描述

#include <iostream>
#include <algorithm>
#include <cstring>
#include <unordered_set>using namespace std;const int N = 110;
int n;
int f[N];//存i个状态的sg值int sg(int x)
{if(f[x] != -1) return f[x];unordered_set<int> S; //哈希表存储每个局面可以到的局面//这个地方特别关键:在集合的Nim游戏中,我们可以明显的知道可以到的下一个状态是什么//比如(x - s[i]),这道题里面需要遍历一下所有可能到达的状态,并且异或起来for(int i = 0; i < x; i ++ )for(int j = 0; j <= i; j ++) //用i和j表示分成的两个状态S.insert(sg(i) ^ sg(j));for(int i = 0; ; i ++ )if(!S.count(i))return f[x] = i;
}int main ()
{cin>>n;memset(f, -1, sizeof f); // 记忆化搜索,因为sg值都是自然数,所以初始化成-1,代表没有求过int res = 0;while(n -- ){int x;cin>>x;res ^= sg(x);}if(res) puts("Yes");else puts("No");return 0;
}

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处:http://www.rhkb.cn/news/250235.html

如若内容造成侵权/违法违规/事实不符,请联系长河编程网进行投诉反馈email:809451989@qq.com,一经查实,立即删除!

相关文章

Scrum敏捷开发企业培训-敏捷研发管理

课程简介 Scrum是目前运用最为广泛的敏捷开发方法&#xff0c;是一个轻量级的项目管理和产品研发管理框架。 这是一个两天的实训课程&#xff0c;面向研发管理者、项目经理、产品经理、研发团队等&#xff0c;旨在帮助学员全面系统地学习Scrum和敏捷开发, 帮助企业快速启动敏…

带libc源码gdb动态调试(导入glibc库使得可执行文件动态调试时可看见调用库函数源码)

文章目录 参考部分查看源码是否编译时有-g调试信息和符号表在 gdb 中加载 debug 文件/符号表将 debug 文件放入 ".debug" 文件夹通过 gdb 命令 set debug-file-directory directories GCC的gcc和g区别指定gcc/g&#xff0c;glibc的版本进行编译指定gcc/g的版本指定gl…

bash脚本学习笔记

一、扫盲 脚本文件是一种文本文件&#xff0c;其中包含了一系列的命令和指令&#xff0c;可以被操作系统解释器直接解释执行。脚本文件通常被用来完成特定的任务或执行重复性的操作。 脚本文件通常以某种编程语言的语法编写&#xff0c;例如 Bash、Python、Perl、Ruby 等等。…

Vue Router

Vue Router 一、Vue Router 回顾 1、路由简介 路由是一个比较广义和抽象的概念&#xff0c;路由的本质就是对应关系。 在开发中&#xff0c;路由分为&#xff1a; ​ 后端路由​ 前端路由 后端路由 概念&#xff1a;根据不同的用户 URL 请求&#xff0c;返回不同的内容本…

k8s中调整Pod数量限制的方法

一、介绍 Kubernetes节点每个默认允许最多创建110个pod&#xff0c;有时可能由于主机配置扩容的问题&#xff0c;从而需要修改节点pod运行数量的限制。 即&#xff1a;需要调整Node节点的最大可运行Pod数量。 一般来说&#xff0c;只需要在kubelet启动命令中增加–max-pods参数…

MySQL进阶之锁(全局锁以及备份报错解决)

锁 全局锁 全局锁就是对整个数据库实例加锁&#xff0c;加锁后整个实例就处于只读状态&#xff0c;后续的DML的写语句&#xff0c;DDL语 句&#xff0c;已经更新操作的事务提交语句都将被阻塞。 其典型的使用场景是做全库的逻辑备份&#xff0c;对所有的表进行锁定&#xff…

Java 基于 SpringBoot+Vue 的考研论坛管理系统

博主介绍&#xff1a;✌程序员徐师兄、7年大厂程序员经历。全网粉丝12W、csdn博客专家、掘金/华为云/阿里云/InfoQ等平台优质作者、专注于Java技术领域和毕业项目实战✌ &#x1f345;文末获取源码联系&#x1f345; &#x1f447;&#x1f3fb; 精彩专栏推荐订阅&#x1f447;…

在PostgreSQL中不开归档?恭喜你!锅你背定了

&#x1f4e2;&#x1f4e2;&#x1f4e2;&#x1f4e3;&#x1f4e3;&#x1f4e3; 哈喽&#xff01;大家好&#xff0c;我是【IT邦德】&#xff0c;江湖人称jeames007&#xff0c;10余年DBA及大数据工作经验 一位上进心十足的【大数据领域博主】&#xff01;&#x1f61c;&am…

微信小程序~上推加载更多组件

本组件使用的是TaroReact 实现的 &#xff0c;具体代码如下 一共分为tsx和less文件 //index.tsx /** RefreshLoading* description 上推加载更多组件* param loading boolean* param style* returns*/import { View } from "tarojs/components"; import React, { FC…

深入解剖指针篇(3)

个人主页&#xff08;找往期文章&#xff09; &#xff1a;我要学编程(ಥ_ಥ)-CSDN博客 目录 二级指针 指针数组 指针数组模拟二维数组 字符指针变量 数组指针 数组指针初始化 二维数组传参的本质 函数指针 函数指针的使用 typedef关键字 函数指针数组 二级指针…

U盘文件管理,禁止拷贝文件到U盘的解决办法

在许多企业和组织中&#xff0c;为了防止敏感数据的泄露和保护计算机系统的安全&#xff0c;通常会采取一些措施来限制员工拷贝文件到U盘的行为。然而&#xff0c;有些员工可能会试图绕过这些限制&#xff0c;导致数据安全风险增加。 案例 2015年5月&#xff0c;隶属于某县政府…

【yaml 文件使用】pytest+request 框架中 yaml 配置文件使用

又来进步一点点~~ 背景&#xff1a;最近在学习pytestrequest框架写接口测试自动化&#xff0c;使用yaml文件配置更方便管理用例中的数据&#xff0c;这样更方便 yaml 介绍&#xff1a; 什么是 yaml 文件&#xff1a;YAML 是 “YAML Ain’t a Markup Language”&#xff08;Y…

Android 系统启动流程

依旧是带着问题再去学习 首先&#xff0c;Android是怎么启动的&#xff1f; Android服务是怎么启动的&#xff1f; Android线程是怎么切换的&#xff1f; Android ApplicationThread是怎么创建的&#xff1f; 那么接下来开始分析Android的启动流程 还是一步一图 先画一张流…

jenkins pipeline配置maven可选参数

1、在Manage Jenkins下的Global Tool Configuration下对应的maven项添加我们要用得到的不同版本的maven安装项 2、pipeline文件内容具体如下 我们maven是单一的&#xff0c;所以我们都是配置单选参数 pipeline {agent anyparameters {gitParameter(name: BRANCH_TAG, type: …

Jenkins手把手图文教程[基于Jenkins 2.164.1]

Jenkins手把手图文教程[基于Jenkins 2.164.1] 本文基于当前最新的 LTS 版本 2.164.1 &#xff0c;理论上适应于Jenkins 2.x所有版本。 一、下载 前往https://jenkins.io/download/ &#xff0c;按需下载。如用于生产&#xff0c;建议下载Long-term Support (LTS) 版本&#xf…

【全网最全】2024美赛ABCDEF题思路模型全解(后续会更新)

欲获取更多资料&#xff0c;一定要点击这里并关注文末的公众号&#xff01;&#xff01;&#xff01; 最新更新&#xff1a;我们团队不仅在第一时间更新了24美赛全题目的深度翻译和深入分析&#xff0c;经过爆肝奋战&#xff0c;我们在第一时间给出了ABCDEF全题目的完整建模过程…

Swagger学习使用

swagger升级导致访问ui页面地址不一样 方式一 依赖 <parent><groupId>org.springframework.boot</groupId><artifactId>spring-boot-starter-parent</artifactId><version>1.5.3.RELEASE</version> </parent> <dependen…

随机 Transformer

在这篇博客中&#xff0c;我们将通过一个端到端的示例来讲解 Transformer 模型中的数学原理。我们的目标是对模型的工作原理有一个良好的理解。为了使内容易于理解&#xff0c;我们会进行大量简化。我们将减少模型的维度&#xff0c;以便我们可以手动推理模型的计算过程。例如&…

某赛通电子文档安全管理系统 UploadFileList 任意文件读取漏洞复现

0x01 产品简介 某赛通电子文档安全管理系统(简称:CDG)是一款电子文档安全加密软件,该系统利用驱动层透明加密技术,通过对电子文档的加密保护,防止内部员工泄密和外部人员非法窃取企业核心重要数据资产,对电子文档进行全生命周期防护,系统具有透明加密、主动加密、智能…