【学习笔记】[AGC048D] Pocky Game
这是一个非平等博弈。但是只要求你判断胜负,本身也不是一道结论题,所以可以用 D P DP DP来解决。
结论:第一堆石子剩的越多,先手玩家获胜的概率越大。这直接引出了一个非常感性的结论:每次取石子时要么取一堆,要么只取一个。很难理性证明这个博弈策略是正确的,但是博弈本身就是很玄学的东西,似乎我们找不出来一套普适的理论去判断游戏的胜负。那么只要这个策略本身具有合理性就可以采纳。就这道题而言,取一堆石子可以看成是加快游戏进度,取一个石子可以看成是让游戏的步数延长。看来这道题当中游戏步数是非常重要的维度,我们可以通过比较游戏步数的大小来判定胜负。
然后就是编 D P DP DP状态。设 f l , r f_{l,r} fl,r表示剩 [ l + 1 , r ] [l+1,r] [l+1,r]堆中石子时先手获胜, a l a_l al的最小数目, g l , r g_{l,r} gl,r表示剩 [ l , r − 1 ] [l,r-1] [l,r−1]堆中石子时后手获胜(后手先操作), a r a_r ar的最小数目。注意,这里我们要求 [ l , r ] [l,r] [l,r]中的石子堆都非空。这个状态给我一种 border \text{border} border的感觉,也就是要么左端点被截断或者右端点被截断,正好就是对应左右两端中两堆石子被消耗的过程。
接着编具体的转移。其实并不复杂:如果 g l + 1 , r > a r g_{l+1,r}>a_r gl+1,r>ar那么直接将第 l l l堆取空就行,有 f l , r = 1 f_{l,r}=1 fl,r=1;否则先手一定是消耗,并且 a l > 1 a_l>1 al>1,任意时刻如果 a l < f l , r − 1 a_l<f_{l,r-1} al<fl,r−1那么后手就会将第 r r r堆取完,从而先手必败,那么分类讨论:
1.1 1.1 1.1 如果 g l + 1 , r = 1 g_{l+1,r}=1 gl+1,r=1,那么一定要是后手取完,并且此时 a l a_l al恰好为 f l , r − 1 f_{l,r-1} fl,r−1,有 f l , r = f l , r − 1 + a r f_{l,r}=f_{l,r-1}+a_r fl,r=fl,r−1+ar
1.2 1.2 1.2 如果 g l + 1 , r ≠ 1 g_{l+1,r}\ne 1 gl+1,r=1,那么当 a l = f l , r − 1 a_l=f_{l,r-1} al=fl,r−1时第 r r r堆也恰好为 g l + 1 , r − 1 g_{l+1,r}-1 gl+1,r−1,此时再将 a l a_l al取完就变成先手必胜了,有 f l , r = f l , r − 1 + a r − g l + 1 , r + 1 f_{l,r}=f_{l,r-1}+a_r-g_{l+1,r}+1 fl,r=fl,r−1+ar−gl+1,r+1。
后手和先手是对称的就不说了。这个 D P DP DP转移还挺容易推错的,可能主要是因为没有想到临界时两端的石子数目都不为 0 0 0。
复杂度 O ( n 2 ) O(n^2) O(n2)。
#include<bits/stdc++.h>
#define ll long long
#define fi first
#define se second
#define pb push_back
#define db double
using namespace std;
int T,n;
ll a[105],f[105][105],g[105][105];
int main(){ios::sync_with_stdio(false);cin.tie(0),cout.tie(0);cin>>T;while(T--){cin>>n;for(int i=1;i<=n;i++)cin>>a[i];memset(f,0x3f,sizeof f),memset(g,0x3f,sizeof g);for(int i=1;i<=n;i++){f[i][i]=1,g[i][i]=1;}for(int len=2;len<=n;len++){for(int l=1;l<=n-len+1;l++){int r=l+len-1;if(g[l+1][r]>a[r])f[l][r]=1;else f[l][r]=f[l][r-1]+a[r]-g[l+1][r]+1;if(f[l][r-1]>a[l])g[l][r]=1;else g[l][r]=g[l+1][r]+a[l]-f[l][r-1]+1;}}if(n==1||f[1][n]<=a[1]){cout<<"First"<<"\n";}else{cout<<"Second"<<"\n";}}
}
相关文章:
【学习笔记】[AGC048D] Pocky Game
这是一个非平等博弈。但是只要求你判断胜负,本身也不是一道结论题,所以可以用 D P DP DP来解决。 结论:第一堆石子剩的越多,先手玩家获胜的概率越大。这直接引出了一个非常感性的结论:每次取石子时要么取一堆…...

Qgis中进行Shp和Excel属性连接实现百强县公共预算空间分析
前言 在之前的博文中,将2022的全国百强县一般公共预算收入的数据下载到了本地,博客原文地址:一种使用Java的快速将Web中表格转换成Excel的方法。对于不关注时空位置关系的一般分析,到此也就基本够用了。但是,如果站在全…...
ES6 新增的循环方法
在 ES6(ECMAScript 2015)中,新增了一些循环方法,这些方法可以帮助我们更方便地遍历数组、字符串、Set、Map 等数据结构。本文将介绍一些常用的 ES6 循环方法。 for…of 循环 for…of 循环是一种遍历可迭代对象的方法,…...

