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