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

题解 | #1002.Random Nim Game# 2023杭电暑期多校7

1002.Random Nim Game

诈骗博弈题

题目大意

Nim是一种双人数学策略游戏,玩家轮流从不同的堆中移除棋子。在每一轮游戏中,玩家必须至少取出一个棋子,并且可以取出任意数量的棋子,条件是这些棋子都来自同一个棋子堆。走最后一步棋(即取出最后一块棋子)的人获胜。

现在更改游戏规则,在每个回合中,棋手必须选择一个棋子堆。假设他选择的堆包含 x x x 个棋子,将从 [ 1 , x ] [1,x] [1,x] 中随机一个整数 y y y ,并从堆中移除 y y y 个棋子

求先手获胜的概率,答案取模

解题思路

看起来很吓人的一道题(谁被吓退了我不说)//

考虑只有一个堆的情况
若只有 1 1 1 个棋子,先手必胜
如果有 2 2 2 个棋子,有 1 2 \dfrac{1}{2} 21 的概率拿完获胜,有 1 2 \dfrac{1}{2} 21 的概率余 1 1 1 失败,综合胜率 1 2 \dfrac{1}{2} 21
⋮ \vdots
如果有 x ( x > 1 ) x\ (x>1) x (x>1) 个棋子,有 n − 2 n \dfrac{n-2}{n} nn2 的概率转移到 剩余个数 > 1 >1 >1 的状态,有 1 n \dfrac{1}{n} n1 的概率拿完获胜,有 1 n \dfrac{1}{n} n1 的概率余 1 1 1 失败。递归得到 x > 1 x>1 x>1 的状态下的综合胜率为 1 2 \dfrac{1}{2} 21

再考虑多堆的情况
如果所有堆的棋子数量均为 1 1 1 ,则当堆数 n n n 为奇数时先手必胜
如果有某堆的数量多于 1 1 1 个,那么必胜态将以 1 2 \dfrac{1}{2} 21 的概率流转

综上所述,如果所有堆的棋子数量均为 1 1 1 ,则当堆数 n n n 为奇数时先手必胜, n n n 为偶数时先手必败,其余情况综合胜率 1 2 \dfrac{1}{2} 21

参考代码

参考代码为已AC代码主干,其中部分功能需读者自行实现

void solve()
{ll n;cin >> n;ll mx=0,t;FORLL(i,1,n){cin >> t;mx=max(mx,t);}if(mx>1) cout << inv(2) << endl;else if(n%2) cout << 1 << endl;else cout << 0 << endl;
}

相关文章:

题解 | #1002.Random Nim Game# 2023杭电暑期多校7

1002.Random Nim Game 诈骗博弈题 题目大意 Nim是一种双人数学策略游戏&#xff0c;玩家轮流从不同的堆中移除棋子。在每一轮游戏中&#xff0c;玩家必须至少取出一个棋子&#xff0c;并且可以取出任意数量的棋子&#xff0c;条件是这些棋子都来自同一个棋子堆。走最后一步棋…...

篇九:组合模式:树形结构的力量

篇九&#xff1a;“组合模式&#xff1a;树形结构的力量” 开始本篇文章之前先推荐一个好用的学习工具&#xff0c;AIRIght&#xff0c;借助于AI助手工具&#xff0c;学习事半功倍。欢迎访问&#xff1a;http://airight.fun/。 另外有2本不错的关于设计模式的资料&#xff0c…...

【注册表】windows系统注册表常用修改方案

文章目录 ◆ 修改IE浏览器打印页面参数设置◆气泡屏幕保护◆彩带屏幕保护程序◆过滤IP(适用于WIN2000)◆禁止显示IE的地址栏◆禁止更改&#xff29;&#xff25;默认的检查(winnt适用)◆允许DHCP(winnt适用)◆局域网自动断开的时间(winnt适用)◆禁止使用“重置WEB设置”◆禁止更…...

ant-design-vue 4.x升级问题-样式丢失问题

[vue] ant-design-vue 4.x升级问题-样式丢失问题 项目环境问题场景解决方案 该文档是在升级ant-design-vue到4.x版本的时候遇到的问题 项目环境 "vue": "^3.3.4", "ant-design-vue": "^4.0.0", "vite": "^4.4.4&quo…...

【果树农药喷洒机器人】Part3:变量喷药系统工作原理介绍

本专栏介绍&#xff1a;免费专栏&#xff0c;持续更新机器人实战项目&#xff0c;欢迎各位订阅关注。 关注我&#xff0c;带你了解更多关于机器人、嵌入式、人工智能等方面的优质文章&#xff01; 文章目录 一、变量喷药系统工作原理二、液压通路设计与控制系统封装2.1液压通路…...

GoogLeNet创新点总结

GoogLeNet是一种深度卷积神经网络架构&#xff0c;于2014年由Google团队提出&#xff0c;是ILSVRC&#xff08;ImageNet Large Scale Visual Recognition Challenge&#xff09;比赛的冠军模型&#xff0c;其创新点主要集中在以下几个方面&#xff1a;   Inception模块&#…...

