IOI2019题解

由于太懒了，好久没更新了。发个题解好了。

shoes

首先不难证明鞋子配对一定是从前往后将同一种的左和右配对。

配好对之后首先我们可以假设左在右的左边，然后讨论可知将左边靠前的排在前面更优。

rect

先考虑只有行限制的情况，那么我们考虑从小到大插入，那么每次极大的区间就是符合题意的，这样就可以扣出O(n)个区间。

同时我们可以考虑矩形左上角，对于每个左上角考虑每个行区间的延伸长度，每个列区间的延伸长度，合并的时候是一个扫描线。

此外本题也有不带log的做法，留作习题。

split

假设a<=b<=c，那么显然有a<=n/3，b<=n/2。我们的目标就是要找到两个联通块，满足其中一个大小在[a,n-b]（或在[b,n-a]）。

我们对[a,n-b]和[b,n-a]都运行以下算法，简记为[l,r]。容易证明l+l<=r。

考虑dfs树。如果树上存在一条符合题意的割边，那么直接输出即可。

否则考虑重心，我们必然有去掉重心之后的每棵子树大小<l，否则这棵子树就符合题意（大小在[l,n/2]之间）。由于只有返祖边，我们只需考虑下属各联通块到重心的祖先是否有边。如果没有，那么它肯定和重心只能同属一个联通块（因为它的大小<l）。如果和重心只能同属一个联通块的大小和>r了那么无解，否则我们先把重心和重心的父亲断开形成两个子树，此时重心子树大小>r，然后我们把能连的子树一个一个抛弃重心往上面连，直到和重心连在一起的大小<=r，这时我们一定有它>=l，由于l+l<=r。

line

考虑螺旋状的构造，那么只有卡在角上的情况才会浪费步数。