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

题解

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

我们先考虑只有两个字母的情况,比如N和A。
比如AANNNNN,显然NNNNNAA的开销最大。
比如ANANNNN,显然也是NNNNNAA。进一步对于ANNANNN,显然最远的也是NNNNNAA,而非AANNNNN。
最后对于NNAANN,我们发现AANNNN, NNNNAA和ANNNNA的开销都是一样的。
于是我们如果只看字母A。我们发现,当只考虑要求恢复A字母的开销尽可能大的话,A字母总能通过把A字母全部集中于左侧或者右侧来实现。

我们现在来思考字母N。我们发现没什么需要思考的。因为在上面的例子中,一旦A恢复了之后N自然也就恢复了。因此恢复字母N的开销是0。

接着我们考虑三个字母:NAT。
对于ATATNNN。我们首先想到把A堆到右边,得到TTNNNAA。在这之后我们发现T字母可以进一步提高开销,于是得到NNNTTAA。为什么呢?
我们先来看TTNNNAA的恢复过程:TTNNNAA -> ATTNNNA -> ATATNNN。相当于是只恢复A,整个过程我们直接可以忽略T和N。
那怎么才能迫使A恢复之外还要考虑T和N呢?那么显然,A堆到右边之后,我们对剩下的TTNNN再做一次同样的操作,得到NNNTT是开销最大的。于是结合A,我们得到NNNTTAA。

所以,做法是:1. 我们每次把一个字母堆到最左或者最右。2. 只考虑剩下的字母重复操作1。

上面这种做法理论上是可以做的。但是这个做法写起来太麻烦了。根据上面做法,我们可以发现,最终的结果,四个字母一定是连续的。也就是必然类似NNNAATTTO,而不会出现NATONAT这样的。
那我们$A_4^4$的枚举字母的排序,然后计算每种排列的开销,选择最大的即可。

代码

Java

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

C++

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

吐槽

这基因由ANOT四个字母组成,这题确定不是北约(NATO)出的?

展示评论