不同路径1、2、3合集(980. 不同路径 III)

不同路径一 矩形格&#xff0c;左上角 到 右下角。 class Solution {int [] directX new int[]{-1,1,0,0};int [] directY new int[]{0,0,-1,1};int rows;int cols;public int uniquePathsIII(int[][] grid) {if (grid null || grid.length 0 || grid[0].length 0) {ret…...

【云原生】Yaml文件详解

目录 一、YAML 语法格式1.1查看 api 资源版本标签1.2 写一个yaml文件demo1.3 详解k8s中的port 一、YAML 语法格式 Kubernetes 支持 YAML 和 JSON 格式管理资源对象JSON 格式&#xff1a;主要用于 api 接口之间消息的传递YAML格式&#xff1a;用于配置和管理&#xff0c;YAML 是…...

ffmpeg下载安装教程

ffmpeg官网下载地址https://ffmpeg.org/download.html 这里以windows为例,鼠标悬浮到windows图标上,再点击 Windows builds from gyan.dev 或者直接打开 https://www.gyan.dev/ffmpeg/builds/ 下载根据个人需要下载对应版本 解压下载的文件,并复制bin所在目录 新打开一个命令…...

uniapp之当你问起“tab方法触发时eventchange也跟着触发了咋办”时

我相信没有大佬会在这个问题上卡两个小时吧&#xff0c;记下来大家就当看个乐子了。 当时问题就是&#xff0c;点击tab头切换的时候&#xff0c;作为tab滑动事件的eventchange同时触发了&#xff0c;使得接口请求了两次 大概是没睡好&#xff0c;我当时脑子老想着怎么阻止它冒…...

TS 踩坑之路(四)之 Vue3

一、在使用定义默认值withDefaults和defineProps 组合时&#xff0c;默认值设置报错 代码案例 报错信息 不能将类型“{ isBackBtn: false; }”分配给类型“(props: PropsType) > RouteMsgType”。 对象字面量只能指定已知属性&#xff0c;并且“isBackBtn”不在类型“(pro…...

【音视频】edge与chrome在性能上的比较

目录 结论先说 实验 结论 实验机器的cpu配置 用EDGE拉九路​编辑 google拉五路就拉不出来了 资源使用情况 edge报错​编辑 如果服务器端 性能也满 了&#xff0c;就会不回复&#xff1b;验证方式 手动敲 8081&#xff0c;不回应。 结论先说 实验 用chrome先拉九路&#…...

Docker Compose编排部署LNMP服务

目录 安装docker-ce 阿里云镜像加速器 文件 启动 安装docker-ce [rootlocalhost ~]# wget -O /etc/yum.repos.d/CentOS-Base.repo http://mirrors.aliyun.com/repo/Centos-7.repo --2023-08-03 18:34:32-- http://mirrors.aliyun.com/repo/Centos-7.repo 正在解析主机 m…...

git使用(常见用法)

一.下载git git官方下载跳转 安装简单,有手就行 二. git的简单使用 1. 连接远程仓库 #初始化 git init #配置账户 git config --global user.name “输入你的用户名” git config --global user.email “输入你的邮箱” git config --list #--q退出 #配置验证邮箱 ssh-key…...

用例拆分情况考虑方案

文章目录 1、方案一方案概述方案分析(1) 把对应图商地图的逻辑给分离开(2) 要使用命令行的方式执行方法 2、方案二3、最终决定 1、方案一 方案概述 每个图商&#xff08;GD、BD、自建&#xff09;拆分成单独的类 把参数化的几个图商类别拆分成对应的图商类&#xff0c;在每个类…...

一文搞懂IS-IS报文通用格式

报文格式 IS-IS报文是直接封装在数据链路层的帧结构中的。PDU可以分为两个部分&#xff0c;报文头和变长字段部分。其中头部又可分为通用头部和专用头部。对于所有PDU来说&#xff0c;通用报头都是相同的&#xff0c;但专用报头根据PDU类型不同而有所差别。 IS-IS的PDU有4种类…...

位置参数 关键字参数

在Python中&#xff0c;函数参数可以按照位置或关键字来传递。这导致了两种主要的参数类型&#xff1a;位置参数和关键字参数。 位置参数: 这是最常见的参数类型&#xff0c;当我们调用函数时&#xff0c;传递给函数的参数值是按照它们的位置来确定的。例如&#xff0c;def fun…...

【果树农药喷洒机器人】Part5:基于深度相机与分割掩膜的果树冠层体积探测方法

文章目录 一、引言二、树冠体积测量对比方法2.1冠层体积人工测量法2.2冠层体积拟合测量法 三、基于深度相机与分割掩膜探测树冠体积方法3.1像素值与深度值的转换3.2树冠体积视觉探测法3.3实验分析 总结 一、引言 果树靶标探测是实现农药精准喷施的关键环节&#xff0c;本章以果…...

生活小妙招之UE custom Decal

