某岛

… : "…アッカリ~ン . .. . " .. .
July 26, 2021

Codeforces Global Round 15

传送门

https://codeforces.com/contest/1552

Problem C.

给定一个圆环,初始已经连了一些线段,要求连剩下的线段,问最优情况下,最后总交点最多是多少。

不考虑已经连的线段,对于剩下的我们按照最优情况 1234..1234.. 这样连就行。。
最后把已经连的拉进来一起统计即可。

Problem D.

给定一个长度为 n 的序列 a,问是否可以构造一个长度同样为 n 的序列 b,使得 a 中的每个元素都是 b 中某两个元素的差。
n <= 10

Problem E. Colors and Intervals

给 n 种颜色,初始时给长度为 n*k 个位置染色,使得每种颜色恰好出现 k 次。
求构造 n 组区间的方案,满足对于每种颜色,都有一组区间的端点是这种颜色。
且,不存在某个位置,使得被区间覆盖超过 \ceil{n, k-1} 次。
(n, k <= 100)

贪心?显然我们总是选择那些尽可能小的区间,因此对于每种颜色,我们只需要考虑 k-1 种相邻的区间即可。
我们按照所有区间大小排序来依次选择?很遗憾这样是错的。但是稍微改改,按照每个区间的右端点来排序就对了。

证明?反证法。
考虑某种颜色,我们枚举了所有 k-1 种区间发现都不满足,那么对于这些区间 [a, b],
每个区间都存在 \ceil{n, k-1} 个区间使得它们的右端点均位于 [a, b] 的内部,因为覆盖 [a, b] 的区间因为右端点比 b 大还没有被我们扫描到。
那么此时一共已经选择了 (k-1)*\ceil{n, k-1} >= n 个区间,但是我们还没有选择那么多,与假设矛盾。

Problem H. Guess the Perimeter

格点图里 ( <= 200) 有一个矩形,你可以至多 4 次询问后回答这个矩形的周长。
每次询问,你可以挑选任意数目的点,返回里这个集合中有多少点在目标举行的内部或者边缘。

???

Problem F. Telepanting

数轴上有 n 个传送门,每个传送门用三元组表示为 (xi, yi, {0,1}),表示传送门所在位置为 xi,传送的目标位置为 yi,以及当前是否 active。(yi < xi)
有一只蚂蚁从 0 出发,每个单位时间向右移动一格,当走到传送门时,如果 inactive 则变为 active,如果 active 则被传送至 yi 并置该传送门为 inactive。
问走到 xn + 1 需要多少时间。

走到某个传送门时,不管这个传送门当前的状态是 inactive 还是 active,前面的传送门一定当前都是 active。
因为所有的传送门都是往后退,那么要突破某个传送门,一定走上去的时候是 inactive,通过之后翻成 active。
这样状态就很简单了,a[i] 表示第 i 个传送门的状态是 active,那么走上去之后传送走到下次回来需要花费多少时间。

转移方程是 …
a[i] += x[i]-y[i];
REP(j, i) if (x[j] >= y[i]) a[i] += a[j];

用前缀和 + 二分查找优化即可。

Problem I. Organizing a Music Festival

求有多少长度为 n 的排列,满足某些集合出现在连续位置。
(n <= 100)

有点意思。

首先不妨弱化,只考虑集合 size = 2 的情况。
那么显然每个集合相当于一条边,于是我们转化为一个图论计数问题。

对于每个连通块,要么 * 1 如果 size = 1。
要么 * 2 如果 size >= 2 并且是一条链(正反两种情况)。
要么 * 0 如果 size >= 2 且不是链。

最后再乘以 连通块数 的阶乘即可。

对于一般情况?构成了某种奇妙的树形结构,上面的点和边都变成节点的集合,dfs 进去边 reduce 边统计即可。

(我傻了,这不是 PQ 树么。。。)