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

P10067 [CCO 2023] Real Mountains

思维训练懒得写代码了,感觉这种题还是思维为重。

我们显然需要考察两个东西:

  1. 最终序列会变成啥样。
  2. 每次是如何一步一步变成最终序列的。

我们先想第一个问题,显然,最终的 \(p\) 一定会是最大的那个 \(a_x\)\(x\),因为将最高的改高一定不优。

优化一下更改操作,每次将一段单调不降的前缀和单调不升的后缀干掉,那么只需要处理中间的值即可。

此时部分分就起到了很关键的作用,考察第二个问题,同样可以拆分成两个问题:

  1. 确定 \(j\) 的情况下,如何选择 \(i, k\)
  2. 如何确定选 \(j\) 的顺序。

显然,考察完第一步是不会影响到第二步的决策的,此时第一步是简单的,选择 \(j\) 两边次小的 \(a_i, a_k\) 所对应的 \(i, k\) 即可。

本题的难点就在考察第二步。

我们仔细思考,发现一定先操作最小值,再操作最大值,否则 \(a_i, a_k\) 就可能会变得更大,影响到了整体的决策。一步一步想到这里,接下来的部分就是简单的了,我们只需要再次考察最小值之间的操作顺序即可,发现为了使得 \(a_i, a_k\) 尽量的小,我们一定是先操作最旁边的两个,中间的随便操作贡献就是一样的,只需要分类讨论一下是先操作左边还是右边即可。

具体过程可以用 set 和主席树维护。

http://www.hskmm.com/?act=detail&tid=31113

相关文章:

  • 先辈题解
  • U-Boot启动探秘:从汇编到命令行的奇幻之旅 - 指南
  • 双指针的初步了解
  • 倍增并查集学习笔记
  • 两数相加-leetcode
  • CF2147E
  • 线程共享区域
  • ZR 2025 NOIP 二十连测 #1
  • 运行时数据区
  • work1
  • 2025 年液压机厂家推荐榜:伺服/小型/大型/数控/液压机厂家口碑推荐,品质可靠 聚焦智能适配,助力企业高效生产
  • 快速上手!山海鲸 4 种高频数据接入方式
  • AI赋能,重塑未来招聘:深度解析易路AI人岗匹配解决方案
  • 2025高级语言程序设计第一次作业lcr
  • luogu 个人主页
  • D230809E. 勇敢的阿乐
  • 解码Linux文件IO之标准IO
  • 10.14 CSP-S模拟31 改题记录
  • 高级程序语言第一次作业
  • 安装devc++过程的分享以及问题的记录
  • Linux之线程池 - 指南
  • zlog1
  • LlamaIndex检索调优实战:分块、HyDE、压缩等8个提效方法快速改善答案质量
  • 动火作业风险早预警!AI + 热成像技术筑牢防火安全线
  • 解题报告-P5664 [CSP-S2019] Emiya 家今天的饭
  • object类
  • Day 10
  • 2025 年生态格宾网厂家推荐榜:格宾网石笼/格宾网护坡/格宾网挡墙/格宾网网箱厂家推荐,聚焦工程安全与生态保护,助力基建项目高效落地
  • 时序博弈算法荣获时间检验奖
  • 背叛 仇恨 消极 如刀子刺穿了铁心 嘲笑 嗤之以鼻 漠然后只剩下孤寂