[AGC037E] Reversing and Concatenating 题目解法

题目链接

点击打开链接

题目解法

很妙的一道题

首先考虑最大化开头出现的最小字母( \(c\) )的个数
可以发现，通过一次操作可以截出后缀为 \(c\) 的序列，之后的操作每次可以倍长 \(c\) 的长度

如果倍长 \(k-1\) 次之后的长度仍然 \(<n\)，那么我们需要考虑在保证上面的条件最优的前提下，最小化后面的字母的字典序
方便起见，先倍长一遍数组，令最长的全 \(c\) 段的左右端点分别为 \(l,r\)，这样可以解决 \(r=n\) 时可以倍长 \(k\) 次的特殊情况

手动模拟一下，发现后面的字母分别为 \(s_{l-1},s_{l-2},...\)，所以我们只需要找到最优的 \(l,r\) 即可
暴力比较不难做到时间复杂度 \(O(n^2)\)

个人认为这道题难点在于想到手动模拟后面的字母

#include <bits/stdc++.h>
#define F(i,x,y) for(int i=(x);i<=(y);i++)
#define DF(i,x,y) for(int i=(x);i>=(y);i--)
#define ms(x,y) memset(x,y,sizeof(x))
#define SZ(x) (int)x.size()-1
#define pb push_back
using namespace std;
typedef long long LL;
typedef unsigned long long ull;
typedef pair<int,int> pii;
template<typename T> void chkmax(T &x,T y){ x=max(x,y);}
template<typename T> void chkmin(T &x,T y){ x=min(x,y);}
inline int read(){
    int FF=0,RR=1;
    char ch=getchar();
    for(;!isdigit(ch);ch=getchar()) if(ch=='-') RR=-1;
    for(;isdigit(ch);ch=getchar()) FF=(FF<<1)+(FF<<3)+ch-48;
    return FF*RR;
}
const int N=10100;
int n,k,ans[N],le[N];
char str[N];
void UPD(int l){ F(i,1,n) ans[i]=str[i+l-1];}
void upd(int l){
    F(i,1,n){
        if(str[i+l-1]<ans[i]){ UPD(l);return;}
        if(str[i+l-1]>ans[i]) return;
    }
}
int main(){
    n=read(),k=read();scanf("%s",str+1);
    F(i,1,n) str[n*2-i+1]=str[i];
    int mnc=1e9;
    F(i,1,n) chkmin(mnc,(int)str[i]);
    F(i,1,n<<1) le[i]=(str[i]==mnc)?le[i-1]+1:0;
    int mx=0;
    F(i,1,n<<1) chkmax(mx,le[i]);
    int lenth=mx;
    if(lenth>=n){ F(i,1,n) putchar(mnc);puts("");exit(0);}
    if(mx>1)
        F(i,1,k-1){
            lenth*=2;
            if(lenth>=n){ F(j,1,n) putchar(mnc);puts("");exit(0);}
        }
    ms(ans,0x3f);
    if(k==1){
        F(i,1,n) upd(i);
        F(i,1,n) putchar(ans[i]);puts("");exit(0);
    }
    F(i,1,n+mx) if(le[i]==mx) upd(i-le[i]+1);
    F(i,1,lenth) putchar(mnc);
    F(i,mx+1,n-lenth+mx) putchar(ans[i]);puts("");
    fprintf(stderr,"%d ms\n",int(1e3*clock()/CLOCKS_PER_SEC));
    return 0;
}