IOI2020 题解

s_r_f · 2020-09-19 20:00:28 · 个人记录

Day1

solution-洛谷博客 solution-cnblogs

题目链接-LOJ 题目链接-洛谷

首先我们考虑构造出一个符合题意的数列。

每次选择一个前面 k-1 个位置上都是 0 或者已经选过，并且当前位置为 0 的位置，然后把它的值置为这个序列的最大值。不难发现这样做一定能构造出一个符合要求的排列。

这个构造的过程可以用线段树+set优化到 \Theta(n\log n)

不难发现，一个排列符合条件相当于它的每连续 k 位的相对大小关系和我们构造出来的排列相同。

那么，不难证明在 2k>n 的时候只有唯一的一个排列，所以不判 0 直接比较可以获得子任务 2/3/4 的分数。

现在排列不唯一怎么办？

考虑对于每个点，求出它往左/右 k 个位置中，比他小的最大的数字的位置，分别记为 pre_i 和 nxt_i ，然后对 pre/nxt 做一个倍增。

对于每组询问，假定我们构造的排列 A 满足 A_x>A_y 。

我们从 x 开始，通过 nxt 和 pre 往左右跳，保证跳的时候仍然满足当前位置的值 >A_y . 如果跳到的区间包含了 y ，那么就输出 1 ，否则不能确定，输出 0 .

$\Theta((n+q)\log n)

solution-洛谷博客 solution-cnblogs

题目链接-LOJ 题目链接-洛谷

首先，如果存在 p_{i,j}=0 ,那么就分成了多个联通块，这些联通块分开做即可。

由于 p_{i,j} \leq 3 所以一个联通块当中不能出现多于一个环，否则必然会有两个点之间有 4 条路径。

没有环的情况(联通块内 p_{i,j} 均为 1 )先判掉，那么这个联通块正好有一个环。

不难发现，如果两个点 x 和 y 之间的路径需要经过多于一个环上的节点，那么 p_{x,y} 就等于 2 ,否则 p_{x,y} 为 1 , 因此如果存在 p_{x,y} = 3 那么也无解。

把所有的 p_{x,y} = 1 的 x 和 y 合并到一个联通块中，把这些块之间连成一个环， check 是否合法即可。

\Theta (n^2)

solution-洛谷博客solution-cnblogs

题目链接-LOJ 题目链接-洛谷

首先我们考虑如何求出最大值。

不难发现这个抽奖的过程中，工作人员必然会取中位数来最小化当前轮次的奖励。

因为n是偶数，不难发现我们能获得的奖励为：

设当前轮次使用的奖券上的数值为 a_{1,2...n} 并且已经从小到大排序，那么

\large ans=\sum\limits_{\frac{n}{2}+1\leq i\leq n} a_i -\sum\limits_{1\leq i\leq \frac{n}{2}} a_i

也就是说，有 \large \frac{n}{2} 个数对答案的贡献为 a_i ,另 \large \frac{n}{2} 个数对答案的贡献为 -a_i , 并且所有负贡献的数字都不大于正贡献的数字。

可以发现，经过 k 次过程获得的最大值，相当于我们在 n 种颜色的奖券上的数字中，每种颜色选取 k 个数字，并在其中选 \large \frac{nk}{2} 个数字，使其对答案的贡献为正数，令另外一半的数字的贡献为负数，然后求和即为答案。

不难发现如果我们获得了这个取数问题的最优解，那么必然存在一种方案把这 nk 个数分成 k 组使得每组中有 n 个颜色两两不同的数，一半取负贡献，一半取正贡献，并且负贡献的数都不大于正贡献的数字。即有对应原问题的合法方案。

证明：如果不存在合法方案，那么对于任何一种方案，必然存在同一组数字中有一个取负贡献的数大于一个取正贡献的数。这时候交换一下它们的符号就可以获得一个更优的解，所以如果取得了最优解的取数方案，必然有一个对应了原问题的合法方案。

取数问题的贪心：先默认都取负数，然后再贪心的做 \large \frac{nk}{2} 次把负数换成正数的操作即可。

然后我们考虑如何构造方案。

递归构造，考虑从当前的 nk 个数字中取出 n 个颜色两两不同的成为一组，保证它合法后再对剩下的 n(k-1) 个数字继续构造。

从每种颜色中取出一个最大的正数和一个最小的负数并将正数和负数分别排序，枚举正数和负数之间的边界，two-pointers 的同时维护可用的正/负数数目即可。

因为正数和负数分别取到了最大和最小，所以在整个取数问题有对应方案的时候这个子问题必然能找到一组解，可以继续递归。

由于递归的时候保证了选数方案一直是当前的最优解，所以一直都能保证当前的选数方案有一组对应原问题的解。

\Theta(nm\log n)

还没有题目