IOI 2019 题解

管理员

Day1 A 排列鞋子

从前往后考虑每个位置 (i),并找到与它匹配的最靠前的元素,将这两个元素放在最靠前的空位置,最后算一下逆序对个数即可。

Day1 B 景点划分

假设 (ale ble c),于是有 (ale frac{n}{3},blefrac{n}{2})

任取图的一棵 DFS 树,设这棵树以 (1) 为根。假如能找到一个点 (u) 满足 (mathrm{size}_uin [a,n-b]) 或者 (mathrm{size}_uin [b,n-a]),那么就做完了。因为 (ale ble n-ble n-a),所以其实就是要找一个 (mathrm{size}_uin [a,n-a])(u)

如果没有这样的 (u),那么我们需要对生成树做调整。考虑那些 (mathrm{size}_u>n-a)(u),因为 (ale frac{n}{3}),所以这样的 (u) 一定分布在以 (1) 为端点的一条链上。找到这条链最底下的那个点 (v),我们需要将 (v) 调整成满足 (mathrm{size}_vle n-a) 的。此时只有那些一端在 (v) 的儿子的子树内,一端在 (v) 的祖先上的返祖边是有用的。每条这样的返祖边都可以让 (mathrm{size}_vgets mathrm{size}_v-mathrm{size}_x),其中 (x)(v) 的某个儿子。

并且,这样调整不会让 (mathrm{size}_v<a),因为 (n-a-age a),而 (v) 的所有儿子的 (mathrm{size})(<a),所以如果能让 (mathrm{size}_vle n-a),那么就一定有解,否则一定无解。

Day1 C 矩形区域

一个重要性质是:合法的矩形个数是 (O(nm)) 的。

我们统计出对于每个行 (i),其中有哪些满足 (a_{i,l-1},a_{i,r+1}) 均大于 ([l,r]) 中的最大值的区间 ([l,r])。感性理解,对于每一行,这样的区间个数是 (O(m)) 的。

然后枚举矩形的列边界 ([l,r])。考虑那些合法区间中有 ([l,r]) 的行,这样的行会形成若干值域连续段。只需要对于每个值域连续段分别计算即可,因为段间矩形一定不合法。

考虑一个值域连续段,设它在行这一维上包含了 ([L,R])。考察一个矩形 ((x_1,L),(x_2,R)),因为我们已经能保证每行都是合法的了,所以只需要预处理 (u_{i,j},d_{i,j}) 表示 ((i,j)) 顶上/底下那部分中第一个大于等于 (a_{i,j}) 的位置,那么这个矩形合法的充要条件就是 (min_{Lle jle R} {d_{x_1-1,j}}>x_2land max_{Lle jle R} {u_{x_2+1,j}}<x_1)。于是做一遍二维数点即可统计。

总时间复杂度 (O(nmlog n))

Day2 A 折线

呃。

Day2 B 视觉程序

(|r_1-r_2|+|c_1-c_2|=K) 是不好做的,考虑转成切比雪夫距离,(max(|r_1-r_2|,|c_1-c_2|)=K)。这样只需要实现对于 (kin {K-1,K}),算出 (|r_1-r_2|) 是否 (le k),以及 (|c_1-c_2|) 是否 (le k)。这两个都是好实现的。

Day2 C

以后补。