移动端事件300ms延迟解决
有移动端与PC端的项目开发,那么移动端和PC端开发上是存在差异的,比如 click 事件的300ms 延迟,即移动Web页面上的click事件响应都要慢上300ms,移动设备访问Web页面时往往需要 “双击” 或者 “捏开” 来放大页面看清页面的具体内容…...

NRF52832的DFU
开发环境: Winsodw:10 nRF5_SDK:17.1.0 1 工具安装 1.1 gcc-arm-none-eabi Downloads | GNU Arm Embedded Toolchain Downloads – Arm Developer 下载“gcc-arm-none-eabi-10.3-2021.10-win32.exe”,接提示安装。注意安装完…...

开源WebRTC库放大器模式在采集桌面图像时遇到的DPI缩放与内存泄漏问题排查
目录 1、在非100%的显示比例下放大器采集到的桌面图像不全问题 1.1、通过manifest文件禁止系统对软件进行缩放 1.2、调用SetThreadDpiAwarenessContext函数,禁止系统对目标线程中的窗口进行缩放 1.3、使用winver命令查看Windows的年月版本 2、使用放大器模式遇…...
敲黑板!java反射机制和原理
获取Class对象:首先,你需要获取表示要操作的类的Class对象。可以使用以下三种方式之一来获取Class对象: Class.forName()方法:使用类的全限定名获取Class对象,例如:Class<? Class<?> clazz MyC…...

【大数据工具】HBase 集群搭建与基本使用
HBase 集群搭建 HBase 安装包下载地址:https://archive.apache.org/dist/hbase/ 安装 HBase 的前提: ZooKeeper 集群 OKHadoop 集群 OK 1. HBase 集群安装 1. 将 HBase 软件包上传至 Hadoop0 解压并重命名 使用 FileZilla 将 hbase-1.3.1-bin.tar.g…...

【Java】数组详解
文章目录 一、数组的基本认识1.1 数组的概念1.2数组的创建与初始化1.3 数组的使用 二、数组的类型 — 引用类型2.1 JVM 内存分布2.2 什么是引用类型2.3 基本类型变量与引用类型变量的区别2.4 Java 中的 null 三、数组的应用3.1 保存数据3.2 函数参数3.3 函数返回值 一、数组的基…...

