松鼠严选
P1783 海滩防御传送门 题意简述给定 个点的坐标，横坐标 ，求以这些点为圆心的圆半径至少为多少才能通过这些圆从横坐标为 走到横坐标为 的点。 ，，， 思路水题。 我们考虑二分半径，用并查集维护连通性，最后检查左边界和右边界是否连通即可。时间复杂度为 。 CF1849E Max to the Right of Min传送门 题意简述给定长度为 的排列，求有多少个子区间 满足区...题解：P7250 [BalticOI 2012 Day1] 山峰
传送门 思路简述题目中的输出格式很明显的提醒我们要把这道题分为两个部分：找到所有的山峰，以及求出走到海拔更高的山峰所经过的最低海拔最大值。接下来的题解也会以这两个部分分开来讲述。 第一部分我们注意到，一个山峰是一个周围没有海拔比它高的连通块，我们不难想到用并查集维护这一点。我们对于每一个方格，遍历与它联通的方格所在的连通块，根据连通块所在的情况来更新状态。具体而言，若旁边的方格海拔比他高，...题解：CF1998D Determine Winning Islands in Race
传送门 思路简介我们考虑什么时候 Bessie 不能赢下比赛：当且仅当 Elsie 能够从 Bessie 起点之前的点，通过额外的路径比 Bessie 先走到某个点。充分性显然，必要性也不难理解：假如 Elsie 无法做到这一点，她永远不可能走到 Bessie 之前，因此她不可能赢得比赛。我们设这个点为 ，Bessie此时的起点为 ，Elsie 在当前状态下走到 的最短时间为 ，那么可以...题解：CF1998C Perform Operations to Maximize Score
传送门 思路简介做过的最难的Div2 C 显而易见的，如果我们选择出的那个数可以被增加，那么增加那个数一定更优。这启示我们分两种情况考虑：一种是选出能被增加的数中的最大的数，并且一直增加那个数；另一种是选出不能被增加的数中的最大的数，并且增大中位数。第一种情况是好处理的，如何处理第二种情况？我们考虑要是中位数为某个特定的值所需的最少操作次数具有单调性，我们不妨考虑二分中位数，可以做到 c...题解：AT_abc360_e [ABC360E] Random Swaps of Balls
传送门 思路简介不难想到，除了第 个位置，在进行 次操作后黑球到每个位置的概率是均等的。因此，我们只需要维护两个值：黑球在第 个位置的概率和在其他位置的概率。 我们考虑从上一次操作进行完之后递推。令上一次操作完后在第一次的概率为 ，在其他位置的概率为 。我们考虑如何得出在这一次操作完后的两种概率，记为 和 。 首先是在第一个位置的概率，有两种转移方式： 从其他位置转移而来，对于每...题解：CF1954D Colored Balls
传送门 思路简介对于一组可能的小球组合，设数量和为 ，最大值为 ，那么能分成的最小组数即为 。观察到 的值不会大于 ，我们可以用一个 数组记录每一种数量和的出现次数，将数量从小到大排序后一边通过遍历 数组分情况来统计答案，一边更新 数组即可。 代码123456789101112131415161718192021222324252627282930313233#include &l...妙妙题
CF369E Valera and Queries传送门 题意简述给定 条线段，共有 次询问，每次询问给定一组点集，询问至少覆盖其中一个点的线段条数。 思路正难则反。 对于每次询问的点集，我们考虑以其为分割点，转化为一条条线段。例如： 这个点集可以转化为 这样的线段。 转化完成后按左端点从大到小排序，用树状数组统计答案即可。 P6564 [POI2007] 堆积木KLO传送门 题...题解：CF853C Boredom
传送门 思路简述这里给出一个较为暴力，但想与写都比较方便的方法。 对于每一个矩形的询问，为了不重不漏，我们可以以矩形的四条边为参考，将整个大矩形划分为 个小矩形，如下图（其中黑色小矩形为询问的矩形）： 我们统计出每个小矩形内部的黑点个数，记为 ，那么我们可以得出与这个矩形有公共点的好的矩阵的计算公式： $$ S_1 \times (S_5 + S_6 + S_8 + S_9) + S_...并查集学习笔记
简介这里引用OI-wiki上的内容： 并查集是一种用于管理元素所属集合的数据结构，实现为一个森林，其中每棵树表示一个集合，树中的节点表示对应集合中的元素。顾名思义，并查集支持两种操作：合并（Union）：合并两个元素所属集合（合并对应的树）查询（Find）：查询某个元素所属集合（查询对应的树的根节点），这可以用于判断两个元素是否属于同一集合 看不懂？ 简单来说，并查集就是一种简单的判断两...
1