【AtCoder Grand Contest 037 E】Reversing and Concatenating | Mrsrz's blog

贪心，构造。

题目大意：

给定长度为 $n$ 的字符串 $s$，和 $k$，要求进行 $k$ 次如下操作：

• 令 $s’=s+\mathrm{reverse}(s)$。
• 令 $s$ 为 $s’$ 中一个长度为 $n$ 的子串。

要求最小化 $k$ 次操作后 $s$ 的字典序。

题解：

我们考虑贪心地构造答案。

第一次操作的时候，我们把一个最小的字符放到 $s$ 的末尾。那么第二次操作的时候，$s’$ 中就有了两个连续的最小字符。我们把它放末尾，重复这个操作。这个字符的个数每次扩大一倍，所以在 $1+\lceil\log_2 n\rceil$ 次内，整个串都可以变为最小的字符。字典序显然无法更小。

当 $k$ 很小的时候，我们直接模拟这个过程。我们发现，这个过程实际上相当于每次取 $s’$ 中反串字典序最小的，长度为 $n$ 的串作为新的 $s$，所以可以 $O(n^2)$ 完成。

时间复杂度 $O(n^2\log n)$。

Code：

#include<iostream>
#include<string>
#include<algorithm>
using namespace std;
string s;
int n,k;
int main(){
    cin>>n>>k>>s;
    s+=string(s.rbegin(),s.rend());
    if(k>20)cout<<string(n,*min_element(s.begin(),s.end()))<<'\n';else{
        while(k--){
            string t(s,0,n);
            reverse(t.begin(),t.end());
            for(int i=1;i<=n;++i){
                string p(s,i,n);
                reverse(p.begin(),p.end());
                if(p<t)t=p;
            }
            s=string(t.rbegin(),t.rend())+t;
        }
        s.erase(0,n);
        cout<<s<<'\n';
    }
    return 0;
}