自动搬运

查看原文

来自洛谷，原作者为

	fz20181223 exlg伪犇验证

搬运于2025-08-24 22:32:45，当前版本为作者最后更新于2021-08-07 15:59:28，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

我们对 $6$ 个字符进行变化，我们不难发现变换是这样的（此处显示的是一开始是第几个字符）：

一开始：$1,2,3,4,5,6$

第一次：$1,6,2,5,3,4$

第二次：$1,4,6,2,3,5$

第三次：$1,5,4,2,6,3$

第四次：$1,3,5,6,4,2$

第五次：$1,2,3,4,5,6$

这启示我们，变换序列是存在循环的！

经过多次尝试，我们发现，字符串长度为 $4$，循环次数为 $3$，但是如果字符串长度为 $8$，循环次数为 $4$，而当字符串长度为 $11$，循环次数为 $6$……得出结论：字符串长度与单词循环次数没有直接关系。

此时我们可以考虑通过代码暴力算出对于长度为 $n$ 的单词单次循环次数。写一个暴力的变换以及对应的检查就行了。思路就是先压一个序列，让它不停地变换直到回到原来压的的序列的样子（比如我压的就是 $1$ 到 $n$）。

此时我们有了单次循环次数，我们可以大大地减少操作的次数。而对于后续的操作，我们可以推出它从最后一次循环结束后它又做了多少次变换 $r$，即 $r \gets X\bmod \operatorname{solve}(|s|)$（其中 $X$ 和 $s$ 均为原题目中的变量，$\operatorname{solve}$ 函数为求循环次数的函数，下同）。

根据循环的特征，在一个单次循环消耗 $rd$ 次的循环中，如果我们做了 $x$ $(x<rd)$ 次，要想还原，我们可以倒推 $x$ 次，也可以再做 $rd-x$ 次，所以，我们只需让现有的字符串再变换 $\operatorname{solve}(|s|)-r$ 次就行了。

另附：AC 代码（不要抄！）。

#include<bits/stdc++.h>
using namespace std;
string st;int x,rd,rin;
vector<int>a;
bool check(int t){
	if(t==0) return 0;
	for(int i=0;i<a.size();++i){
		if(a[i]!=i+1) return 0;
	}
	return 1;
}
int solve(int n){
	a.clear();
	int i;
	for(i=1;i<=n;++i) a.push_back(i);
	for(i=0;;++i){
//		printf("%dth change:",i);
//		for(int j=0;j<n;++j) printf("%d ",a[j]);
//		puts("");
		if(check(i)) break;
		for(int j=0;j<a.size()>>1;++j){ 
			int tmp=a.back();
			a.pop_back();
			a.insert(a.begin()+(j<<1|1),tmp);
		}
	} 
//	printf("change time:%d",i);
	return i;
}
int main(){
	scanf("%d",&x);
	cin>>st;
	rd=solve(st.size());
	rin=x%rd;
	for(int i=0;i<rd-rin;++i){
		for(int j=0;j<st.size()>>1;++j){ 
			string tmp="";
			tmp+=(char)st[st.size()-1];
			st.erase(st.size()-1,1);
			st.insert(j<<1|1,tmp);
		}
	}
	cout<<st;
	return 0;}