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

A. Mean Inequality

题解

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

代码

Java

C++

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

C++

C. Potions

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

Codeforces Round #723 Potions (Hard/Easy) 题解 (Java/C++)

题解首先，如果没有任何限制，我们当然会喝光所有的药水。而事实上，唯一的限制是生命值不能小于0。那么什么时候生命值会小于0呢？显然是喝的正数的药水的总和小于了喝的负数的药水的总和。

xloypaypa的博客xloypaypa

点击上面链接查看具体题解

D. Kill Anton

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

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

题解首先考量Anton是怎么还原才能做到最快。我们发现，Anton其实就是从左往右每次恢复一位。比如从NNOTA恢复到ANTON的第一步是恢复成ANNOT。于是我们想到，大方向就是把字母尽可能拉远，让他每一步都尽可能花费尽可能多的次数。

xloypaypa的博客xloypaypa

点击上面链接查看具体题解

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$.

xloypaypa的博客xloypaypa

点击上面链接查看具体题解