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

NOISG 2025 Prelim

NOISG 2025 Prelim

评分 \(\in[0,10]\)

https://www.luogu.com.cn/problem/list?type=luogu&page=1&tag=436|62

Train Or Bus

\(1\)

\(\sum_{i=1}^n \min(a_i,b_i)\),原因显然。

Ducks And Buttons

\(2.5\)

\(d\) 没有用。

至少要派 \(a_i\) 只鸭子去 \(i\),那么肯定会经过 \(2\sim i-1\),路途中 \(a_j<a_i\)\(j\) 会被 \(i\) 支配,做一遍后缀最大值加起来就行了。

Snacks

\(3.5\)

颜色段均摊,拿一个 set 搞一搞就行了,复杂度均摊正确。

Itinerary

\(5\)

先对相邻的关键点的路径在树上进行链 \(+1\)

\(i\) 为根时,合法当且仅当将 \(i\) 到第一个关键点的路径链 \(+1\) 后,每条边的被加的次数均 \(\le 2\)

可以用树链剖分维护。

怎么去想到这个东西?

上述过程相当于抛弃了一些边,只把关键点之间以及根和第一个关键点之间路径上的边进行了考虑,因为其他边只要不作死就一定是不会让这个情况不合法的。

题目也是抽象,一个点会经过两次,而合法的判断只需要关键点序列是巡游序列的子序列就行了,为什么不钦定第一次经过才算呢,说明有转化,这是值得推敲的。

Lasers 2

\(6\)

首先发现这题二维是骗人的,实际上就是一个一维的线段问题。

\(k\) 达到了 \(10^9\) 级别,所以可以毙掉把“当前花费了多少”放进 dp 状态里的想法。

那怎么设计 dp,可以交换结果和状态,即可以这样设计:选定了 \(x\) 列激光不被阻挡的情况下的最小花费。

将小的线段移到大的线段中直至被包含,可以消除小的线段的影响。

这有什么启示?可以枚举一个长度为 \(\max_i (r_i-l_i+1)\) 的窗口(可以琢磨一下为什么这样一定是对的,假设解锁了最长线段,那么这个没问题;反之,可以都放到最长线段里,这是不影响的,如果最优策略真是这样,那么等窗口刚好枚举到这个最长线段上也没有问题,这是这题一个比较有价值的地方)。

接着,将之前为了选定 \(x\) 列激光不被阻挡而去解锁的线段放到窗口里,就当作消去了影响。

那么可以前后缀分别做一遍 dp,然后拼起来就行了。

在我的实现里,dp 用了线段树优化,拼起来的时候用到了二分。

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

相关文章:

  • STM32 教程
  • 先进反应堆:BWRX-300
  • ch58x/ch59x系列芯片Indication添加
  • Lab 4 Challenge - Sum of Proper Elements
  • perl经典hash解决问题
  • LCR 129. 字母迷宫
  • Ignite3 竟然变成分布式数据库了!
  • NUIST 《程序设计基础》 实验1
  • 10.9总结
  • [MIT 6.828] Lab 1 C, Assembly, Tools, and Bootstrapping
  • WCH低功耗蓝牙系列芯片usb烧录故障排查
  • 使用docker构建.net api镜像及nginx反向代理 - binzi
  • 利用sprintf与snprintf巧妙实现数值变量转换为字符串型
  • Helmholtz-Gibbs自由能与熵弹性
  • 日志|电话号码的字母组合|子集|回溯
  • Docker实用篇(初识Docker,Docker的基本操作,Dockerfile自定义镜像,Docker-Compose,Docker镜像仓库) - a
  • ROIR 2023
  • Rust 的验证码图像识别系统设计与实现
  • 【题解】P12992 [GCJ 2022 #1C] Intranets
  • ysyx:pa3.1批处理系统
  • C 语言的验证码图像识别系统实现
  • Nginx典型流控配置示例
  • 基于 C 语言的验证码图像识别系统实现
  • oppoR9m刷Linux系统: 引导知识
  • 操作系统知识点
  • JAVA: Mybatis添加xml执行多行更新语句时报错
  • 安装Docker(CentOS安装Docker,CentOS7安装DockerCompose,Docker镜像仓库) - a
  • 上代码演示下Profile-Guided Optimization (PGO)
  • 所有文档每页的第一行居中对齐
  • 109