什么是淀粉质点分治？ 就是把分治搬到树上，以某个点为根，分别分治处理子树的答案，再计算子树与子树间的答案的玄学算法。 举个例子： 如何求出一颗树上距离为K且所经过的点最少的点对？ 对于这种题，我们可以把某个点（一般为重心）作为根，然后对左右子树递归处理，先分别得出左右子树的答案，再求出横跨两个子树之间的点对的答案。 为什么要学淀粉质 对于上面那道题，如果我们用传统的暴力做法，最优的复杂度只能...

题面 传送门：洛谷 Solution 这题极其巧妙。 首先，如果直接做m次排序，显然会T得起飞。 注意一点：我们只需要找到一个数。 所以说，我们可以考虑一个绝妙的想法：我们可以用二分答案的方法缩小要找的数的区间。 考虑二分一个值，判定p位置的数排序之后，p位置上的数是否>=mid 如果>=mid,则向右找，否则向左找。 怎么判定p位置的数排序之后是否>=mid呢？ 考虑这...

题面： 传送门：Codeforces 题目大意：给你一颗有根树，点有权值，问你每个节点的子树中距离其不超过k的点的权值的最小值。（边权均为1，强制在线） Solution 这题很有意思。 我们一般看到这种距离不超过k的题目，第一反应一般是建以深度为下标，以dfs序为时间轴的的主席树。 很不幸，区间最小值并不能通过减去历史状态得出某个子树的状态。 所以说，这题妙在思想的转换。 考虑以dfs序...

题面 传送门：洛谷 Solution 你们搞的这道题啊，excited！ . 这题真的很有意思。 首先，我们可以先理解一下题面：固定一个a，找到一个b，c就是a与b的公共子树中的某个点。 那么，我们显然可以把这个b分成两类，第一种是在a上面的，第二种在a下面的。 对于b在a上面的情况，**显然，c一定是a的子树中的某个点，**答案即为$min(K，depth[a])*size[a]$ 对于...

题面 洛谷 Solution 这题十分有意思。 首先，我们可以先想想离线做法，因为在线做法可以从离线做法推出。（虽然这题推不出） 我们可以明确一点，一个熊孩子开心的时间是满足二分的要求的（如果他某个时刻开心了，那之后的时刻都会保持开心）。 对于判断一个区间是否为全0，我们可以用主席树以一个log的代价来判断。 得到每个熊孩子开心的时刻之后，我们就可以直接前缀和解决问题了。 时间复杂度$O(...

题面 传送门：洛谷 Solution 如果题目只要求求出第一问，那这题显然就是大水题。 但是加上第二问的话…那这题就成为大（du）火（liu）题了。 对于第一问：求一整个区间的最大线段总数，我们可以很轻松的切掉。 怎么处理第二问呢？ 我们可以考虑这样做： 对于一条线段，如果它属于答案的一部分，那么它一定会有以下性质： 区间③的最大线段数 = 区间①的最大线段数 + 区间②的最大线段数 + ...

题面 传送门:洛咕 Solutiton 挺简单的一道模拟题,拿堆模拟一下题目意思就好 堆中有两个关键字,分别是优先级和到达时间 还要维护一下每个任务剩余时间(还有多久完成) 因为堆不能直接改.得在堆里记录编号然后映射出来 这里总结一下要注意的细节: 1.在下一个任务到达之前,尽可能把CPU内的任务完成了 2.注意读入 3.注意注释文件读写233(我因为这破事爆零一次) 4.没了 好像不需要...