Codeforces Round #723 ABCDE 题解 (Java/C++)

A. Mean Inequality

题解

将数组排序。然后将数组分成两半。每次从两半中各取一个数即可。

代码

Java

Submission #117684818 - Codeforces
Codeforces. Programming competitions and contests, programming community

C++

Submission #117728821 - Codeforces
Codeforces. Programming competitions and contests, programming community

B. I Hate 1111

题解

考虑1111。我们发现1111=11*101。同理可得,我们只需要考虑这个数能不能用11和111构造出来即可。

令$x=a\cdot 11 + b\cdot 111$。当$b>11$时,有$x=a\cdot 11 + 11 \cdot 111 + (b-11)\cdot 111=(a+111)\cdot 11 + (b-11) \cdot 111$。于是我们如果有解,则必然可以找到$b<11$得解。暴力枚举b即可。

代码

Java

Submission #117686818 - Codeforces
Codeforces. Programming competitions and contests, programming community

C++

Submission #117729243 - Codeforces
Codeforces. Programming competitions and contests, programming community

C. Potions

我还专门想了一下,看有没有$n^2$的做法看能不能只过Easy不过Hard。我是没有想到。这个题也比较显然。就是维护前缀和,只是在前缀和出现负数的时候,往前找最毒的药水吐出来即可。

Codeforces Round #723 Potions (Hard/Easy) 题解 (Java/C++)
题解首先,如果没有任何限制,我们当然会喝光所有的药水。而事实上,唯一的限制是生命值不能小于0。那么什么时候生命值会小于0呢?显然是喝的正数的药水的总和小于了喝的负数的药水的总和。
点击上面链接查看具体题解

D. Kill Anton

推了一半天,最后的结论是,4各字母最终必然各自连续出现。于是就暴力枚举4各字母的排列,看看哪种排列开销大即可。

Codeforces Round #723 Kill Anton 题解 (Java/C++)
题解首先考量Anton是怎么还原才能做到最快。我们发现,Anton其实就是从左往右每次恢复一位。比如从NNOTA恢复到ANTON的第一步是恢复成ANNOT。于是我们想到,大方向就是把字母尽可能拉远,让他每一步都尽可能花费尽可能多的次数。
点击上面链接查看具体题解

E. Oolimry and Suffix Array

其实只需要推导出第四组样例基本上这个题目就做出来了。这个题的关键点是考虑清楚当有字母重复的时候怎么处理。

Codeforces Round #723 Oolimry and Suffix Array 题解 (Java/C++)
题解令原字符串为c。首先我们可以注意到一个性质:对于i<j,那么一定有$c_{s[i]}\leq c_{s[j]}$。比如对于$[3,2,4,1,0,5,6]$,至少有$c_3\leq c_2\leq c_4\leq c_1\leq c_0\leq c_5\leq c_6$.
点击上面链接查看具体题解
展示评论