NumPy库的学习
本文主要记录的是笔者在B站自学Numpy库的学习笔记。 引入numpy库 import numpy as np矩阵的创建 创建一个二行三列的矩阵。 array np.array([[1,2,3],[2,3,4]])查看array的行数、形状、元素数量 print("number of dim:",array.ndim) print("shape:"…...
CentOS安装IRIS
最近电脑提搞了,可以无顾虑创建虚拟机了,试一下在Linux安装IRIS,适用CentOS7.6上安装Intersystem公司的IRIS数据库,资料基本是空白,分享一下。 首先安装解压软件unzip和libicu,最小化安装的缺,…...

华为OD机试真题 JavaScript 实现【最多几个直角三角形】【2023Q1 100分】
一、题目描述 有 N 条线段,长度分别为 a[1]-a[n]。 现要求你计算这 N 条线段最多可以组合成几个直角三角形,每条线段只能使用一次,每个三角形包含三条线段。 二、输入描述 第一行输入一个正整数 T (1< T< 100) ,表示有…...
vue3中的reactive、ref、toRef和toRefs
目录 reactivereactive的实现原理使用reactive的注意事项 refref的实现原理使用ref的注意事项 toRef和toRefsref和reactive的使用比较 reactive reactive用于创建响应式对象,它返回一个对象的响应式代理。即:它返回的对象以及其中嵌套的对象都会通过 Pr…...
数字图像处理与Python实现-图像增强经典算法汇总
图像增强经典算法汇总 文章目录 图像增强经典算法汇总1、像素变换2、图像逆变换3、幂律变换4、对数变换5、图像均衡化6、对比度受限自适应直方图均衡(CLAHE)7、对比度拉伸8、Sigmoid校正9、局部对比度归一化10、总结本文将对图像增强经典算法做一个简单的汇总。图像增强的经典…...
tag提示词总结
顺序的权重 越靠前的tag权重越大,越靠后的tag权重越小经验来讲,将图像质量相关的tag放在前面,例如masterpiece,best quality等;接着添加主体画风等;最后添加一些不太重要的细节 权重增减 (tag):…...

微信小程序原生开发功能合集二十:导航栏、tabbar自定义及分包功能介绍
本章实现导航栏及tabbar的自定义处理的相关方法介绍及效果展示。 另外还提供小程序开发基础知识讲解课程,包括小程序开发基础知识、组件封装、常用接口组件使用及常用功能实现等内容,具体如下: 1. CSDN课程: https://edu.csdn.net/course/detail/37977 2. 5…...

高通 Camera HAL3:项目开发技术点总结
做高通 Camera HAL3开发的一些技术点的总结、整理。 做个记录,方便后续查阅。 1.目录、so、配置文件 productName是项目名 out Target路径:\out\target\product\productName\chi-cdk:\vendor\qcom\proprietary\chi-cdk\ldc node࿱…...

chatgpt赋能python:Python怎么删除列表中的最大值和最小值
Python怎么删除列表中的最大值和最小值 在Python中,一个列表(List)是一种非常常见的数据结构,它允许我们以有序的方式存储和访问数据。但是,有时候我们需要从列表中删除最大或最小的值,以满足我们的特定需…...

简述Vue的生命周期以及每个阶段做的事情
03_简述Vue的生命周期以及每个阶段做的事情 思路 给出概念 列举出生命周期各个阶段 阐述整体流程 结合实际 扩展:vue3变化 回答范例 每个vue组件实例被创建后都会经过一系列步骤。比如它需要数据观测、模板编译、挂载实例到dom、以及数据变化的时候更新dom、…...
LeetCode-C#-0004.寻找两个正序数组的中位数
0.声明 该题目来源于LeetCode 如有侵权,立马删除。 解法不唯一,如有新解法可一同讨论。 1.题目 0004寻找两个正序数组的中位数 给定两个大小分别为m和n的正序(从小到大)数组nums1和nums2。 请你找出并返回着两个正序数组的中位…...
椭圆曲线密码学(ECC)
一、ECC算法概述 椭圆曲线密码学(Elliptic Curve Cryptography)是基于椭圆曲线数学理论的公钥密码系统,由Neal Koblitz和Victor Miller在1985年独立提出。相比RSA,ECC在相同安全强度下密钥更短(256位ECC ≈ 3072位RSA…...

dedecms 织梦自定义表单留言增加ajax验证码功能
增加ajax功能模块,用户不点击提交按钮,只要输入框失去焦点,就会提前提示验证码是否正确。 一,模板上增加验证码 <input name"vdcode"id"vdcode" placeholder"请输入验证码" type"text&quo…...
测试markdown--肇兴
day1: 1、去程:7:04 --11:32高铁 高铁右转上售票大厅2楼,穿过候车厅下一楼,上大巴车 ¥10/人 **2、到达:**12点多到达寨子,买门票,美团/抖音:¥78人 3、中饭&a…...

DBAPI如何优雅的获取单条数据
API如何优雅的获取单条数据 案例一 对于查询类API,查询的是单条数据,比如根据主键ID查询用户信息,sql如下: select id, name, age from user where id #{id}API默认返回的数据格式是多条的,如下: {&qu…...
AI编程--插件对比分析:CodeRider、GitHub Copilot及其他
AI编程插件对比分析:CodeRider、GitHub Copilot及其他 随着人工智能技术的快速发展,AI编程插件已成为提升开发者生产力的重要工具。CodeRider和GitHub Copilot作为市场上的领先者,分别以其独特的特性和生态系统吸引了大量开发者。本文将从功…...
使用Matplotlib创建炫酷的3D散点图:数据可视化的新维度
文章目录 基础实现代码代码解析进阶技巧1. 自定义点的大小和颜色2. 添加图例和样式美化3. 真实数据应用示例实用技巧与注意事项完整示例(带样式)应用场景在数据科学和可视化领域,三维图形能为我们提供更丰富的数据洞察。本文将手把手教你如何使用Python的Matplotlib库创建引…...

HashMap中的put方法执行流程(流程图)
1 put操作整体流程 HashMap 的 put 操作是其最核心的功能之一。在 JDK 1.8 及以后版本中,其主要逻辑封装在 putVal 这个内部方法中。整个过程大致如下: 初始判断与哈希计算: 首先,putVal 方法会检查当前的 table(也就…...

2025季度云服务器排行榜
在全球云服务器市场,各厂商的排名和地位并非一成不变,而是由其独特的优势、战略布局和市场适应性共同决定的。以下是根据2025年市场趋势,对主要云服务器厂商在排行榜中占据重要位置的原因和优势进行深度分析: 一、全球“三巨头”…...

浪潮交换机配置track检测实现高速公路收费网络主备切换NQA
浪潮交换机track配置 项目背景高速网络拓扑网络情况分析通信线路收费网络路由 收费汇聚交换机相应配置收费汇聚track配置 项目背景 在实施省内一条高速公路时遇到的需求,本次涉及的主要是收费汇聚交换机的配置,浪潮网络设备在高速项目很少,通…...

Linux 内存管理实战精讲:核心原理与面试常考点全解析
Linux 内存管理实战精讲:核心原理与面试常考点全解析 Linux 内核内存管理是系统设计中最复杂但也最核心的模块之一。它不仅支撑着虚拟内存机制、物理内存分配、进程隔离与资源复用,还直接决定系统运行的性能与稳定性。无论你是嵌入式开发者、内核调试工…...