蓝桥杯练习题——博弈论

1.必胜态后继至少存在一个必败态
2.必败态后继均为必胜态
在这里插入图片描述
在这里插入图片描述
在这里插入图片描述
在这里插入图片描述
在这里插入图片描述

Nim游戏

在这里插入图片描述

思路

2 3,先手必赢,先拿 1,然后变成 2 2,不管后手怎么拿,先手同样操作,后手一定先遇到 0 0
a1 ^ a2 ^ a3 … ^ an = 0,先手必败,否则先手必胜

#include<iostream>
using namespace std;
const int N = 1e5 + 10;
int a[N];
int n;

int main(){
    cin>>n;
    for(int i = 1; i <= n; i++) cin>>a[i];
    int res = a[1];
    for(int i = 2; i <= n; i++) res ^= a[i];
    if(res == 0) cout<<"No";
    else cout<<"Yes";
    return 0;
}

// 求先手必胜第一次怎么拿
#include<iostream>
using namespace std;
const int N = 1e5 + 10;
int a[N];
int n;

int main(){
    cin>>n;
    for(int i = 1; i <= n; i++) cin>>a[i];
    int res = a[1];
    for(int i = 2; i <= n; i++) res ^= a[i];
    if(res == 0) cout<<"lose";
    else{
        for(int i = 1; i <= n; i++){
            if((a[i] ^ res) >= a[i]) continue;
            printf("第%d堆 拿%d个\n", i, (a[i] - (a[i] ^ res)));
            a[i] = a[i] ^ res;
            break;
        }
    }
    for(int i = 1; i <= n; i++) printf("%d ", a[i]);
    return 0;
}

台阶-Nim游戏

在这里插入图片描述

思路

如果拿偶数的台阶,你拿多少下去,我就拿多少下去,所以只需要看奇数台阶
如果奇数位 a1 ^ a3 ^ a5 ^ … ^ an = 0,先手必败

#include<iostream>
using namespace std;
const int N = 1e5 + 10;
int a[N];
int n;

int main(){
    scanf("%d", &n);
    for(int i = 1; i <= n; i++) scanf("%d", &a[i]);
    int res = a[1];
    for(int i = 3; i <= n; i += 2){
        res ^= a[i];
    }
    if(res) printf("Yes\n");
    else printf("No\n");
    return 0;
}

集合-Nim游戏

在这里插入图片描述

思路

如果 SG(x1) ^ SG(x2) ^ SG(x3) ^ … ^ SG(xn) = 0,先手必败
在这里插入图片描述
能到 0 那就是 1,能到 1 那就是 0,同时能到 1 和 0,那就是 2

#include<iostream>
#include<cstring>
#include<unordered_set>
using namespace std;
const int N = 110, M = 1e4 + 10;
int a[N], b[M];
int n, m;

int sg(int x){
    if(b[x] != -1) return b[x];
    unordered_set<int> s;
    for(int i = 0; i < n; i++){
        int t = a[i];
        if(x >= t) s.insert(sg(x - t));
    }
    for(int i = 0; ; i++){
        if(!s.count(i)){
            b[x] = i;
            return b[x];
        }
    }
}

int main(){
    memset(b, -1, sizeof(b));
    scanf("%d", &n);
    for(int i = 0; i < n; i++) scanf("%d", &a[i]);
    scanf("%d", &m);
    int res = 0, x;
    for(int i = 0; i < m; i++){
        scanf("%d", &x);
        res ^= sg(x);
    }
    if(res) printf("Yes\n");
    else printf("No\n");
    return 0;
}

拆分-Nim游戏

在这里插入图片描述
在这里插入图片描述

思路

一个数分成两个数,再异或

#include<iostream>
#include<cstring>
#include<unordered_set>
using namespace std;
const int N = 110;
int b[N];
int n;

int sg(int x){
    if(b[x] != -1) return b[x];
    unordered_set<int> s;
    for(int i = 0; i < x; i++){
        for(int j = 0; j <= i; j++){
            s.insert(sg(i) ^ sg(j));
        }
    }
    for(int i = 0; ; i++){
        if(!s.count(i)){
            b[x] = i;
            return b[x];
        }
    }
}

