solution 首先可以发现，这张图其实可以转化为一棵最大生成树。 我们按权值从大到小加入边，如果新加入的边所连接的两点，已经可以通过其他权值更大的边相连，后面的询问中只删除这条边起不到任何作用。 所以我们考虑建出 重构树。 具体建立方法:对于在生成树中的一条边，新建一个节点，并且从向所在的集合分别连边。将的点权设为的边权。并将所在的集合改为。最终重构树的根节点为最后新建的节点。 在重构树中，每个生成树中的节点在重构树中全都是叶子节点。生成树中两个节点之间的路径最小值为重构树中这两个点的点权。 利用这条性质，我们考虑回答询问。对于每个询问，我们如果暴力处理，可以删除这个点任意两个点路径上...

solution 用表示前个元素，删掉了，所能得到的不同序列的数量。 如果先不考虑不同序列的话，那么就有。也就是种方案。然后考虑减去不合法的方案。 对于一个位置，如果上一个和相等的位置为,那么以结尾的每个序列，都可以通过删掉这个区间变成以结尾的序列。这显然是重复的，所以只要让就行了。 code /* * @Author: wxyww * @Date: 2020-04-24 18:48:43 * @Last Modified time: 2020-04-24 18:59:03 */ #include<cstdio> #include<iostream> #includ...

solution 我们大胆猜测：如果当前已经选择了一些位置，加入新位置时只要与已选的最后一个位置满足题目条件，那么肯定与前面的每个位置都满足条件。下面给出证明。 证明:设已有。对于第一个不等式，同时变为，因为底数为正数，所以不等式符号不变。即变为,对于第二个不等式，同时变为，即变为。然后将这两个新的不等式合并得到，同样的，我们让两边同时变为，得到。 然后就变成了一个比较简单的了，用表示已第个位置结尾符合条件的子序列个数。转移只要枚举一个满足的，让即可。 还有最后一个问题，如何比较与的大小。我们对其同时取对数，即比较与的大小。根据高中所学，我们知道，所以只要比较与的大小就行了。 code /...

problem 题意搞了很久才搞懂233.给出一个序列，对于每个长度的子段，会将其中第大的元素放进集合中。最后询问集合中第大的子段。 solution 首先二分一个答案。然后一下区间第大大于等于的区间个数，如果，那么说明还可以再放大并且可以成为答案，否则说明需要缩小。 然后考虑函数如何写。维护两个指针。然后向右不断的挪动。当区间内大于等于的数字个数个时，说明当前区间是一个合法区间，此时在满足区间内的个数的条件下，再不断的向右挪动。对于此时经过的每个，以他们为左端点，并且以中的任意一个数为右端点时，都是一个合法区间。 code /* * @Author: wxyww * @Date: 202...

solution 对于每个糖糖考虑计算他是不是会被消灭。一个组的糖糖会被消灭仅后面存在一个组的糖糖满足，表示前秒总共增加的能量值。移项得。所以把每个糖糖的能量值都变为。然后从后向前枚举的过程中分别统计两个后面的最大值。判断当前点是否会被消灭。 code /* * @Author: wxyww * @Date: 2020-04-20 17:25:13 * @Last Modified time: 2020-04-20 17:37:11 */ #include<cstdio> #include<iostream> #include<cstdlib> #inc...

solution 考虑求答案的补集。也就是计算有多少个序列不是反复横跳的。 这样的序列肯定是单调不降序列或者是单调不升序列。 又因为所有数字不超过k。 以单调不降序列为例（单调不升序列个数与其相等）。我们枚举最后一个数字的大小。然后对这个序列做一下差分，也就是令。这样就转化成了有多少个满足条件的序列，满足什么条件呢？只要满足。这是经典的组合问题，相当于把x个物品分为b份，每份可以为空，用隔板法可以看出答案就是 所以这种序列的个数就是 因为题目要求，所以只要将上面的变为所给的k-1即可。 因为有种序列是既单调不升又单调不降的，所以要减去k。 综上，答案就是 将那个组合数拆开，发现复杂度是可以接受...

solution 用线段树维护即可。考虑线段树的懒标记如何维护。我们维护两个懒标记，添加到当前位置的数列在该区间开始位置的首项之和，表示这些添加的数列公差之和。 因为如果往一个位置添加了一个等差数列。其中某个位置可以看作，那么再添加一个等差数列，那么该位置就可以看作，相当于添加了一个首项为公差为的等差数列。 挺简单的思路，就是有点难调233 code /* * @Author: wxyww * @Date: 2020-04-17 19:25:25 * @Last Modified time: 2020-04-17 20:49:01 */ #include<cstdio> #in...

solution 其实本题只要解决一个问题，剩下的就是模拟了。 这个问题就是如何快速的比较两个字符串的字典序。这是一个非常经典的思路。我们对这两个字符串都哈希一遍，然后二分一下这两个字符串最长的公共前缀长度。然后比较最长公共前缀的下一位上的字符就行了。因为所有要比较的字符串都在同一个母串上。我们只要对这个母串进行一遍哈希就行了。 剩下的按照题目中讲的模拟即可。 code /* * @Author: wxyww * @Date: 2020-04-17 19:15:03 * @Last Modified time: 2020-04-17 19:23:46 */ #include<cstd...