当前位置: 首页 > news >正文

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&#xfffd; 堆石子以及一个由 k&#xfffd; 个不同正整数构成的数字集合 S&#xfffd;。 现在有两位玩家轮流操作&#xff0c;每次操作可以从任意一堆石子中拿取石子&#xff0c;每次拿取的石子数量必须包含于集合 S&#xfffd;&#xff0c;最后无法进行操作的人视…...

数据安全防护:云访问安全代理(CASB)

云访问安全代理&#xff08;Cloud Access Security Broker&#xff0c;CASB&#xff09;&#xff0c;是一款面向应用的数据防护服务&#xff0c;基于免应用开发改造的配置方式&#xff0c;提供数据加密、数据脱敏功能。数据加密支持国密算法&#xff0c;提供面向服务侧的字段级…...

面试准备-操作系统

参考&#xff1a; 《程序员面试笔试宝典》&#xff08;何昊、叶向阳&#xff09; 进程是系统进行资源分配和调度的一个独立单位。线程是进程的一个实体&#xff0c;是cpu调度和分配的基本单位。线程基本不拥有系统资源&#xff0c;只拥有必须的&#xff0c;但是同属于一个进程…...

深度学习基础知识 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 开发人员使用的&#xff0c;其中包含了 java 的开发工具&#xff0c;也包括了 JRE 。所以安装了 JDK &#xff0c;就…...

【ppt技巧】批量修改ppt中的字体

PPT文件中的字体想要全部更换&#xff0c;有什么方便的方法吗&#xff1f;今天分享两个方法&#xff0c;一键修改ppt文件字体。 方法一&#xff1a; 找到功能栏中的编辑选项卡&#xff0c;点击替换 – 替换字体&#xff0c;在里面选择我们想要替换的字体就可以了。 方法二&am…...

RustDay01——运行在线GitHub Rust环境

1.跟着教程进入GitHub教室 2. 授权确认后进入学习空间 3.点击链接进入在线平台 4.添加本机密钥对到GitHub 5. 安装依赖 我们使用在线的Linux试验平台&#xff0c;就自动帮我们clone好了仓库 我们直接在仓库目录执行 cargo install --force --path . 安装依赖 PS:其实刚开始…...

上门按摩小程序|同城上门按摩软件开发|上门按摩系统;

上门按摩小程序的开发具有许多优势&#xff0c;下面就给大家介绍下按摩小程序功能: 上门按摩小程序的优势 方便快捷&#xff1a;上门按摩小程序提供在线预约服务&#xff0c;用户可以通过手机随时随地预约按摩师上门服务&#xff0c;避免了传统预约方式的繁琐和不确定性。 个性…...

rpm安装mysql8后碰到的问题

1 mysqld 无法启动 原因 已经使用了3306端口&#xff0c;修改my.cnf中端口为3308 2 修改为3308端口后&#xff0c;还是无法启动&#xff0c; 2023-10-07T02:20:10.096689Z 0 [ERROR] [MY-010262] [Server] Cant start server: Bind on TCP/IP port: Permission denied 2023…...

Linux 磁盘管理+实例

目录 一、文件系统 二、添加磁盘 三、查看磁盘信息&#xff08;块设备&#xff09; 四、分区 1、格式 1&#xff09;MBR分区 2&#xff09;GPT分区 2、管理分区 1&#xff09;使用fdisk 2&#xff09;使用gdisk 3&#xff09;使用parted a.交互式 b.非交互式 3、…...

MongoDB——centOS7安装mongodb5.0.21版本服务端(图解版)

目录 一、mongodb官网下载地址二、安装步骤2.1、上传安装包并解压2.2、配置环境变量2.3、创建目录并授权2.4、创建配置文件2.5、启动MongoDB 三、开放端口四、客户端连接 一、mongodb官网下载地址 mongodb官网下载地址&#xff1a;https://www.mongodb.com/try/download/commu…...

C#实现OPC DA转OPC UA服务器

运行软件前提前安装好OPC运行组件&#xff1a; 为方便演示&#xff0c;提前准备好了一个DAServer服务器&#xff1a; 接下来开始配置&#xff1a; 该软件主要实现的功能如下&#xff1a; 配置过程也相对简单&#xff1a; 第一步&#xff1a; 编辑如下文件&#xff1a; 第二步…...

TCP/IP网络协议通信函数接口

创建套接字函数 socket 【头文件】 #include <sys/types.h> #include <sys/socket.h> 【函数原型】 int socket(int domain, int type, int protocol); 【函数功能】 socket 函数创建一个通信端点&#xff0c;并返回一个引用该端点的文件描述符&#xff0c;…...

go语言判断管道是否关闭的误区

前言 本文是探讨的是"在Go语言中&#xff0c;我们是否可以使用读取管道时的第二个返回值来判断管道是否关闭?" 样例 在Go语言中&#xff0c;我们是否可以使用读取管道时的第二个返回值来判断管道是否关闭? 可以看下面的代码 package mainimport "fmt"…...

如何轻松使用 ChatGPT 进行论文大纲和创作

ChatGPT能够编写复杂的代码、博客文章等&#xff0c;它可以帮助我们做很多事情。今天本篇文章分享的主要内容如何利用 ChatGPT 来撰写论文文章。下面会介绍如何轻松使用 ChatGPT 进行论文大纲和创作&#xff01; 1、使用 ChatGPT 确定主题 文章非常重要的一个部分就是主题。如…...

【深蓝学院】手写VIO第6章--视觉前端--笔记

