Codeforces Round #713 (Div. 3) 题解(A-G)

A. Spy Detected!

对于\(i \in [2, n -1]\),当且仅当\(a_i \ne a_i - 1\)且\(a_i \ne a_{i + 1}\)时,\(i\)为最终答案。

否则,答案可能是\(1\)或者\(n\),将\(a_1\)和\(a_n\)与\(a_2\)比较看那个与\(a_2\)相同,另一个就是答案。

B. Almost Rectangle

标记出两点的坐标\((x_1, y_1)\),\((x_2, y_2)\)。

若两点不同行且不同列,那么已经确定了一个唯一的矩形。

若两点同属第\(x\)行,则只需再其他行种任选一行\(x^\prime\),在\((x^\prime, y_1)\)和\((x^\prime, y_2)\)处加点即可。

同列的做法类似。

C. A-B Palindrome

首先,由于是回文串,有些?的位置填什么是已经确定了的。

统计字符串中,还需添加0的数量,还需添加1的数量,剩余?的数量,分别记为\(a, b, c\)。

那么如果\(c\)是偶数,那么\(a\)和\(b\)都必须是偶数。然后扫一遍,先填其中一种,再填另外一种。

如果\(c\)是奇数,那么,字符串的长度必须是奇数,\(a\)和\(b\)中必须有且只能有一个奇数,且字符串的中心为?。分类讨论,先填中心,转换成之前的情况处理。

D. Corrupted Array

其实\(b\)的顺序不会影响结果,为方便处理,不妨先将其升序排序。

假设\(x\)为\(b_i\),\(sum = \sum_{i = 1}^{n + 2} b_i\),那么\(\forall i \in [1, m -1]\),若\(sum - b_i - b_{m + 2} = b_{m + 2}\),则\(b\)除去\(b_i\)和\(b_{m + 2}\)就是一个可行解。

\(x\)也可能是\(b_{m + 2}\),特判一下就可以了。

E. Permutation by Sum

\(p_l, \dots, p_r\)的顺序其实不影响结果,不妨假设其为升序。

枚举\(p_l\)的值,可以\(O(n)\)判断是否有可行解。总的时间复杂度为\(O(n^2)\)。

判断

不妨假设\(\forall i \in [l+1, r], p_i = p_{i-1} + 1\)。记此时\(\sum_{i = l}^r p_i = t\)

从右边开始处理,若\(t > s\),则后续无论怎么搞,都无法满足条件。

若\(t < s\),则可以放大当前元素。每次放大不能放大到超过\(s\),也不能放大到违反升序的假设,即放大存在上界\(p_i + min(s - t, ma - p_i)\)。其中,\(ma\)表示第\(i\)个位置,不违反升序假设的最大值。

易得:每次尽可能放大是最优解之一。

然后模拟一下就完事了。

F. Education

假设最终Polycarp停在第\(i\)个位置。那么,对于之前的位置,能晋升就晋升是最优的。

贪心+模拟完事。

G. Short Task

由于要找满足条件的最小的\(n\),所以对于一个因子集合,每个因子只出现一次是最佳的。

由此,除\(1\)和\(n\)本身外,可以只考虑素因子以及素因子的组合。

然后就是欧拉筛跑一下。

假设当前已经得到了\(d(n) = c\),若加入一个新的素因子\(p\),那么\(d(np) = c(p+1)\)。

假设当前已经得到了\(d(n) = c\),若删除一个重复的素因子\(p\),那么\(d(n) = c - pd(\frac{n}{p})\)。

上一篇:Codeforces Round #713 (Div. 3)题解


下一篇:求最大边/最小边的比值最小的路径 codevs 1001 舒适的路线