Codeforces Global Round 15 题解

A - Subsequence Permutation

求出 (s) 排序后的结果 (t),计算 (s, t) 不同的位置数即可。

B - Running for Gold

答案唯一,因为如果有两个答案,那么两者是相互矛盾的。

于是顺序扫描,维护可能的答案就行了。

C - Maximize the Intersections

如果所有位点都是空的,那么每个位点与对面相连最优。

现在有若干初始的弦,那把剩下的 (2(n-k)) 个取出,第 (i) 个连向第 (n - k + i) 个即可。

D - Array Differentiation

如果 (b) 的长度为 (n + 1) 就好办了,(b_1=0)(a_i=b_{i+1})

长度为 (n)​,说明存在一个“环”,边权值和为 (0)。我们枚举一个子集 (S),作为环的边权,并且枚举正负。如果存在 (=0) 就是成功。

复杂度 (O(3^n n))(O(3^n))

E - Colors and Intervals

考虑到 (lceil frac{n}{k-1} ceil (k-1) ge n),我们每次处理 (k-1)​ 种颜色,进行 (lceilfrac{n}{k-1} ceil) 轮这样的操作,就能操作到所有的颜色。这样合法的前提是,没轮操作中每个位置覆盖不超过一次。

我们尝试这样一个算法:提取出所有当前 (k-1) 种颜色对应的位置,每个颜色有 (k) 个位置。那么顺序扫过,当第一次遇到一个“第二次出现该颜色”的位置时,记录答案,清空之前所有的扫描记录。

其中,只要证明“清除记录”不会造成无解即可。首先考虑一次清空,最多导致其他颜色 (k) 个位置中的一个变成无效的。但注意我们一次只处理 (k-1) 种颜色,因此最后一个出解的颜色只会有不超过 (k-2) 次使之位置无效化的清除。剩下两个仍然构成解。

复杂度不超过立方级别都能过,可以做到 (O(nk))

F - Telepanting

动态规划,设 (f_i)​ 表示当前刚经过 (x_i)​,且经过后 (1sim i)​ 号机关全为活跃状态,这时希望穿过 (x_{i+1})​ 且穿过后 (i+1)​ 号机关也是活跃的,其间所需时间。一般认为默认状态都为活跃。如果求出了 (f),那么答案不难计算,如果 (s_i=0) 则加上 (x_i - x_{i-1}),否则加上 (f_{i-1})。最后再加一。

考虑从 (f_{i-1})​​​​ 推到 (f_{i})​​​​。首先一开始 (i)​​​​ 号机关是活跃的,那么会直接传送到 (y_{i+1})​​​​ 的位置,然后计算“从 (y_{i+1})​​​​ 到达并穿过 (i)​​​ 号机关”,加上 (x_{i+1}-x_i)​​​ 就是所求。要得到 (y_{i+1})​​​ 后第一个 (x)​​ 可以 std::lower_bound,记为 (x_k)​​。计算中途的代价即为中间 (f_p)​ 之和。可以直接相加而不考虑再次被传送回去,是因为在之前计算 (f_p)​​ 考虑过了。完整状态转移:

[f_{i} = (x_{i+1} - x_i) + (y_{i+1} - x_{k-1}) + sum_{p=k-1}^{i-1} f_p ]

前缀和优化,复杂度 (O(nlog n))

G - A Serious Referee

咕咕咕

H - Guess the Perimeter

对于一个 (w imes h)​ 的矩形,如果知道了它的面积以及一边的长度,周长就很显然了。考虑面积,很简单,把所有点都扔进去,问一遍,结果就 (=(w+1)(h+1))​。这需要一次询问,剩下 (3)​ 次我们搞出 (h)​。(这么多 (+1) 是因为每个维度两侧边框都算)

首先有一个还算显然的引理:记询问一个点集 ({(dcdot i,j)| 1le ile lfloor frac{200}{d} floor, 1le jle 200}) 得到的结果为 (f(d))。那么 (forall d | (w+1)),满足 (dcdot f(d) = f(1))

根据这个,可以判断一个数 (d)​ 是否是 (w+1)​ 的因数。如果图画出来,注意到一点,如果一个数 (d|(w+1))​,(dcdot f(d) = f(1))​ 的实际意义为,(dcdot f(d))​ 可以直接表示 (f(1)) 而无差错。反之,则 (dcdot f(d) eq f(1))​,(dcdot f(d))​ 相比 (f(1)),多了或少了若干列的点。如果可以利用这部分差错,并得知一共多了或少了多少列,就不难得到 (h) 的具体值。

考虑求一个 (k),满足 (2^k)(2) 的最高为 (w+1) 因子的幂,即 (2^k |(w+1))(2^{k+1} ot{|} (w+1))。为什么是 (2) 的幂而不是其他数的幂呢?观察上面那个突破口,由于 (h) 需要差错和“一共多了或少了多少列”这两部分信息求得,前者就是询问本身,后者则不那么号操作。而对于 (2) 的幂,从 (2^k)(2^{k+1})​,多了或少了的列数必然为 (1)。于是具体得到的差错值就完美地等于 (h+1)

形式化上面的描述,就一个等式:

[left| f(2^k) - 2f(2^{k+1}) ight| = h+1 ]

最后就是如何求 (k)​ 的问题了。显然 (k in {0, 1, 2, 3, 4, 5, 6, 7}),直接顺序可能要求 (8) 次。但我们发现此处有可二分性,对于不超过 (7) 个数可以在 (3) 次查询得到结果。其中 (f(1)) 是面积相关,在一开始就计算好,这里一共 (4) 次询问。不过最后一步还需要 (f(2^{k+1})) 的值,然而这在二分的过程中已经算过了(这也是选择 (2) 的幂的又一个优势);对于 (k=7)​​ 的情况,由于 (f(2^8)) 必然 (=0),不会有额外的询问。

至于 (2) 的幂是怎么反应到的……大概还是做题经验吧。

I - Organizing a Music Festival

咕咕咕

本文来自博客园,作者:-Wallace-,转载请注明原文链接:https://www.cnblogs.com/-Wallace-/p/sol-cf-gr15.html

原文地址:https://www.cnblogs.com/-Wallace-/p/sol-cf-gr15.html