lojround3

A。绯色 IOI(开端)

首先注意到是完全图,数据范围又很大,肯定要观察一些性质

我们化简一下式子 发现其实是要求simga(xixj)最大

那么结论就很好想了

最大的和次大的第三大的连一起。。。然后。。。。

至于题解说的部分分要求大小递减也是很容易想的

B. 绯色 IOI(抵达)(写)

也是性质题

我们会发现所有的一定是二元的

然后 树的完美匹配是唯一的(考虑叶子节点)

然后我们可以得到n条边(同阶)的大小关系

那么1的大小就是子树大小

然后标记1子树的范围是1-x,根的范围变成x+1-n

然后查找2,找到2上面最近的有标记的节点,然后取一段,改一下标记

如何查找最近有标记的节点,我们可以用线段树来打区间赋值操作

原文地址:https://www.cnblogs.com/yinwuxiao/p/9533339.html