第5章相关内容&#xff0c;还是CSDN的传统Markdown编辑器好用。 视觉前段在14讲课程中已经讲过&#xff0c;这里再简单复习一下。 1. 前端工作的定性比较&#xff0c;分析 这一节讲了很多关于前端的方法框架的对比讨论&#xff0c;后面看完了相关的论文之后强烈建议再回来听一…...

用例图 UML从入门到放弃系列之三

1.说明 关于用例图&#xff0c;这篇文章我将直接照搬罗伯特.C.马丁老爷子在《敏捷开发》一书种的第17章&#xff0c;并配上自己的理解&#xff0c;因为这一章写的实在是太精彩了&#xff0c;希望能够分享给大家&#xff0c;共勉。以下是老爷子的原文中文翻译以及豆芽的个人解读…...

NLP大模型

大模型 1、大模型的模型结构 一般指一亿参数以上的模型。 目前以Transformer为基础自回归生成大致可以分为三种架构: Encoder-only的模型,如BERT Encoder-Decoder的模型,如T5。 Decoder-Only的模型,如GPT系列。...

Python- 将一个字符串列表连接成一个单独的字符串

Python中一个常用的技巧&#xff1a;将一个字符串列表连接成一个单独的字符串。 ,.join(list) 是使用Python的 str.join() 方法。 详细解析&#xff1a; join() 方法: 是一个字符串方法&#xff0c;意味着在一个字符串上调用它。它需要一个参数&#xff0c;通常是一个列表或任…...

深度学习在微纳光子学中的应用

深度学习在微纳光子学中的主要应用方向 深度学习与微纳光子学的结合主要集中在以下几个方向&#xff1a; 逆向设计 通过神经网络快速预测微纳结构的光学响应&#xff0c;替代传统耗时的数值模拟方法。例如设计超表面、光子晶体等结构。 特征提取与优化 从复杂的光学数据中自…...

synchronized 学习

学习源&#xff1a; https://www.bilibili.com/video/BV1aJ411V763?spm_id_from333.788.videopod.episodes&vd_source32e1c41a9370911ab06d12fbc36c4ebc 1.应用场景 不超卖&#xff0c;也要考虑性能问题&#xff08;场景&#xff09; 2.常见面试问题&#xff1a; sync出…...

ssc377d修改flash分区大小

1、flash的分区默认分配16M、 / # df -h Filesystem Size Used Available Use% Mounted on /dev/root 1.9M 1.9M 0 100% / /dev/mtdblock4 3.0M...

JVM垃圾回收机制全解析

Java虚拟机&#xff08;JVM&#xff09;中的垃圾收集器&#xff08;Garbage Collector&#xff0c;简称GC&#xff09;是用于自动管理内存的机制。它负责识别和清除不再被程序使用的对象&#xff0c;从而释放内存空间&#xff0c;避免内存泄漏和内存溢出等问题。垃圾收集器在Ja…...

在 Nginx Stream 层“改写”MQTT ngx_stream_mqtt_filter_module

1、为什么要修改 CONNECT 报文&#xff1f; 多租户隔离&#xff1a;自动为接入设备追加租户前缀&#xff0c;后端按 ClientID 拆分队列。零代码鉴权&#xff1a;将入站用户名替换为 OAuth Access-Token&#xff0c;后端 Broker 统一校验。灰度发布&#xff1a;根据 IP/地理位写…...

聊一聊接口测试的意义有哪些?

目录 一、隔离性 & 早期测试 二、保障系统集成质量 三、验证业务逻辑的核心层 四、提升测试效率与覆盖度 五、系统稳定性的守护者 六、驱动团队协作与契约管理 七、性能与扩展性的前置评估 八、持续交付的核心支撑 接口测试的意义可以从四个维度展开&#xff0c;首…...

GC1808高性能24位立体声音频ADC芯片解析

1. 芯片概述 GC1808是一款24位立体声音频模数转换器&#xff08;ADC&#xff09;&#xff0c;支持8kHz~96kHz采样率&#xff0c;集成Δ-Σ调制器、数字抗混叠滤波器和高通滤波器&#xff0c;适用于高保真音频采集场景。 2. 核心特性 高精度&#xff1a;24位分辨率&#xff0c…...

Unsafe Fileupload篇补充-木马的详细教程与木马分享(中国蚁剑方式)

在之前的皮卡丘靶场第九期Unsafe Fileupload篇中我们学习了木马的原理并且学了一个简单的木马文件 本期内容是为了更好的为大家解释木马&#xff08;服务器方面的&#xff09;的原理&#xff0c;连接&#xff0c;以及各种木马及连接工具的分享 文件木马&#xff1a;https://w…...

【生成模型】视频生成论文调研

工作清单 上游应用方向&#xff1a;控制、速度、时长、高动态、多主体驱动 类型工作基础模型WAN / WAN-VACE / HunyuanVideo控制条件轨迹控制ATI~镜头控制ReCamMaster~多主体驱动Phantom~音频驱动Let Them Talk: Audio-Driven Multi-Person Conversational Video Generation速…...

springboot整合VUE之在线教育管理系统简介

可以学习到的技能 学会常用技术栈的使用 独立开发项目 学会前端的开发流程 学会后端的开发流程 学会数据库的设计 学会前后端接口调用方式 学会多模块之间的关联 学会数据的处理 适用人群 在校学生&#xff0c;小白用户&#xff0c;想学习知识的 有点基础&#xff0c;想要通过项…...