题目链接
题目解法
很妙的一道题
首先考虑最大化开头出现的最小字母( \(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;
}