href="https://www.cnblogs.com/sigman/p/19621928"

title="发布于

贪心题&猜性质题总结

id="post_view_count">0)

评论(

id="post_comment_count">0)

inline">\(p_i\)，现在可以把任意数字变成

n-p_i\)，问序列最小的逆序对个数为多少。

贪心直接去想每一个

inline">\(c_1+n-i-c_2\)，如果将

inline">\(c_1+n-i-c_2>n-i\)

inline">\(c_1>c_2\)，我们执行操作是最优的。

但是我们在处理

时前面的数可能也执行了操作，我们分析一下这样的情况的影响。

对于两个数

inline">\(p_i,p_j\)，我们按照大小分两种情况讨论。

inline">\(c_1,c_2\)，那么对于

inline">\(c'_1>c'_2\)，也就是说按照这种做法，

class="math

inline">\(c'_1>c'_2\)，那么我们也会进行操作，此时逆序对个数增加

inline">\(c'_1>c'_2\)

，我们操作后逆序对个数会减少，综合一下我们的逆序对个数是不增的。

我们只考虑两个数的原因是因为操作后对于逆序对的影响只是操作的数之间的大小的变化。

inline">\(c_1>c_2\)，我们就可以进行上面的操作使得逆序对个数减少至少也不会增加，这样就说明了贪心的正确性。

场比赛，每一场比赛两个队伍之间比赛，两个队伍的每个人一一配对去比，会有输赢，现在问比赛结束后最多有多少的人是赢了

很明显，一个人如果输了，那么就一定不会成为答案的一部分，一个人如果赢了，那么我们既要尽可能的让他们成为

自我感觉是一道比较好的题目。

首先一开始我猜了一个结论，只要

inline">\(000111\)，也可以将序列

inline">\(000111\)，由于操作具有可逆性，所以我们可以将序列

inline">\(a\)。

也就是说我们可以将任意的序列都变换为

如果不在第一或最后一个位置，它一定可以变换到倒数第二个位置或第二个位置，因为我们可以将

inline">\(1\),奇数反之。

最终我们得到子段合法的判断标准，即子段中

inline">\(c_0,c_1\)，那么答案为

inline">\(C_{c_0}^{2}+C_{c_1}^{2}\)，结束！

我们注意到最后的树一定是一个菊花图，且对于每一个点，如果我们通过操作使得它的度数增加，我们只会一直让它增加。

所以我们对每一个点进行讨论。

对于每一个点，我们发现只要将叶子节点到它的路径上的点连边即可，那么操作数就是叶子节点的数量，当然，如果叶子节点就是它的儿子，那就不用考虑。

所以我们只要记录初始的叶子结点总数，对于每一个点，遍历它的儿子，减去不必要操作的点，剩下的就是我们必须要操作的，最后去

min

inline">\(b\)，那么我们肯定要让当前的

inline">\(a_{i+1},a_{i+2},a_{i+3}\dots\)，

假设我们需要异或到

inline">\(a_{i+2}\dots\)，这是固定的，所以我们还需要记录一个右端点

的异或的数已经固定了，只要判断满不满足即可。

实现的话我们需要预处理前缀异或和，判断是否是我们需要异或的数只需要根据

b_i\)，那么我们就做完了。