AGC037E - Reversing and Concatenating 题解

原题链接：E - Reversing and Concatenating
题目大意：给定一个字符串长度为\(N\)的字符串\(S\)，每次将它和它的反串拼起来，然后从中截取一段长度为\(N\)的子串，并用这个字串覆盖原串，进行\(K\)次这样的操作后，使得所得串字典序最小。

题解：首先，我们可以发现，若令\(S\)串中的最小字符为\(c\)，那么最终的串不可能比\(N\)个\(c\)还要小。

然后，如果原串中\(c\)的连续长度最多为\(len\)，那么每次一定会使\(c\)的连续串长度翻倍。

所以，\(K\)的数据范围是唬人的，当\(N \leq len\cdot 2^{k-1}\)是，答案就是\(N\)个\(c\)。

那么当\(N> len\cdot 2^{k-1}\)时该怎么办呢？\(N \leq 5000\)，直接\(O(n^2)\)暴力上，查出一开始\(U\)的最小子串，然后输出\(len\cdot 2^{k-1}\)个\(c\)，再按着顺序输出后面的就可以了。

接下来是代码：

#include <cstdio>
const int Maxn=10000;
char s[Maxn+5];
int n,k;
char *ans;
bool check(char *a,char *b){
    for(int i=1;i<=n;i++){
        if(a[i]<b[i]){
            return 1;
        }
        if(a[i]>b[i]){
            return 0;
        }
    }
    return 0;
}
int main(){
    scanf("%d%d",&n,&k);
    scanf("%s",s+1);
    while(s[++n]!='\0');
    n--;
    for(int i=1;i<=n;i++){
        s[(n<<1)-i+1]=s[i];
    }
    ans=s;
    for(int i=1;i<=n;i++){
        if(check(s+i-1,ans)){
            ans=s+i-1;
        }
    }
    int len=1;
    while(len<=n&&ans[++len]==ans[1]);
    len--;
    if(k>=15||(len*(1<<(k-1))>=n)){
        for(int i=1;i<=n;i++){
            putchar(ans[1]);
        }
        puts("");
    }
    else{
        int now=n-(len*(1<<(k-1)));
        for(int i=1;i<=(len*(1<<(k-1)));i++){
            putchar(ans[1]);
        }
        for(int i=1;i<=now;i++){
            putchar(ans[i+len]);
        }
        puts("");
    }
    return 0;
}

AGC037E - Reversing and Concatenating 题解

原文：https://www.cnblogs.com/withhope/p/12380757.html