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 用了线段树优化,拼起来的时候用到了二分。