总结：[[2024.11.10 模拟赛]] ## 机械师 II #贪心 #优先队列 #平衡树 > [!quote] 题目背景 > > 机械师一直渴望着去糖果世界看看，她乐观爱笑，为了梦想不畏艰险。 > > 但谁又知道，那传说世界满布蜜糖的背后又是怎样的险恶，她做梦也不会想到，可怕的梦魔也一直期待着她的到来。 机械师正在操纵她的 $m$ 个机械玩偶。 庄园里发生了 $n$ 起事件，第 $i$ 起事件的时间是 $[l_i,r_i)$。只有指派一个机械玩偶在这段时间针对性解决第  起事件（期间这个机械玩偶不能解决其他事件），才可以完成这个事件。 机械师应该怎么指派，才能让完成的事件个数尽可能多？请告诉机械师最多能完成多少事件。 ## 守墓人 > [!quote] 题目背景 > > 当我长眠于此，请勿为我哀歌。 > > 预定一个好位子吧，通往天堂的列车也有一等座。 墓园的地图可以被抽象为一个 $n$ 个点的有根树， 号点为根，树上的每个点代表一个地点。 守墓人将从 $1$ 号点出发，按某个 DFS 序依次访问树上的所有点。 你需要对每个 $(x,y)$ 求出，有多少的 DFS 序使得第 $x$ 个点是守墓人按顺序第 $y$ 个访问到的点。答案对 $10^9+7$ 取模。 ## 慈善家 > [!quote] 慈善家 > > 表情不安，目光躲闪，手电筒照亮的前路似乎充满未知与恐惧。 > > 陈旧且带有补丁的西装，象征着“体面”的工作，却也能隐约透露当前的窘境。 慈善家投资的孤儿院正在修建中！ 孤儿院的建筑轮廓可以看做一个序列 $a$，第 $i$ 个楼的高度为 $a_i$。接下来每次修建如下： - 选择三个整数 $(i,j,k$) 使得 $1\le i<j<k\le n$，满足 $a_j<a_i$ 且 $a_j<a_k$，将 $a_j$ 增加 $1$。 也就是每次可以升高的楼需要满足两侧都有比它更高的楼。 我们对于这样的序列 $a$，记 $f(a)$ 表示其最多可以进行的修建次数。 现在慈善家可以重新规划孤儿院的修建。他可以将序列 $a$ 重排得到序列 $b$，他想知道 $f(b)$ 有哪些可能的取值。 ## 先知 > [!quote] 题目背景 > > 命运将他引向巨大的橡树，给予他启示，又使他沉睡于“无可更改”的终局。 > > 一切关于他的，都在无形之环中消逝，意志、誓约、椋鸟的掠影，概莫能外。 先知正在挑选自己的役鸟。 先知有 $n$ 只役鸟，第 $i$ 只的守护能力为 $a_i$。 先知将会挑选两只役鸟，分别为主役鸟 $x$ 和副役鸟 $y$。为了防止守护能力悬殊，两只役鸟的守护能力需要满足以下条件： $ \left\lfloor\cfrac{a_x}{2}\right\rfloor\le a_y<a_x $ 一组役鸟的综合守护能力定义为两只役鸟的守护能力之和。 现在先知会进行 $m$ 次询问，每次给定两个区间 $[l_1,r_1]$ 和 $[l_2,r_2]$，你需要在 $[l_1,r_1]$ 区间内挑选主役鸟，在 $[l_2,r_2]$ 区间内挑选副役鸟，在满足条件的前提下，最大化综合守护能力。 如果不存在任意一组满足条件的役鸟，则综合守护能力为 $0$。