因为这几年大部分时间都在搞美术&#xff0c;所以博客相关的可能会鸽的比较多&#xff0c;阿巴阿巴 https://twitter.com/Tuatara_Games/status/1674034744084905986 之前正好看到一个贴花相关的小技巧&#xff0c;正好做一个记录&#xff0c;也在这个的基础上做一些小的拓展…...

DAY02_Spring—第三方资源配置管理Spring容器Spring注解开发Spring整合Mybatis和Junit

目录 一 第三方资源配置管理1 管理DataSource连接池对象问题导入1.1 管理Druid连接池1.2 管理c3p0连接池 2 加载properties属性文件问题导入2.1 基本用法2.2 配置不加载系统属性2.3 加载properties文件写法 二 Spring容器1 Spring核心容器介绍问题导入1.1 创建容器1.2 获取bean…...

Python爬虫实战:研究MechanicalSoup库相关技术

一、MechanicalSoup 库概述 1.1 库简介 MechanicalSoup 是一个 Python 库,专为自动化交互网站而设计。它结合了 requests 的 HTTP 请求能力和 BeautifulSoup 的 HTML 解析能力,提供了直观的 API,让我们可以像人类用户一样浏览网页、填写表单和提交请求。 1.2 主要功能特点…...

使用VSCode开发Django指南

使用VSCode开发Django指南 一、概述 Django 是一个高级 Python 框架&#xff0c;专为快速、安全和可扩展的 Web 开发而设计。Django 包含对 URL 路由、页面模板和数据处理的丰富支持。 本文将创建一个简单的 Django 应用&#xff0c;其中包含三个使用通用基本模板的页面。在此…...

Qt Http Server模块功能及架构

Qt Http Server 是 Qt 6.0 中引入的一个新模块&#xff0c;它提供了一个轻量级的 HTTP 服务器实现&#xff0c;主要用于构建基于 HTTP 的应用程序和服务。 功能介绍&#xff1a; 主要功能 HTTP服务器功能&#xff1a; 支持 HTTP/1.1 协议 简单的请求/响应处理模型 支持 GET…...

ServerTrust 并非唯一

NSURLAuthenticationMethodServerTrust 只是 authenticationMethod 的冰山一角 要理解 NSURLAuthenticationMethodServerTrust, 首先要明白它只是 authenticationMethod 的选项之一, 并非唯一 1 先厘清概念 点说明authenticationMethodURLAuthenticationChallenge.protectionS…...

【Web 进阶篇】优雅的接口设计:统一响应、全局异常处理与参数校验

系列回顾&#xff1a; 在上一篇中&#xff0c;我们成功地为应用集成了数据库&#xff0c;并使用 Spring Data JPA 实现了基本的 CRUD API。我们的应用现在能“记忆”数据了&#xff01;但是&#xff0c;如果你仔细审视那些 API&#xff0c;会发现它们还很“粗糙”&#xff1a;有…...

拉力测试cuda pytorch 把 4070显卡拉满

import torch import timedef stress_test_gpu(matrix_size16384, duration300):"""对GPU进行压力测试&#xff0c;通过持续的矩阵乘法来最大化GPU利用率参数:matrix_size: 矩阵维度大小&#xff0c;增大可提高计算复杂度duration: 测试持续时间&#xff08;秒&…...

实现弹窗随键盘上移居中

实现弹窗随键盘上移的核心思路 在Android中&#xff0c;可以通过监听键盘的显示和隐藏事件&#xff0c;动态调整弹窗的位置。关键点在于获取键盘高度&#xff0c;并计算剩余屏幕空间以重新定位弹窗。 // 在Activity或Fragment中设置键盘监听 val rootView findViewById<V…...

智能仓储的未来:自动化、AI与数据分析如何重塑物流中心

当仓库学会“思考”&#xff0c;物流的终极形态正在诞生 想象这样的场景&#xff1a; 凌晨3点&#xff0c;某物流中心灯火通明却空无一人。AGV机器人集群根据实时订单动态规划路径&#xff1b;AI视觉系统在0.1秒内扫描包裹信息&#xff1b;数字孪生平台正模拟次日峰值流量压力…...

大语言模型(LLM)中的KV缓存压缩与动态稀疏注意力机制设计

随着大语言模型&#xff08;LLM&#xff09;参数规模的增长&#xff0c;推理阶段的内存占用和计算复杂度成为核心挑战。传统注意力机制的计算复杂度随序列长度呈二次方增长&#xff0c;而KV缓存的内存消耗可能高达数十GB&#xff08;例如Llama2-7B处理100K token时需50GB内存&a…...

SAP学习笔记 - 开发26 - 前端Fiori开发 OData V2 和 V4 的差异 (Deepseek整理)

上一章用到了V2 的概念&#xff0c;其实 Fiori当中还有 V4&#xff0c;咱们这一章来总结一下 V2 和 V4。 SAP学习笔记 - 开发25 - 前端Fiori开发 Remote OData Service(使用远端Odata服务)&#xff0c;代理中间件&#xff08;ui5-middleware-simpleproxy&#xff09;-CSDN博客…...