AGC037E

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

---

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

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

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

那么当(N> lencdot 2^{k-1})时该怎么办呢？(N leq 5000)，直接(O(n^2))暴力上，查出一开始(U)的最小子串，然后输出(lencdot 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]!='');
	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;
}