acwing.893. 集合-Nim游戏(博弈论sg函数模板)
给定 n� 堆石子以及一个由 k� 个不同正整数构成的数字集合 S�。
现在有两位玩家轮流操作,每次操作可以从任意一堆石子中拿取石子,每次拿取的石子数量必须包含于集合 S�,最后无法进行操作的人视为失败。
问如果两人都采用最优策略,先手是否必胜。
输入格式
第一行包含整数 k�,表示数字集合 S� 中数字的个数。
第二行包含 k� 个整数,其中第 i� 个整数表示数字集合 S� 中的第 i� 个数 si��。
第三行包含整数 n�。
第四行包含 n� 个整数,其中第 i� 个整数表示第 i� 堆石子的数量 hiℎ�。
输出格式
如果先手方必胜,则输出 Yes。
否则,输出 No。
数据范围
1≤n,k≤1001≤�,�≤100,
1≤si,hi≤10000
思路:
对每个x求sg(x)然后然后异或得解。
代码:
#define _CRT_SECURE_NO_WARNINGS
#include<iostream>
#include<cstdio>
#include<cstdlib>
#include<string>
#include<cstring>
#include<cmath>
#include<ctime>
#include<algorithm>
#include<utility>
#include<stack>
#include<queue>
#include<vector>
#include<set>
#include<math.h>
#include<unordered_map>
#include<map>
using namespace std;
#define LL long long
#define per(i,a,b) for(int i=a;i<=b;i++)
#define rep(i,a,b) for(int i=a;i>=b;i--)
const int N = 1e5 + 100;
int k, n;
int f[N], s[N], ans = 0;//f[x]为sg(x)
int sg(int x)
{
if (f[x] != -1) return f[x];
unordered_map<int, int> p;
per(i, 1, k)//递归求由x能到的状态sg函数值
{
if (x >= s[i])
p[sg(x - s[i])] = 1;
}
for (int i = 0;; i++)//mex函数求sg(x)
if (!p[i])
{
f[x] = i;
break;
}
p.clear();
return f[x];
}
int main()
{
memset(f, -1, sizeof f);
cin >> k;
per(i, 1, k)
cin >> s[i];
cin >> n;
int x;
per(i, 1, n)
{
cin >> x;
ans ^= sg(x);
}
if (ans)
cout << "Yes" << endl;
else
cout << "No" << endl;
return 0;
}
相关文章:
acwing.893. 集合-Nim游戏(博弈论sg函数模板)
给定 n� 堆石子以及一个由 k� 个不同正整数构成的数字集合 S�。 现在有两位玩家轮流操作,每次操作可以从任意一堆石子中拿取石子,每次拿取的石子数量必须包含于集合 S�,最后无法进行操作的人视…...
数据安全防护:云访问安全代理(CASB)
云访问安全代理(Cloud Access Security Broker,CASB),是一款面向应用的数据防护服务,基于免应用开发改造的配置方式,提供数据加密、数据脱敏功能。数据加密支持国密算法,提供面向服务侧的字段级…...
面试准备-操作系统
参考: 《程序员面试笔试宝典》(何昊、叶向阳) 进程是系统进行资源分配和调度的一个独立单位。线程是进程的一个实体,是cpu调度和分配的基本单位。线程基本不拥有系统资源,只拥有必须的,但是同属于一个进程…...
深度学习基础知识 Batch Normalization的用法解析
深度学习基础知识 Batch Normalization的用法解析 import numpy as np import torch.nn as nn import torchdef bn_process(feature, mean, var):feature_shape feature.shapefor i in range(feature_shape[1]):# [batch, channel, height, width]feature_t feature[:, i, :,…...
Centos7安装MongoDB7.xxNoSQL数据库|设置开机启动(骨灰级+保姆级)
一: mongodb下载 MongoDB 社区免费下载版 MongoDB社区下载版 [rootwww tools]# wget https://fastdl.mongodb.org/linux/mongodb-linux-x86_64-rhel70-7.1.0-rc4.tgz 二: 解压到指定目录 [rootwww tools]# mkdir -p /usr/local/mongodb [rootwww tools]# tar -zxvf mongodb-…...
JDK、JRE、JVM三者之间的关系
1.JDK 基本介绍 1) JDK 的全称 (Java Development Kit Java 开发工具包 ) JDK JRE java 的开发工具 [java, javac,javadoc,javap 等 ] 2) JDK 是提供给 Java 开发人员使用的,其中包含了 java 的开发工具,也包括了 JRE 。所以安装了 JDK ,就…...
【ppt技巧】批量修改ppt中的字体
PPT文件中的字体想要全部更换,有什么方便的方法吗?今天分享两个方法,一键修改ppt文件字体。 方法一: 找到功能栏中的编辑选项卡,点击替换 – 替换字体,在里面选择我们想要替换的字体就可以了。 方法二&am…...
RustDay01——运行在线GitHub Rust环境
1.跟着教程进入GitHub教室 2. 授权确认后进入学习空间 3.点击链接进入在线平台 4.添加本机密钥对到GitHub 5. 安装依赖 我们使用在线的Linux试验平台,就自动帮我们clone好了仓库 我们直接在仓库目录执行 cargo install --force --path . 安装依赖 PS:其实刚开始…...
上门按摩小程序|同城上门按摩软件开发|上门按摩系统;
上门按摩小程序的开发具有许多优势,下面就给大家介绍下按摩小程序功能: 上门按摩小程序的优势 方便快捷:上门按摩小程序提供在线预约服务,用户可以通过手机随时随地预约按摩师上门服务,避免了传统预约方式的繁琐和不确定性。 个性…...
rpm安装mysql8后碰到的问题
1 mysqld 无法启动 原因 已经使用了3306端口,修改my.cnf中端口为3308 2 修改为3308端口后,还是无法启动, 2023-10-07T02:20:10.096689Z 0 [ERROR] [MY-010262] [Server] Cant start server: Bind on TCP/IP port: Permission denied 2023…...
Linux 磁盘管理+实例
目录 一、文件系统 二、添加磁盘 三、查看磁盘信息(块设备) 四、分区 1、格式 1)MBR分区 2)GPT分区 2、管理分区 1)使用fdisk 2)使用gdisk 3)使用parted a.交互式 b.非交互式 3、…...
MongoDB——centOS7安装mongodb5.0.21版本服务端(图解版)
目录 一、mongodb官网下载地址二、安装步骤2.1、上传安装包并解压2.2、配置环境变量2.3、创建目录并授权2.4、创建配置文件2.5、启动MongoDB 三、开放端口四、客户端连接 一、mongodb官网下载地址 mongodb官网下载地址:https://www.mongodb.com/try/download/commu…...
C#实现OPC DA转OPC UA服务器
运行软件前提前安装好OPC运行组件: 为方便演示,提前准备好了一个DAServer服务器: 接下来开始配置: 该软件主要实现的功能如下: 配置过程也相对简单: 第一步: 编辑如下文件: 第二步…...
TCP/IP网络协议通信函数接口
创建套接字函数 socket 【头文件】 #include <sys/types.h> #include <sys/socket.h> 【函数原型】 int socket(int domain, int type, int protocol); 【函数功能】 socket 函数创建一个通信端点,并返回一个引用该端点的文件描述符,…...
go语言判断管道是否关闭的误区
前言 本文是探讨的是"在Go语言中,我们是否可以使用读取管道时的第二个返回值来判断管道是否关闭?" 样例 在Go语言中,我们是否可以使用读取管道时的第二个返回值来判断管道是否关闭? 可以看下面的代码 package mainimport "fmt"…...
如何轻松使用 ChatGPT 进行论文大纲和创作
ChatGPT能够编写复杂的代码、博客文章等,它可以帮助我们做很多事情。今天本篇文章分享的主要内容如何利用 ChatGPT 来撰写论文文章。下面会介绍如何轻松使用 ChatGPT 进行论文大纲和创作! 1、使用 ChatGPT 确定主题 文章非常重要的一个部分就是主题。如…...
【深蓝学院】手写VIO第6章--视觉前端--笔记
第5章相关内容,还是CSDN的传统Markdown编辑器好用。 视觉前段在14讲课程中已经讲过,这里再简单复习一下。 1. 前端工作的定性比较,分析 这一节讲了很多关于前端的方法框架的对比讨论,后面看完了相关的论文之后强烈建议再回来听一…...
用例图 UML从入门到放弃系列之三
1.说明 关于用例图,这篇文章我将直接照搬罗伯特.C.马丁老爷子在《敏捷开发》一书种的第17章,并配上自己的理解,因为这一章写的实在是太精彩了,希望能够分享给大家,共勉。以下是老爷子的原文中文翻译以及豆芽的个人解读…...
NLP大模型
大模型 1、大模型的模型结构 一般指一亿参数以上的模型。 目前以Transformer为基础自回归生成大致可以分为三种架构: Encoder-only的模型,如BERT Encoder-Decoder的模型,如T5。 Decoder-Only的模型,如GPT系列。...
Python- 将一个字符串列表连接成一个单独的字符串
Python中一个常用的技巧:将一个字符串列表连接成一个单独的字符串。 ,.join(list) 是使用Python的 str.join() 方法。 详细解析: join() 方法: 是一个字符串方法,意味着在一个字符串上调用它。它需要一个参数,通常是一个列表或任…...
Vim 调用外部命令学习笔记
Vim 外部命令集成完全指南 文章目录 Vim 外部命令集成完全指南核心概念理解命令语法解析语法对比 常用外部命令详解文本排序与去重文本筛选与搜索高级 grep 搜索技巧文本替换与编辑字符处理高级文本处理编程语言处理其他实用命令 范围操作示例指定行范围处理复合命令示例 实用技…...
Docker 离线安装指南
参考文章 1、确认操作系统类型及内核版本 Docker依赖于Linux内核的一些特性,不同版本的Docker对内核版本有不同要求。例如,Docker 17.06及之后的版本通常需要Linux内核3.10及以上版本,Docker17.09及更高版本对应Linux内核4.9.x及更高版本。…...
日语学习-日语知识点小记-构建基础-JLPT-N4阶段(33):にする
日语学习-日语知识点小记-构建基础-JLPT-N4阶段(33):にする 1、前言(1)情况说明(2)工程师的信仰2、知识点(1) にする1,接续:名词+にする2,接续:疑问词+にする3,(A)は(B)にする。(2)復習:(1)复习句子(2)ために & ように(3)そう(4)にする3、…...
Java 8 Stream API 入门到实践详解
一、告别 for 循环! 传统痛点: Java 8 之前,集合操作离不开冗长的 for 循环和匿名类。例如,过滤列表中的偶数: List<Integer> list Arrays.asList(1, 2, 3, 4, 5); List<Integer> evens new ArrayList…...
【网络安全产品大调研系列】2. 体验漏洞扫描
前言 2023 年漏洞扫描服务市场规模预计为 3.06(十亿美元)。漏洞扫描服务市场行业预计将从 2024 年的 3.48(十亿美元)增长到 2032 年的 9.54(十亿美元)。预测期内漏洞扫描服务市场 CAGR(增长率&…...
鸿蒙中用HarmonyOS SDK应用服务 HarmonyOS5开发一个医院查看报告小程序
一、开发环境准备 工具安装: 下载安装DevEco Studio 4.0(支持HarmonyOS 5)配置HarmonyOS SDK 5.0确保Node.js版本≥14 项目初始化: ohpm init harmony/hospital-report-app 二、核心功能模块实现 1. 报告列表…...
【AI学习】三、AI算法中的向量
在人工智能(AI)算法中,向量(Vector)是一种将现实世界中的数据(如图像、文本、音频等)转化为计算机可处理的数值型特征表示的工具。它是连接人类认知(如语义、视觉特征)与…...
鱼香ros docker配置镜像报错:https://registry-1.docker.io/v2/
使用鱼香ros一件安装docker时的https://registry-1.docker.io/v2/问题 一键安装指令 wget http://fishros.com/install -O fishros && . fishros出现问题:docker pull 失败 网络不同,需要使用镜像源 按照如下步骤操作 sudo vi /etc/docker/dae…...
代码随想录刷题day30
1、零钱兑换II 给你一个整数数组 coins 表示不同面额的硬币,另给一个整数 amount 表示总金额。 请你计算并返回可以凑成总金额的硬币组合数。如果任何硬币组合都无法凑出总金额,返回 0 。 假设每一种面额的硬币有无限个。 题目数据保证结果符合 32 位带…...
【电力电子】基于STM32F103C8T6单片机双极性SPWM逆变(硬件篇)
本项目是基于 STM32F103C8T6 微控制器的 SPWM(正弦脉宽调制)电源模块,能够生成可调频率和幅值的正弦波交流电源输出。该项目适用于逆变器、UPS电源、变频器等应用场景。 供电电源 输入电压采集 上图为本设计的电源电路,图中 D1 为二极管, 其目的是防止正负极电源反接, …...
