Codeforces Round 919 (Div. 2) D题 偏移量,二分,子问题

Problem - D - Codeforces

题意:

用两种方式制作一个很大的数组,然后查询对应下标对应的数字。

难点:

制作的方式有复制n次原数组接到后面,样例的数据很大,很快就会溢出unsigned long long。暴力做出这个数组是不可以的。

细节:

查询的大小不会超过1e18,所以我们超过上限的不进行记录了。

方法:

我们用记录数字偏移量的方法。查找时找对应偏移量即可。->代码上我们记录操作,计算这次操作末尾的偏移量,这样查找的话可以用二分查找,很快就能找到是哪次操作的位置。

为什么要这么做:

因为是对应数字的偏移量,那么这个位置就是这个数字

如果这个位置是复制操作,我们取余就可以得到复制前的偏移量,得到的数字也是这个数字。(如果前面还是复制操作呢? ->其实就是子问题啦)

————

根据题目第一个样例做解释:

(pos数组是偏移量,options数组就是操作类型,val数组就是操作的值)

代码:注意看对超过1e18位置的处理:

#define ll unsigned long long
const ll inf = 1e18;
void solve()
{ll n, q;cin >> n >> q;vector<ll>pos;//偏移量vector<ll>val;vector<ll>options;for (ll i = 0; i < n; i++){ll op, num; cin >> op >> num;options.push_back(op);val.push_back(num);if (op == 1){if (pos.size() == 0)//第一次pos.push_back(1);else{pos.push_back(pos[i - 1] + 1);}}else{//查询不会查老后面,但是前面操作会超出if ((inf) / num < pos[i - 1]) //#### 这里是对超过1e18的处理,inf加个num向上取整更合适,不过这里也可以过pos.push_back(inf + 5);elsepos.push_back(pos[i - 1] * (num + 1));}}for (ll i = 0; i < q; i++){ll num; cin >> num;//ll left = 0, right = pos.size() - 1;while (1){while (left < right)//根据偏移量二分。二分就是找到自己在的对应操作的位置。{ll mid = left + (right - left) / 2;if (pos[mid] >= num)right = mid;else left = mid + 1;}if (options[right] == 1)//!!!偏移量正好对应的是一个数字{cout << val[right] << " ";break;}else//调整位置接着二分(num变了,划成子问题了{ll snum = pos[right - 1];//pos[right] / (val[right]+1);//这次操作的原始数组大小num %= snum;//换到对应位置if (num == 0)num = snum;left = 0;//只会在左边了,再次找}}}cout << endl;
}

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

如若内容造成侵权/违法违规/事实不符,请联系长河编程网进行投诉反馈email:809451989@qq.com,一经查实,立即删除!

相关文章

第7章-第9节-Java中的Stream流(链式调用)

1、什么是Stream流 Lambda表达式&#xff0c;基于Lambda所带来的函数式编程&#xff0c;又引入了一个全新的Stream概念&#xff0c;用于解决集合类库既有的鼻端。 2、案例 假设现在有一个需求&#xff0c; 将list集合中姓张的元素过滤到一个新的集合中&#xff1b;然后将过滤…

【C++】Qt:Qt事件介绍与正弦曲线绘制示例

&#x1f60f;★,:.☆(&#xffe3;▽&#xffe3;)/$:.★ &#x1f60f; 这篇文章主要介绍Qt事件介绍与正弦曲线绘制示例。 学其所用&#xff0c;用其所学。——梁启超 欢迎来到我的博客&#xff0c;一起学习&#xff0c;共同进步。 喜欢的朋友可以关注一下&#xff0c;下次更…

[软件工具][windows]yolov8自动标注工具自动打标签工具

软件截图如下&#xff1a; 这个工具可以自动将图片识别为指定类别并保存为VOC格式xml文件&#xff0c; 软件只支持官方80类别&#xff0c;您可以选择其中一部分或者一部分进行自动标注&#xff0c;标注的效果依据图片而定&#xff0c;通过自动标注您可以减少很多标注工作量&…

制造知识普及--MES系统中的调度排产管理

要想弄清楚MES系统调度排产的管理机制&#xff0c;则要首先搞清楚车间调度排产是一套怎样的工作流程&#xff0c;它的难点在什么地方&#xff1f; 生产调度指的是具体组织实现生产作业计划的工作&#xff0c;是对执行生产作业计划过程中发生的问题和可能出现的问题&#xff0c…

Unity 工具 之 Azure 微软连续语音识别ASR的简单整理

Unity 工具 之 Azure 微软连续语音识别ASR的简单整理 目录 Unity 工具 之 Azure 微软连续语音识别ASR的简单整理 一、简单介绍 二、实现原理 三、注意实现 四、实现步骤 五、关键脚本 一、简单介绍 Unity 工具类&#xff0c;自己整理的一些游戏开发可能用到的模块&#x…

重磅!ESI高被引论文阈值发布

1月11日&#xff0c;科睿唯安&#xff08;Clarivate Analytics&#xff09;公布了最新的ESI数据。 注&#xff1a;ESI的更新时间为每奇数月的第二个星期四。 Essential Science Indicators (ESI) 是一种分析工具&#xff0c;可帮助识别 Web of Science 核心合集中表现最好的研…

Lamp架构从入门到精通

