闲扯这题之前不是绿题吗，怎么 突然紫了。。。 题面P5588 小猪佩奇爬树 Solution这道题的要做的事是很清晰的：给定一些点，问是否存在一条简单路径 $(u,v)$ 满足所有的点都在该路径上。如果有，请输出这种路径的个数。 显然，这题的难点就在于怎么判断是否存在，至于方案，是很好计算的。 因为 ...

题面题面 $T1$Solution首先，我们不考虑字典序，只考虑代价最小。 明显的，我们有一个贪心的想法：确定先填奇数还是先填偶数之后，我们让奇数和偶数的相对位置关系不变，这种策略的代价一定是最小的。 （证明：我们考虑交换排序过后的两个数，分类讨论一下，可以得知答案一定不会比直接按照原来的顺序更优。 ...

闲扯平时我都记得到计算范围， 这次怎么就算漏了呢。。 题面$ftp$ $T1$Solution根据题面，我们可以得到这样一个事实：这颗树是某个图的 $dfs$ 树。 据此我们可以得到一个很有用的性质：对于图中的所有非树边，它们一定都是回向边。 所以对于每一个点，我们只需要判断能否向从他的父节点到根结 ...

闲扯我发誓，我以后再也不会把不同的情况混着写了！！！ 题面$ftp$ 上 $T1$Solution对于一个家店，我们肯定是用之前没有还没有进行过操作，而且能带来利润的店（ $val_i>val_j,i>j$ ）来配对。 如果不存在，那么我们就直接忽略掉它。 这样配对之后能得到的利润肯定是 ...

闲扯线段树进行区间操作一定要判断范围！！！ 题面P2824 [HEOI2016/TJOI2016]排序 Solution如果直接排序显然是不好做的，我们考虑一个简单的形式： $01$ 序列排序。 这个显然是可以用线段树直接做的。 然后这个题有一个神奇的性质：答案是单调的 假设我们指定答案为 $k$ ...

闲扯这题的题面有问题。 题面P4198 楼房重建 Solution这道题我们不需要看题面给的解释（因为有问题），只需要用我们的生活常识来判断就行。 我们能看到一栋楼，当且仅当这栋楼最高点与原点的连线没有经过任意一个在它前面的楼。（交于一点也不行，相似三角形搞一搞就可以看出） 我们将每一栋楼的权值定义 ...

闲扯这题用倍增做着感觉好麻烦啊，一个是走 $2^k$ 条边，一个是走 $2^k$ 个点，细节上要注意一下。 题面CF587C Duff in the Army Solution这道题有一个很关键的性质： $a\leq10$ 。 这是一个很小的值，所以我们可以直接维护。 由于是树上的路径，我们可以考虑 ...

闲扯一年前刚学倍增的时候老师给的训练题，一直没做，过来填坑了。 题面P1613 跑路 Solution因为每秒能跑的长度为 $2^k$ ，所以对于一对 $u,v$ ，如果它们之间的距离能用 $2^k$ 表示出来，那么我们就可以从 $u$ 向 $v$ 连一条长度为 $1$ 的边。 而这个问题的形式恰好 ...

题面CF1168A Increasing by Modulo Solution因为要求最小操作次数，我们考虑二分答案。 因为每次都是任选 $k$ 个数，所以我们可以看做是每个数都能操作最多 $k$ 次。 定义 $pre$ 为当前元素的前一个元素 要判定 $mid$ 是否有解，我们有如下策略： 如果 ...

闲扯这道题挺妙的。 题面CF1167F Scalar Queries Solution这道题直接模拟肯定是不行的，我们考虑换个思路。 我们统计对于每一个 $a_i$ ，它被计算了几次。 排序后，假如 $a_i$ 处于第 $k$ 个，那么它就会被多算 $k-1$ 次。那么相当于在这个区间中每一个比 $ ...