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

【ACWing】1273. 天才的记忆

题目地址:

https://www.acwing.com/problem/content/1275/

从前有个人名叫WNB,他有着天才般的记忆力,他珍藏了许多许多的宝藏。在他离世之后留给后人一个难题(专门考验记忆力的啊!),如果谁能轻松回答出这个问题,便可以继承他的宝藏。题目是这样的:给你一大串数字(编号为111NNN,大小可不一定哦!),在你看过一遍之后,它便消失在你面前,随后问题就出现了,给你MMM个询问,每次询问就给你两个数字A,BA,BA,B,要求你瞬间就说出属于AAABBB这段区间内的最大数。一天,一位美丽的姐姐从天上飞过,看到这个问题,感到很有意思(主要是据说那个宝藏里面藏着一种美容水,喝了可以让这美丽的姐姐更加迷人),于是她就竭尽全力想解决这个问题。但是,她每次都以失败告终,因为这数字的个数是在太多了!于是她请天才的你帮他解决。如果你帮她解决了这个问题,可是会得到很多甜头的哦!

输入格式:
第一行一个整数NNN表示数字的个数。接下来一行为NNN个数,表示数字序列。第三行读入一个MMM,表示你看完那串数后需要被提问的次数。接下来MMM行,每行都有两个整数A,BA,BA,B

输出格式:
输出共MMM行,每行输出一个数,表示对一个问题的回答。

数据范围:
1≤N≤2×1051≤N≤2×10^51N2×105
1≤M≤1041≤M≤10^41M104
1≤A≤B≤N1≤A≤B≤N1ABN

思路是ST表。预处理一个二维数组ffff[i][j]f[i][j]f[i][j]指的是max⁡A[i:i+2j−1]\max A[i:i+2^j-1]maxA[i:i+2j1]。这样f[i][0]=A[i]f[i][0]=A[i]f[i][0]=A[i],而f[i][.>0]f[i][.>0]f[i][.>0]可以递推得出:f[i][j]=max⁡{f[i][j−1],f[i+2j−1][j−1]}f[i][j]=\max\{f[i][j-1], f[i+2^{j-1}][j-1]\}f[i][j]=max{f[i][j1],f[i+2j1][j1]}这样在询问的时候,设询问是问max⁡A[l:r]\max A[l:r]maxA[l:r],设m=r−l+1m=r-l+1m=rl+1即区间长度,则可以找到最大的xxx使得2x≤m2^x\le m2xm,这样可以保证f[l][x]f[l][x]f[l][x]f[r−2x+1][x]f[r-2^x+1][x]f[r2x+1][x]所覆盖的区间恰好就是A[l:r]A[l:r]A[l:r],并且由于2×2x>m2\times 2^x>m2×2x>m,所以不会超出边界。所以max⁡A[l:r]=max⁡{f[l][x],f[r−2x+1][x]}\max A[l:r]=\max\{f[l][x],f[r-2^x+1][x]\}maxA[l:r]=max{f[l][x],f[r2x+1][x]}xxx可以直接调用数学库里的log⁡\loglog函数计算。代码如下:

#include <iostream>
#include <cstring>
#include <cmath>
using namespace std;const int N = 2e5 + 10, M = 19;
int n, m;
int f[N][M];int main() {scanf("%d", &n);for (int i = 1; i <= n; i++) scanf("%d", &f[i][0]);for (int j = 1; j < M; j++)for (int i = 1; i + (1 << j) - 1 <= n; i++)f[i][j] = max(f[i][j - 1], f[i + (1 << j - 1)][j - 1]);scanf("%d", &m);while (m--) {int l, r;scanf("%d%d", &l, &r);int k = log(r - l + 1) / log(2);printf("%d\n", max(f[l][k], f[r - (1 << k) + 1][k]));}return 0;
}

预处理时间复杂度O(n)O(n)O(n),每次询问时间O(1)O(1)O(1),空间O(nlog⁡n)O(n\log n)O(nlogn)

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

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