系列文章目录 lnmp架构 lnmp架构-nginx负载均衡以及高可用 系列文章目录一、源码编译configure(检测预编译环境是否可行)makemake install优化关闭Debug 二、 nginx负载均衡三、nginx的高并发nginx work数量的设定nginx work进程与cpu的静态绑定压力测试nginx高并发修改操作系…

Unity使用Protobuf

1.下载Protobuf ProtoBuf 2.打开它并且编译 如果有报错下载相应的.net版本即可 这里默认是6.0.100 由于我本机是8.0.100所以我改了这个文件 3.编译后的文件复制到Unity Assets/Plugins下 4.写个测试的proto文件 5.然后使用protoc生成 这里实现了一个简单的bat批量生成 Protos C…

从0开始学Git指令(3)

从0开始学Git指令 因为网上的git文章优劣难评&#xff0c;大部分没有实操展示&#xff0c;所以打算自己从头整理一份完整的git实战教程&#xff0c;希望对大家能够起到帮助&#xff01; 远程仓库 Git是分布式版本控制系统&#xff0c;同一个Git仓库&#xff0c;可以分布到不…

MySQL体系结构

MySQL体系结构 MySQL采用的是客户/服务器体系结构&#xff0c;实际是有两个程序&#xff0c;一个是MySQL服务器程序&#xff0c;指的是mysqld程序&#xff0c;运行在存放数据库的机器上&#xff0c;负责在网络上监听并处理来自客户的服务请求&#xff0c;根据这些请求去访问数据…

运筹说 第84期 | 网络计划-网络图的基本概念

自华罗庚教授将网络计划技术引入我国&#xff0c;网络计划已取得巨大发展。本期开始&#xff0c;小编将从网络图基本概念、时间参数计算、网络计划优化和图解评审法等方面对网络计划进行系统的介绍。 01前言 20世纪50年代以来&#xff0c;产生了许多计划管理的新方法&#xf…

如何使用Docker一键部署WBO白板并实现固定公网地址远程访问

文章目录 前言1. 部署WBO白板2. 本地访问WBO白板3. Linux 安装cpolar4. 配置WBO公网访问地址5. 公网远程访问WBO白板6. 固定WBO白板公网地址 前言 WBO在线协作白板是一个自由和开源的在线协作白板&#xff0c;允许多个用户同时在一个虚拟的大型白板上画图。该白板对所有线上用…

详解ISIS动态路由协议

华子目录 前言应用场景历史起源ISIS路由计算过程ISIS的地址结构ISIS路由器分类ISIS邻居关系的建立P2PMA ISIS中的DIS与OSPF中DR的对比链路状态信息的交互ISIS的最短路径优先算法&#xff08;SPF&#xff09;ISIS区域划分ISIS区域间路由访问原理ISIS与OSPF的不同ISIS与OSPF的术语…

【Python机器学习系列】建立随机森林模型预测心脏疾病(完整实现过程)

这是Python机器学习系列原创文章&#xff0c;我的第200篇原创文章。 一、引言 对于表格数据&#xff0c;一套完整的机器学习建模流程如下&#xff1a; 针对不同的数据集&#xff0c;有些步骤不适用即不需要做&#xff0c;其中橘红色框为必要步骤&#xff0c;由于数据质量较高&…

【降龙算法】基于QT插件机制实现一个机器视觉算法小框架

机器视觉行业有各种各样的拖拉拽框架&#xff0c;也叫做低代码平台&#xff0c;例如国内海康的VisionMaster&#xff1a; 一个机器视觉框架需要包含各种算法模块&#xff0c;日志窗口&#xff0c;图像显示窗口等等&#xff0c;【降龙算法】就是做了一个入门级的机器视觉算法框…

python贪吃蛇游戏

为了实现这个游戏&#xff0c;需要用到Python的pygame模块&#xff0c;它是一个专门用于开发游戏的模块&#xff0c;提供了很多方便的功能&#xff0c;比如窗口、图形、音效、事件处理等。 用pygame来创建一个窗口&#xff0c;设置游戏的背景色&#xff0c;画出蛇和食物&#…

芯片有关新闻-China chip imports suffer steepest drop on record after US curbs

Jan 16, 2024 9:01 am 由于长期的经济不确定性和美国的出口管制&#xff0c;中国的芯片进口去年遭遇了有记录以来的最大降幅。 全球最大半导体市场的集成电路进口额下降了15.4%&#xff0c;至3494亿美元&#xff0c;这是自2004年中国海关数据公布以来的最大跌幅&#xff0c;并…

目标服务器执行脚本

deploy.sh 为了任何时候都能执行&#xff0c;移动到环境变量 Publish Over SSH deploy.sh 178.119.30.133:80 repo ${JOB_NAME} $tag $port 构建

深入类加载机制及底层

深入类加载机制 初识类加载过程 使用某个类时&#xff0c;如果该类的class文件没有加载到内存时&#xff0c;则系统会通过以下三个步骤来对该类进行初始化 1.类的加载&#xff08;Load&#xff09; → 2.类的连接&#xff08;Link&#xff09; → 3.类的初始化&#xff08;In…

【java八股文】之JVM基础篇

【java八股文】之JVM基础篇-CSDN博客 【java八股文】之MYSQL基础篇-CSDN博客 【java八股文】之Redis基础篇-CSDN博客 【java八股文】之Spring系列篇-CSDN博客 【java八股文】之分布式系列篇-CSDN博客 【java八股文】之多线程篇-CSDN博客 【java八股文】之JVM基础篇-CSDN博…