Codeforces Global Round 11/Codeforces1427 ABCD

AC代码

A. Avoiding Zero

记\(sum_i = \sum_{j=1}^i a_i\)。易得\(sum_n\)为定值,故若\(sum_n = 0\),则无解。

若\(sum_n < 0\),将\(a\)升序排序后作为\(b\),此时\(sum_i\)先降后升,最大值在\(sum_1\)处或\(sum_n\)处取到,这两个值都小于零,所以必定不会存在\(sum_i = 0\)的点。

同理,若\(sum_n > 0\),此时将\(a\)降序排序后作为\(b\)。

B. Chess Cheater

遍历字符串,统计胜场数,败场数和初始分数\(score\)。

特判\(k = 0\)和作弊后可以全胜的情况。

若全败,则消耗一个\(k\)且加一分后转移到只有一个胜场的情况。

若只有一个胜场,那么就只修改和胜场相邻的败场,每次修改固定加两分,即\(score = socre + 2k\)。

若胜场数大于等于二,那么对于有败场隔开的两个胜场,记中间有\(x\)场败场,则将这\(x\)场全都改为胜场后可以加\(2x + 1\)分。优先填\(x\)较小的败场。

C. The Hard Work of Paparazzi

早年涛爷出了道弹钢琴,和这题很像,就是空间范围是1*12。然后最近几天我自己想着出题,就想着把之前涛爷那道题给他扩展到二维,大概\(r = 5\),题目背景本来已经想好了用DOTA2暂停的时候打米波小游戏(就是打地鼠),现在看来已经不需要了。

令\(dp_i\)表示只考虑前\(i\)个点,并且在\(i\)处拍照的答案。

\(dp_i\)可以从\(dp_j\)转移过来,其中\(1 \le j \le i - 1\)。如果\(t_i - t_j \ge 2r\),那么必定可以从\(j\)点转移到\(i\);否则就需要判断曼哈顿距离是否小于等于\(t_i - t_j\)。

因为\(t_i < t_{i+1}\),所以至多枚举\(2r\)个需要判断曼哈顿距离的点,再往前的点就一个前缀最大值解决了。

复杂度为\(O(2rn)\),足够优秀。

D. Unshuffling a Deck

想到构造方法后,就是简单模拟了。

\(n\)为奇数的时候,先找到\(n\)的位置,然后通过至多一个操作让\(c_n = n\)。

然后找到\(n - 1\)的位置,通过一个操作让\(c_1 = n, c2 = n - 1\)。

然后找到\(n - 2\)的位置,通过一个操作让\(c_n = n, c_{n - 1} = n - 1, c_{n - 2} = n - 2\)。

然后找到\(n - 3\)的位置,通过一个操作让\(c_1 = n, c2 = n - 1, c3 = n - 2, c4 = n - 3\)。

以此类推,每次操作让一个数字移动到对应的位置,至多\(n\)次操作过后,\(c_i = i\)就会满足了。

\(n\)为偶数的时候,上述方法会使\(c_i = n - i + 1\)。这个时候稍微改改,先将\(1\)移动到数组末尾,然后让前两个数为\(1, 2\),然后让后三个数为\(3, 2, 1\),以此类推。

E. Xum

zfc说是线性基,然而我不会线性基。

上一篇:考题第三题


下一篇:Codeforces Round #678 (Div. 2)【ABCD】