松鼠严选

P1783 海滩防御

传送门

题意简述

给定个点的坐标，横坐标，求以这些点为圆心的圆半径至少为多少才能通过这些圆从横坐标为走到横坐标为的点。

，，，

思路

水题。

我们考虑二分半径，用并查集维护连通性，最后检查左边界和右边界是否连通即可。时间复杂度为。

CF1849E Max to the Right of Min

传送门

题意简述

给定长度为的排列，求有多少个子区间满足区间最大值在区间最小值的右边。

思路

在松鼠的题单上，这题叫做“一种数区间问题的线段树解法”。我们考虑用类似与扫描线的思路，从左到右枚举右端点，维护合法的左端点，表示合法，表示不合法。我们考虑维护左边第一个比它大的数的位置，第一个比它小的数的位置，这可以用单调栈求出。考虑从移动到的影响。假如，那么这个区间一定合法；假如，那么这个区间一定不合法。对于其他的区间不会产生影响。我们需要一个能够区间赋值，区间求和的数据结构，直接线段树即可。时间复杂度为。

还有一个启发式分裂的做法，先搁着。

CF1748E Yet Another Array Counting Problem

传送门

题意简述

定义一个区间的“最左端最大值位置”为区间内位置最靠左的最大值位置。给定一个长度为的序列，给定，求满足以下条件的序列的数量：

• 的长度为

• 对于任意的，和在子段的“最左端最大值位置”相同。

答案对取模。

，，

思路

我们发现“最左端最大值位置”这个条件非常好，因为以值为第一关键词，位置为第二关键词，建出的笛卡尔树唯一。我们考虑在笛卡尔树上 dp。设表示点填了的方案数，不难得出转移方程：，直接计算是的，我们考虑进行前缀和优化，那么单组数据的时间复杂度即变为。

ABC280E Critical Hit

传送门

题意简述

有一值，每次有的概率让其减少，有的概率让其减少，求让的期望步数，对取模。

思路

不知道为什么这道题在题单里。

我们设为时还需要的期望步数，初始化，，那么，递推计算即可。

CF1817B Fish Graph

传送门

题意简述

给定一个有个点，条边的图，求出这个图有没有满足这些条件的子图：

• 子图中有一个环

• 环上有且只有个特殊点连有两个不在环上的点。

若有这样的子图，输出任意一个。

思路

在看到数据范围之前：这才 *1900？我变菜了？

在看到数据范围之后：sb 题。

由于，太小了，我们可以枚举一个度数的点为特殊点，进行 dfs 找环，判断答案即可，时间复杂度为。

CF1693C Keshi in Search of AmShZ

传送门

题意简述

（复制洛谷题解的）

给定一个个点，条边的有向连通图，你可以从点开始沿着一条路径行走，沿着一条边行走花费的时间，在某个点上时你可以花费的时间断掉一条相邻的边，若沿着边行走的行动是完全随机的，即随机选择一条相邻边行走，问到达 点的最大时间的最小值。

，

思路

由于题目要求的是最大时间，因此我们可以把随机移动看作最劣移动。我们设表示在这种情况下，从点走到点的时间的最小值，那么可以得出转移方程。我们发现转移方程满足 Dijkstra 的形式，同时我们按从小到大考虑可以很快的算出后面一部分的值，那么我们只需要在反图上跑堆优化的 Dijkstra 即可，时间复杂度为。

CF1753C Wish I Knew How to Sort

传送门

题意简述

（洛谷翻译很简洁啊，直接复制了）

给定一个长度为的 01 序列和一种操作，你需要用这种操作将序列从小到大排序。

操作如下：

• 等概率随机选取两个位置，若，则交换。

注意：当时，交换失败，也算作一次操作。

请你求出操作被执行的 期望次数。对 998244353 取模。。

思路

很好的 dp 题。松鼠的题单中这道题叫“认真读题 + 状态设计复杂就换⼀种”，我们可以从中得到什么启示呢？

我们仔细分析这个序列，发现最后这个序列的样子一定是个后面接着个。假如一开始前个数中有个，我们容易发现这样一个事实：一定是不增的；同时，一次操作让减小一的概率为，期望次数则为，那么答案即为。时间复杂度为。

CF940F Machine Learning

这题我在妙妙题 - Floze3’s Blog中写过，因此不要脸的扔个链接就跑。

P3293 [SCOI2016] 美味

传送门

题意简述

给定一长度为的序列，有次询问，给定，，，，从到中找出的最大值。

，，，

思路

很显然我们需要按位贪心。我们假设贪到了第位，设表示在位之前选的位之和，假如第位为，那么最终的答案上这一位为的充要条件是中有属于的数，反之，则是有属于的数，我们可以用主席树维护这一点，时间复杂度为。