好难绷的题。
你也许需要先会 E1。猜你喜欢：[CF2150E1] Hidden Single (Version 1) 题解
看到题后似乎只能想到分治，于是想想该怎么分治。
考虑对于 中的每个 ，判断它是不是答案。考虑 ，设中点为 。我们尝试找出 在当前区间内的分布情况（左区间或右区间）。总共分三类情况：
所有 均出现在左区间：有 的概率，需要询问 次。
所有 均出现在右区间：...
看到题后似乎只能想到分治，于是想想该怎么分治。
考虑 ，设中点为 。假定当前区间内存在答案，并且我们知道 中的每个 在这个区间内的出现次数 。特别地，对于答案 ，我们不得不钦定 。对于 中的每个 ，我们尝试找出它在当前区间内的分布情况（左区间或右区间）。于是根据 分讨：
：需要 次询问。直接跳过。
：需要 次询问。只需要询问左区间，即可得到它属于左区间还是右区间。
：最多需要 ...
乍一看感觉很难直接 DP，于是考虑先把限制形式化。设当前选的歌曲形成的集合是 ，因为歌曲的顺序并不影响所选集合的合法性，所以 。考虑简化条件，对于一个固定的 ，要最大化前者，显然只需要取较大的几个 。所以自然想到先将 （连带着 ）降序排序，条件就转化为了 ，记后者为 ，它是可以预处理出来的。可以证明这个条件是充要的，一个感性的理解是，我们取出了原集合的每一个子集并判断其是否合法，具体的证明...
好题。本题解做法与官方题解相同，但将采用类似 CF Hints 的风格。下文中的 均指将两个十进制数进行拼接， 表示 在十进制下的位数，且默认包含前导零。
提示 1
考虑答案的形式。
答案
答案一定是 的形式，其中允许 有前导零。
提示 2
考虑 与 ...
赛时
看到这个题先乱写了一个状压，发现显然没有正确性，然后开始乱推容斥，后面发现自己想复杂了，想到了本文的做法，但是因为太慌了在一直在乱写，调半天没过样例，最后在 85 分钟才做出来，菜死了。
看到 显然状压。首先容易想到设 表示一定出现的蝉种类形成的集合为 的年份数量（没有被选中的蝉不一定出现）， 表示出现的蝉种类形成的集合为 ...
赛时没打这场 ABC。
设 的重儿子是 ，以 为根的子树为 ， 的大小是 ， 中最多能选出 个点对。定义点 是好的，当且仅当 。接下来分点 是不是好的分类讨论：
若点 是好的：显然有 。
若点 不是好的：我们尝试让 成为好的。具体地，我们可以在 中先选取一些点对，并且从 中删去这些点，使得 减小，从而使点 成为好的。在 中最多可以选取 个点对，所以 的最小值是...
鲜花
MX NOIP 模拟赛 T3，补题时只找到了一篇 十年前的日文题解，并且目前洛谷里这道题唯一一个讨论甚至还是提供翻译，并且也是七年前的了。这题真冷门。
下文中，最长上升子序列简写为 LIS，最长下降子序列简写为 LDS。
注意到红色的元素构成了一个单调递增的子序列 ，蓝色的元素构成了一个单调递减的子序列 。在最优情况下，若 恰好是...
Upd. 修了一点笔误。
显然是 DP，并且是稍微想一想就能发现性质的 DP。
首先攻击的形式一定钦定若干个生物，打死这些生物，使得剩下的生物形成若干个堆叠。对于每个堆叠，我们再从下往上依次一个个打死。容易发现，若 是一个独立的堆叠，需要的攻击次数是 ，减一与加一是因为除了第一个生物都会受到 的跌落伤害。设前缀和数组为 ，那么上式就是 。
注意到，为了减少攻击次数，我们会尽量增加摔落伤害...
一眼根号复杂度。
这道题应该有很多做法。我的做法是尝试消掉 ，使得关于 只出现了一次项。
设
那么就可以枚举 解出 ，当 是整数是才是合法解。 是根号级别的，但是为了保险， 的值域可以开大一点。
赛时提交记录，稍微卡了点常，所以写法有点沟槽。应该不卡常就用 set 去重也能过。
看到 就显然分讨了。
Case 1：
此时显然无解。
Case 2：
此时答案即为从 走到 的方案数，即 。
Case 3：
即在 Case 2 的基础上再选一堵墙拆除。发现对于任意一条从 到 的路径，都可以选择其余任意一堵墙拆除。故答案为 。
Case 4：
发现此时又产生了两种情况。一种是路径长度依旧为 ，另一种是路径长度为 。
Case 4.1：路径长度为
即在 ...