C语言中的整型提升

C语言中的整型提升 提到整型提升,可能刚学c语言的小伙伴们很头疼这个知识点吧,下面我就我的理解简单分析一下整型提升是怎么回事. 首先还是介绍一下整型提升的概念: ​ c的整型算术运算总是至少以缺省整型类型的精度来进行的. 为了获得这个精度,表达式中的字符和短整型操作数在…...

Dubbo(一)项目架构演变过程

Dubbo&#xff08;一&#xff09;项目架构演变过程架构演变过程单体架构垂直架构SOA&#xff08;分布式架构&#xff09;微服务架构架构演变过程 dubbo是一款高性能的java rpn框架。 随着互联网的发展&#xff0c;用户群体逐渐壮大&#xff0c;网站的流量成倍增长&#xff0c;…...

Nuxt 项目完结总结

1、状态保存&#xff0c;即localstorage。 这里选择了 nuxt-vuex-localstorage&#xff08;^1.3.0&#xff09; 来做store的持久化保存。 modules: [nuxtjs/style-resources,nuxtjs/axios,[nuxt-vuex-localstorage,{localStorage: [localStorage]}] ] 2、登录token保存&…...

浅入浅出实现一个异步求和函数

简化&#xff1a;两数之和 我们先来简单的实现一个异步两数之和函数 function sumT(a, b) {return await new Promise((resolve, reject) > {asyncAdd(a, b, (err, res) > {if(!err) {resolve(res)}reject(err)})}) }// 测试 const test await sumT(1, 2) console.log…...

入门图形学:屏幕波爆特效

最近bilibili看了黑神话悟空的UE5演示视频&#xff0c;感觉是真牛逼&#xff0c;地址&#xff1a;黑神花悟空UE5实机演示视频 遥想我也算是国内第一批用ue4的开发者了&#xff0c;15年开始用ue4.7源码版&#xff0c;做了一年多就又用回u3d了&#xff0c;哈哈&#xff0c;主要因…...

unity学习笔记(一)

unity基础简介&#xff08;一&#xff09; unity是如何跨平台的&#xff08;附c和c#编译过程&#xff09; 前言 游戏引擎为了兼顾易用性和性能&#xff0c;往往使用一种高效率语言编写核心&#xff0c;使用另一种高级语言作为脚本语言&#xff0c;大部分游戏引擎的底层核心由…...

浮动布局,定位布局,伸缩盒布局

布局 默认文档流 1.元素显示的顺序和代码的顺序是一致的 2.块级元素独占一行空间&#xff0c;默认宽度为父元素的100%&#xff0c;高度由内容或者子元素决定 3.行内元素共享一行空间&#xff0c;默认宽高都由内容决定 浮动布局 float&#xff08;如果一个元…...

Python大数据分析学习基础篇(3)——数据结构

一、函数部分 1、闭包 所谓闭包其实跟回调函数有有相通之处。闭包可以延长作用时间和作用域。 def say(word):def name(name):print(word,name)return name hi say(你好) hi("小明") bye say("再见") bye("小明 ") 运行结果&#xff1a; …...

SQL 之共同使用ip用户检测问题【自关联问题】-HQL面试题48【拼多多面试题】

