关于信息学奥赛中的一些做题思路

这篇具有很好参考价值的文章主要介绍了关于信息学奥赛中的一些做题思路。希望对大家有所帮助。如果存在错误或未考虑完全的地方,请大家不吝赐教,您也可以点击"举报违法"按钮提交疑问。

观前须知

Sugar_Cube的博客园主页

背景介绍

本文记录了笔者在刷题或比赛中运用到的一些做题思路
可以适当参考

正文

Luogu P2048 超级钢琴

首先显然有 \(\mathcal {O}(n^2)\) 暴力枚举每个子段,然后选择其中前k大的
那么可以发现有贪心策略:
选择k次最大值
那么考虑怎样求最大值
想到可以枚举每个起始位置,想办法计算从该位置开始符合要求的字段最大值
将字段长度符合要求转换为终止位置在区间内
由于连续,记前缀和 \(sum_i\)
则对于一个三元组 \((lx,l,r)\) 表示从 \(lx\) 起始,合法终止位置在 \([l,r]\) 区间内
它的最优答案是 \(max\{sum_t-sum_{lx-1} | t\in [l,r] \}\)
\(max\{sum_t | t\in [l,r] \} - sum_{lx-1}\)
求最大的 \(sum_t\) 不就是一个RMQ问题吗
注意到,一个起始位置算完后,仍然有别的终止位置可以使用
则分裂原三元组为 \((lx,l,t-1)\)\((lx,t+1,r)\)
并将新的三元组放到中继续维护最大值

细节:
为了计算 \(t\) 要在st表中维护最大值对应的下标
注意判新的三元组的合法性

一句话思路:
暴力->贪心->求最大值->计算子段和->RMQ->分裂三元组用堆维护文章来源地址https://www.toymoban.com/news/detail-839337.html

到了这里,关于关于信息学奥赛中的一些做题思路的文章就介绍完了。如果您还想了解更多内容,请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章,希望大家以后多多支持TOY模板网!

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处: 如若内容造成侵权/违法违规/事实不符,请点击违法举报进行投诉反馈,一经查实,立即删除!

领支付宝红包 赞助服务器费用

相关文章

  • 关于特殊时期电力行业信息中心运营思路

    安全运营是一系列规则、技术和应用的集合,用以保障组织核心业务平稳运行的相关活动,是通过灵活、动态的实施控制以期达到组织和业务需要的整体范围可持续性正常运行。信息中心在特殊时期扮演着关键的角色,因此需要精心设计运营思路以确保信息安全。以下是我们

    2024年02月09日
    浏览(50)
  • 关于文章《爬取知网文献信息》中代码的一些优化

    哈喽大家好,我是咸鱼   之前写了一篇关于文献爬虫的文章 Python爬虫实战(5) | 爬取知网文献信息   文章发布之后有很多小伙伴给出了一些反馈和指正,在认真看了小伙伴们的留言之后,咸鱼对代码进行了一些优化   优化的代码在文末,欢迎各位小伙伴给出意见和指正   p

    2023年04月27日
    浏览(52)
  • 一些关于Aleo项目的误解和常见的试错信息

    在现实生活中,你不会因为买了一杯咖啡而被人知道你有多少财富,但在区块链世界,你可能会因为在opensea上买了一个便宜的NFT而被人发现你的钱包地址、所有转账信息以及钱包里的所有财富。如果被不怀好意的人或一些恶意的黑客盯上,你可能就会受到攻击,遭受很大的损

    2024年02月06日
    浏览(43)
  • 信息学竞赛中的一些调试方法

    本文包含了笔者及其同学再模拟赛或正式比赛中出现的问题 继承了笔者曾在dl24jp oj上发布的 警钟撅烂 系列 警钟长鸣~ 数组下标越界,stl.empty 函数记得写返回值 手写队列算好长度 数组注意开2倍 递归记得写边界 循环迭代和退出条件 函数内变量记得初始化 对于部分数据结构

    2024年03月09日
    浏览(35)
  • 关于嵌入式开发的一些信息汇总:嵌入式C开发人员、嵌入式系统Linux

    这篇文章是关于嵌入式开发的一些基本信息,供想入行的人参考。有一些作者本人的想法,以及来自外网的大拿的文章翻译而来,原文链接在此Learning Linux for embedded systems,再次感谢,支持原创。 普通C开发人员和嵌入式C开发人员之间的 基本区别在于 ,因为嵌入式C程序被设

    2024年02月03日
    浏览(70)
  • 关于 yarn.lock 在实际项目中的一些作用

    在实际项目中我们如果想正确使用 yarn.lock , 有必要了解什么是锁定文件以及它是如何工作的。尽管根据您使用的是 npm 还是 yarn 可以有不同的名称,但前提几乎相同。笔者从事 SAP Spartacus 开发中使用的是 yarn,所以我将在本文中使用 yarn.lock 作为示例。 当您在项目中运行 yar

    2024年02月12日
    浏览(30)
  • 关于java中的多态和对实例化对象的一些理解

    java面向对象三大特征即为:继承封装多态。而多态需要三大必要条件。分别是:继承、方法重写、父类引用指向子类对象。我们先一个一个来理解。 1、首先是继承和重写。这个很简单。因为多态就是建立在不同的重写之上的。也就是说多态就是在使用着一个方法的不同重写

    2024年02月02日
    浏览(39)
  • 《信息学奥赛一本通 提高篇》

    提高篇 第一部分 基础算法 第1章 贪心算法 提高篇 第一部分 基础算法 第1章 贪心算法_青少年趣味编程-CSDN博客 提高篇 第一部分 基础算法 第1章 贪心算法 提高篇 第一部分 基础算法 第1章 贪心算法_青少年趣味编程-CSDN博客 信息学奥赛一本通 提高篇 第一部分 基础算法 第2章

    2024年02月16日
    浏览(46)
  • 开发中的花样玩法(前端打工人须知)

    目录 一、关于vue使用vant的van-popup,子元素设定固定定位失效问题。 二、当浏览器因为有缓存导致页面新增内容不生效的问题解决方法 三、代码的另类写法 四、解决git项目中文件夹首字母改成大写后在远程出现两个文件夹的问题 五、chrome 源代码调试快捷键 六、父组件获取

    2024年02月13日
    浏览(46)
  • 信息学奥赛一本通【1302】股票买卖

    信息学奥赛一本通1302 1302:股票买卖 时间限制: 1000 ms 内存限制: 65536 KB   【题目描述】 最近越来越多的人都投身股市,阿福也有点心动了。谨记着“股市有风险,入市需谨慎”,阿福决定先来研究一下简化版的股票买卖问题。 假设阿福已经准确预测出了某只股票在未来N天的

    2024年02月05日
    浏览(39)

觉得文章有用就打赏一下文章作者

支付宝扫一扫打赏

博客赞助

微信扫一扫打赏

请作者喝杯咖啡吧~博客赞助

支付宝扫一扫领取红包,优惠每天领

二维码1

领取红包

二维码2

领红包