int main(){
    memset(b, -1, sizeof(b));
    scanf("%d", &n);
    int res = 0, x;
    for(int i = 0; i < n; i++){
        scanf("%d", &x);
        res ^= sg(x);
    }
    if(res) printf("Yes\n");
    else printf("No\n");
    return 0;
}

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

如若内容造成侵权/违法违规/事实不符,请联系我们进行投诉反馈qq邮箱809451989@qq.com,一经查实,立即删除!

相关文章

STL----vector的模拟实现

1. vector的介绍与使用 1.1 vector的介绍 1. vector是表示可变大小数组的序列容器。 2. 就像数组一样&#xff0c;vector也采用的连续存储空间来存储元素。也就是意味着可以采用下标对vector的元素进行访问&#xff0c;和数组一样高效。但是又不像数组&#xff0c;它的大小是可…

Vscode + PlatformIO + Arduino 搭建EPS32开发环境

Vscode PlatformIO Arduino 搭建EPS32开发环境 文章目录 Vscode PlatformIO Arduino 搭建EPS32开发环境1. Vscode插件安装2. 使用PlatformIO新建工程3.工程文件的基本结构4.一个基本的测试用例Reference 1. Vscode插件安装 如何下载vscode这里不再赘述&#xff0c;完成基本…

2024-2028年中国丙二醇乙醚(PE)市场行情监测及未来发展前景研究报告

丙二醇乙醚&#xff08;PE&#xff09;又称1-乙氧基-2-丙醇&#xff0c;化学式为C5H12O2&#xff0c;是一种有机化合物。丙二醇乙醚外观呈无色透明液体&#xff0c;微含醚气味&#xff0c;能与水和多数有机溶剂混溶&#xff0c;微溶于乙酸乙酯和氯仿。丙二醇乙醚具有吸湿性、挥…

ensp中pc机访问不同网络的服务器

拓扑图如下&#xff0c;资源已上传 说明&#xff1a;pc通过2个路由访问server服务器 三条线路分别是192.168.1.0网段&#xff0c;192.168.2.0网段和192.168.3.0网段&#xff0c;在未配置的情况下&#xff0c;pc设备是访问不到server的 具体操作流程 第一&#xff1b;pc设备…

Redis桌面客户端

3.4.Redis桌面客户端 安装完成Redis&#xff0c;我们就可以操作Redis&#xff0c;实现数据的CRUD了。这需要用到Redis客户端&#xff0c;包括&#xff1a; 命令行客户端图形化桌面客户端编程客户端 3.4.1.Redis命令行客户端 Redis安装完成后就自带了命令行客户端&#xff1…

连接数据库(MySQL)的JDBC

目录 JDBC简介快速入门API详解DriverManager&#xff08;驱动管理类&#xff09;注册驱动&#xff1a;获取数据库连接(对象)&#xff1a; Connection&#xff08;数据库连接对象&#xff09;获取执行SQL的对象管理事务 Statement(执行SQL语句)执行DML、DDL语句执行DQL语句 Resu…

ArcGIS矢量裁剪矢量

一、利用相交工具 Arctoolbox工具一分析工具一叠加分析一相交

深度|庖丁解InnoDB之Buffer Pool

以下文章来源于MySQL内核剖析 &#xff0c;作者王康 前言 Buffer Pool是InnoDB中非常重要的组成部分&#xff0c;也是数据库用户最关心的组件之一。Buffer Pool的基本功能并不复杂&#xff0c;设计实现也比较清晰&#xff0c;但作为一个有几十年历史的工业级数据库产品&am…

那位拿了多个Offer的大佬分享了最新Go面经

和大家分享一下我们 Go就业训练营 和 升职加薪星球 中战友们投稿的真实面经。 这是第一篇&#xff0c;计划还会再更新4篇最新Go面经&#xff0c;都是拿到Offer的那种&#xff01; 欢迎大家关注我的账号&#xff0c;关注之后不迷路。 先秀战绩 虽然不同的公司考察的侧重点不一…

Linux系统服务

文章目录 什么是daemon与服务(service)systemd使用unit分类 通过systemctl管理服务通过systemctl管理单一服务(service unit)通过systemctl查看系统上所有的服务通过systemctl管理不同的操作环境(target unit)通过systemctl分析各服务之间的依赖性与systemd的daemon运行过程相关…