目录 0 问题描述 1 数据分析 2 小结 0 问题描述 1 数据分析 (1)数据准备 create table log (uid string,ip string,time string )row format delimited fields terminated by \t;insert into log values (a, 124, 2019-08-07 12:0:0), (a, 124, 2019-08-07 13:0:0), (b, 1…...

thinkphp6 通过命令行快速生成多应用模块报 【Command “build“ is not defined.】错误的解决办法

在项目下执行如下命令 php think build admin报如下错误 [rootlocalhost orange]# php think build admin[InvalidArgumentException] Command "build" is not defined. 解决办法&#xff1a; 1.查看官方文档&#xff1a; https://www.kancloud.cn/manual…...

线程的安全性 - 并发基础篇

简介 当多个线程访问某个类时&#xff0c;这个类始终都能表现出正确的行为&#xff0c;那么就说这个类是线程安全的。 目录 这次分三步走&#xff1a;关于相关知识点&#xff0c;放在文末的脑图里了&#xff0c;大家想看结论的&#xff0c;可直接下拉观看哦。 1.创建一个线…...

栈?队列?Java ArrayDeque常用首尾操作方法整理

对于用Java刷leetcode的同学一定很眼熟ArrayDeque这个数据结构&#xff0c;因为它既可以作为队列也可以作为栈&#xff0c;解题时使用频率很高。补充一嘴&#xff0c;Stack也能作为栈来用&#xff0c;但是作为存在设计缺陷的Vector类的子类&#xff0c;已经不推荐使用了。 Arr…...

开发程序流程

JavaWeb程序--> 将一个请求路径( 网络地址) 变成一条sql语句&#xff0c;发送给数据库进行查询&#xff1b; 会将获取的数据&#xff0c;通过页面的方式&#xff0c;展示给用户进行操作&#xff1b; Javaweb程序如何将一个路径变成一条sql语句&#xff1f;...

从入门到放弃:Markdown中的LaTeX使用教程

LaTeX CSDN不支持显示的语法我已用 标注显示 基本语法 展现形式 在正文中的LaTeX公式用$...$定义行内公式&#xff0c;$$...$$单独居中显示 希腊字母 显示命令显示命令α\alphaβ\betaγ\gammaδ\deltaε\epsilonζ\zetaη\etaθ\thetaι\iotaκ\kappaλ\lambdaμ\muν\…...

----- ElasticSearch -----

1.什么是RestFul 2.什么是全文检索 3.什么是Elastic Search 开源 Apache Lucen 工具包 java api特别多 solr 全文检索服务器 底层封装了lucene ElasticSearch 开源搜索引擎 java 4.ES中基本概念 1&#xff09;接近实时(NRT Near Real Time 2&#xff09;索引(index) 3&am…...

39.【Axure 10 】交元件(元件组)交互事件

鼠标相关交互事件 【高】单击时 元件(元件组)的是鼠标单击事件&#xff0c;可以实现鼠标单击的触发的交互事件。 【中】双击事件 元件(元件组)的是鼠标双击事件&#xff0c;作为触发条件。同时也是双击页面任何地方可触发。 【中】鼠标右击事件 元件(元件组)的鼠标右击是…...

PO / PO和 ERP的配置

一、前言 PO / PI 是SAP公司的一个中间件产品&#xff0c;用来辅助SAP系统和外围系统&#xff0c;( 当然外围系统也可以使用PO)。 PO可以完成一些数据内容转换,群发(一份数据发给多个异构系统),分发(数据区分特征发送给特定的系统)等功能. 二、ERP端 ERP和 PO的连接&#x…...

array_search() 在数组中搜索给定的值,如果成功则返回相应的键名

实例 在数组中搜索键值 "red"&#xff0c;并返回它的键名&#xff1a; <?php $aarray("a">"red","b">"green","c">"blue"); echo array_search("red",$a); ?>输出 a 如果…...

不断提升自己创造溢价的能力,附带学习经验

开头 互联网时代的到来&#xff0c;让我们获取知识变得更加简单&#xff0c;理论上讲只要你想学&#xff0c;便会有不尽的知识等你&#xff0c;只要方法得当&#xff0c;够努力&#xff0c;任何人都可以都有可能成为大牛。 自己在努力的基础上&#xff0c;还学习了一些高效的…...

从入门到精通!一个三非渣本的Android校招秋招之路,终局之战

前言: 本文收集整理了各大厂常见面试题N道&#xff0c;你想要的这里都有内容涵盖&#xff1a;Java 相关、Android 基础、Android Framework、三方源码、算法与数据结构、等技术栈&#xff0c;希望大家都能找到适合自己的公司&#xff0c;开开心心的撸代码。 实现方案 直接依…...

js音乐播放器

场景 &#xff1a;如果只是前端用的话&#xff0c;估计不需要多讲&#xff0c;我的运用场景是“后台推送语音提示” 我的使用方式 :当接受的WebSocket的时候播放他 <audio src"https://www.cbdaojia.com//yuyin/语音1 .mp3" id"music2"></au…...

string应用

将’a’从字符串s1中全部删除 s1.erase(std::remove(s1.begin(), s1.end(), a), s1.end());string s(b,e); //以区间b,e内的字符作为字符串s的初值 string s4(s3.begin(),s3.begin()5);...

个人技能点(郎)

个人技能点1. 熟悉 h5 和 c3 新特性&#xff1a;语义化标签&#xff0c;flex 布局&#xff0c;动画等H5 新特性&#xff1a;2. 熟悉js作用域、原型、事件轮询机制、闭包等原理&#xff1b;js 作用域闭包事件轮询机制原型3. 熟悉 ES6 语法标准 promise&#xff0c;async/await 异…...

微信小程序从云开发到上线

文章目录一、创建项目二、云函数三、静默登录四、获取用户信息五、使用缓存六、同页面数据操作七、不同页面数据传递八、页面跳转九、检查版本更新十、上线​ 前段时间自己做了一个云开发微信小程序&#xff0c;发现并不复杂&#xff0c;有前端基础的可以试一下。这里主要简单说…...

P4173 残缺的字符串

P4173 残缺的字符串 题意&#xff1a; 有A&#xff0c;B两个串&#xff0c;每个串都有通配符&#xff0c;问A为模板串&#xff0c;对于 B 的每一个位置 i&#xff0c;从这个位置开始连续 m 个字符形成的子串是否可能与 A 串完全匹配&#xff1f; 题解&#xff1a; 我们定义…...

祥云杯部分pwn的wp

lemon 主要问题是2.26版本下, 未控制好指针导致任意写 数据结构如下: lemon_name: lemon_content: 主要可利用的函数是color: 里的buf是指lemon_name结构, 所以可以控制指针lemon_addr的指向了, 因为只能用一次所以想控制整个tcache结构 其它一点可利用的函数: 开头的一次…...

OverScroll介绍

OverScroll OverScroll作用 首先&#xff0c;OverScroll虽然内置了很多看起来像执行滑动效果的方法名&#xff0c;比如startScroll(int, int, int, int),springBack(int, int, int, int, int, int)等等&#xff0c;但是他们并不实际执行滑动效果&#xff0c;只是用于辅助计算…...

TensorFlow项目1——鸢尾花识别(来源:北大曹健老师tensorflow学习视频)

项目1.鸢尾花识别 1.完整代码 import matplotlib.pyplot as plt from sklearn import datasets from pandas import DataFrame import pandas as pd import numpy as np import tensorflow as tf# 数据处理 #1.读取iris数据&#xff08;sklearn已有&#xff09; #2.随机打乱&…...

1.5 异常

什么是异常 异常就是在程序运行期间&#xff0c;因为某些原因导致程序出现了错误的情况。 异常封装了三个重要信息: 类型&#xff0c;信息&#xff0c;行号 异常的简单继承结构 Throwable |- Error 系统级别的错误&#xff0c;无法处理&#xff0c;只能停止运行 |- Excepti…...

使用朴素贝叶斯过滤垃圾邮件

示例&#xff1a;使用朴素贝叶斯对电子邮件进行分类(1) 收集数据&#xff1a;提供文本文件。(2) 准备数据&#xff1a;将文本文件解析成词条向量。 (3) 分析数据&#xff1a;检查词条确保解析的正确性。(4) 训练算法&#xff1a;使用我们之前建立的trainNB0()函数。(5) 测试算法…...

详解 Spring Boot 项目中的日志文件

目录 1. 日志的作用 2. 自定义日志打印 2.1 日志的基本格式 2.2 得到日志对象 2.3 使用日志对象提供的方法&#xff0c; 打印自定义的日志内容 2.4 日志框架的说明 3. 日志的持久化 3.1 配置日志文件的文件名 3.2 配置日志文件的保存路径 3.3 持久化日志的特性 4. 日…...

平面设计转前端,啥都不会怎么办?

毕业三年&#xff0c;干了3年平面设计。现决定转行学习前端&#xff0c;寻求外单。 在我眼中技术类型的事情就是分为三大块 &#xff0c;一&#xff1a;理论 二&#xff1a;软件 三&#xff1a;平台 你会发现只要你是从事互联玩相关的任何行业这三种是必不可少的。 一&#xf…...

平面设计点线面在设计中的运用

本文由&#xff1a;“学设计上兔课网”原创&#xff0c;图片素材来自网络&#xff0c;仅供学习分享 平面设计点线面在设计中的运用&#xff0c;点、线、面是平面构成中最基础的要素&#xff0c;就是在同一个平面空间内,主角和配角元素组合&#xff0c;让配角有效的衬托主角&am…...

深度学习常见网络结构和设计思路总结(期末复习)

前言 该文的主要原因是深度学习期末开卷考试&#xff0c;因此整理了NN&#xff0c;CNN&#xff0c;RNN&#xff0c;GAN各个网络模型原理和相关知识。 并且对如何设计一个神经网络提出相关讨论&#xff0c;以及神经网络中损失函数&#xff0c;优化算法等也举例&#xff0c;希望…...

平面设计学习网

http://www.68pslm.com/...

Python 安装pandas模块

pandas Python Data Analysis Library 或 pandas 是基于NumPy 的一种工具&#xff0c;该工具是为了解决数据分析任务而创建的。Pandas 纳入了大量库和一些标准的数据模型&#xff0c;提供了高效地操作大型数据集所需的工具。pandas提供了大量能使我们快速便捷地处理数据的函数和…...

《模拟电子技术》半导体原理部分笔记

《模拟电子技术》笔记绪论第一章 常用半导体器件第二章 基本放大电路绪论 有的人把三极管的出现作为电子技术工业革命的开始标志学习架构&#xff1a;半导体器件&#xff08;二极管、三极管、场效应晶体管&#xff09;、基于上述管的放大电路、集成运算放大器、放大电路的频率…...

毕业设计-基于机器视觉的车型识别系统

目录 前言 课题背景和意义 实现技术思路 实现效果图样例 前言 &#x1f4c5;大四是整个大学期间最忙碌的时光,一边要忙着备考或实习为毕业后面临的就业升学做准备,一边要为毕业设计耗费大量精力。近几年各个学校要求的毕设项目越来越难,有不少课题是研究生级别难度的,对本科…...

Unity3D实现场景跳转方法

一、搭建一个场景&#xff0c;创建Button按钮&#xff0c;在其Inspector版面创建脚本ChangeScene 二、编写ChangeScene脚本&#xff0c;实现场景跳转功能 三、选择菜单栏的File->Build Settings添加场景...

Unity创建超写实三维场景的一般步骤

使用Unity创建三维场景最容易想到的是手动在地形上刷草、刷树等&#xff0c;但是这种方法不仅工作量大&#xff0c;但不真实。最近学习了Gaia插件&#xff0c;发现Gaia用程序自动生成的&#xff0c;感觉这种思想太妙了&#xff0c;World Creator也采用了类似的方法&#xff0c;…...

Unity3D项目之游戏场景小地图制作

Unity3D项目之游戏场景小地图制作 创建一个场景资源&#xff0c;可在asset store资源商店下载&#xff0c;选择心仪场景。 链接:https://assetstore.unity.com/?localezh-CN 添加一个对象GameObject&#xff0c;命名为player,子物体包括&#xff1a;主摄像机&#xff0c;角色…...

QT3D场景快速绘制入门学习

在QT中实现3D绘制的方式&#xff1a; 1) 使用QT OpenGL模块&#xff08;QOpenGLWidget等&#xff09; 2) 使用QT 3D C类&#xff08;QEntity等&#xff09; 3) 使用QT 3D QML类&#xff08;Entity等&#xff09; QT3D场景提供了一种快速设置3D场景的一种方式&#xff…...

Jetson的mavros使用offboard模式,终端按键控制无人机飞行

基于Promethues根据wiki配置好之后可以实现使用终端控制&#xff0c;起飞&#xff1b;降落&#xff1b;前后左右飞行&#xff1b;上升下降左转右转&#xff1b; 开始我基于仿真测试实机不成功&#xff0c;是因为某个运行节点没有打开&#xff0c;仔细看gazebo.launch文件里仿真…...

ue4和Airsim仿真无人机,键盘控制无人机运动

代码 #键盘测试 import keyboard import airsimclient airsim.MultirotorClient() client.confirmConnection()def abc(x):w keyboard.KeyboardEvent(down, 28, w)s keyboard.KeyboardEvent(down, 28, s)a keyboard.KeyboardEvent(down, 28, a)d keyboard.KeyboardEvent(…...

Unity工具 - 工具聚合页(UEWindow)

随着项目工程的推进&#xff0c;开发者们会根据工作内容的需要在Unity内开发众多的工具。随着工具的增多&#xff0c;Unity 的Menu菜单也会逐渐臃肿&#xff0c;过于分散&#xff0c;工具代码也难以查找。在此问题的基础上&#xff0c;开发了工具聚合页(UEWindow) 这一功能来管…...

无人机相关知识解读

目录 1.什么是云台&#xff1f; 2.云台的工作原理&#xff1f; 3.无人机吊舱是什么&#xff1f; 4.什么是无人机&#xff1f; 5. 无人机都有哪些&#xff1f; 6.什么是多旋翼无人机&#xff1f; 7.什么是直升机无人机&#xff1f; 8.什么是固定翼无人机&#xff1f; 9…...

客户关系管理(增删查改)

完整项目代码: 第一次使用mvc设计模式开发项目&#xff0c;是一个功能简单的项目&#xff0c;业务层service的功能也很少。 需要用到的jar包&#xff1a; 直接上代码 链接&#xff1a;https://pan.baidu.com/s/1cNCUvQBWY_NGiJT4FRX2qw 提取码&#xff1a;kak7 CustomerServ…...

[附源码]计算机毕业设计基于SpringBoot的小说阅读系统

项目运行 环境配置&#xff1a; Jdk1.8 Tomcat7.0 Mysql HBuilderX&#xff08;Webstorm也行&#xff09; Eclispe&#xff08;IntelliJ IDEA,Eclispe,MyEclispe,Sts都支持&#xff09;。 项目技术&#xff1a; SSM mybatis Maven Vue 等等组成&#xff0c;B/S模式 M…...

七、创业谈话记录

曾在创业公司工作&#xff0c;亲身参与公司的各个方面活动&#xff0c;习惯做笔记&#xff0c;将记录和体会整理成的杂记&#xff0c;没有进行严格分类&#xff1b; 往期文章&#xff1a; 简析创业 创业知识域 一、在创业公司的一些经历思考、讨论、常见问题以及解决 — 创业…...

客户资料用得好,客户跑不了!

在现代企业管理中&#xff0c;客户资料管理过程仍存在诸多问题&#xff1a; 1.早期的客户资料登记不规范&#xff0c;导致信息很杂乱。客户资料的分类不够科学&#xff0c;导致很多该跟进的客户跟进不及时。 2.记录的客户资料过于分散&#xff0c;信息不够全面&#xff0c;想…...