Codeforces Round 930 (Div. 2) --- D. Pinball --- 题解

目录 D. Pinball&#xff1a; 题目大意&#xff1a; 思路解析&#xff1a; 代码实现&#xff1a; 代码一&#xff1a; 代码二&#xff1a; D. Pinball&#xff1a; 题目大意&#xff1a; 思路解析&#xff1a; 假设字符串为 >>><<<&#xff0c; 当前位…

程序员35岁会失业吗?【来自主流AI的回答】

程序员35岁会失业吗&#xff1f; 35岁被认为是程序员职业生涯的分水岭&#xff0c;许多程序员开始担忧自己的职业发展是否会受到年龄的限制。有人担心随着年龄的增长&#xff0c;技术更新换代的速度会使得资深程序员难以跟上&#xff1b;而另一些人则认为&#xff0c;丰富的经…

STM32CubeIDE基础学习-USART串口通信实验(轮询方式)

STM32CubeIDE基础学习-USART串口通信实验&#xff08;轮询方式&#xff09; 文章目录 STM32CubeIDE基础学习-USART串口通信实验&#xff08;轮询方式&#xff09;前言第1章 硬件介绍第2章 工程配置2.1 工程外设配置部分2.2 生成工程代码部分 第3章 代码编写3.1 串口发送3.1.1 发…

SqlServer期末复习(数据库原理及应用)持续更新中

一、SQL语句 1.1 SQL语句知识引入 1.DDL语言(数据定义语言&#xff09;主要是进行定义/改变表的结构、数据类型、表之间的链接等操作&#xff0c;关键字CREATE、DROP、ALTER CREATE TABLE 表面( 列名1 数据类型&#xff0c; 列名2 数据类型&#xff0c; ) ALTER TABLE 表名&a…

[计算机效率] 文件查重工具:Vistanita Duplicate Finder

3.6 文件查重工具&#xff1a;Vistanita Duplicate Finder Vistanita Duplicate Finder 是一款强大的文件查重工具&#xff0c;可以帮助用户快速查找并删除重复的文件&#xff0c;节省存储空间并提高文件管理效率。该软件支持多种文件类型&#xff0c;包括图片、文档、音频、视…

el-table 表格中插入表单循环校验

<template><div>{{form}}<el-form :model"form" ref"form"><el-form-item label"呃呃呃呃呃呃呃"><el-table :data"tableData" border><el-table-column prop"time" label"日期"…

cookie、localStorage、sessionStorage 详解

目录 cookie 是什么&#xff1f; cookie 不可以跨域请求 cookie 的属性 会话cookie & 永久性cookie cookie 禁用 cookie 的应用 sessionStorage 是什么&#xff1f; 失效时间 存储内容的类型 存储的大小 存储的位置 sessionStorage 的应用 localStorage 是什么…

Linux内核架构和基础概念

文章目录 前言 一、简述操作系统 二、宏内核和微内核 1.宏内核 2.微内核 3.Linux内核的特点 三&#xff0c;Linux内核架构 1.整体架构图 2.Linux子系统的划分 3.Linux子系统之间的关系 4.Linux内核目录介绍 总结 前言 随着Linux内核在全球市场份额的持续扩大&#xff0c;其影…

使用WebClient发起网络请求

目录 1、导入对应的pom 2、编写WebClientUtil请求工具类 3、使用WebClientUtil发起请求 使用WebClient的优点&#xff1a;支持lambdas 的函数&#xff1b;支持更高的并发性和更少的硬件资源&#xff1b;支持同步和异步&#xff1b;支持流式传输。具体的使用方式如下&#xff1a…

Redis 特性,为什么要用Redis,Redis到底是多线程还是单线程

一、Redis介绍 Redis&#xff08;Remote Dictionary Server )&#xff0c;即远程字典服务&#xff0c;是一个开源的&#xff0c;使用C语言编写、支持网络、可基于内存亦可持久化的日志型、Key-Value数据库&#xff0c;并提供多种语言的API。 二、特性(为什么要用Redis&#x…