[Codeforces Round #467 (Div. 1)][Codeforces 936C] Lock Puzzle

        题目大意：定义对字符串S的操作shift x为\[S'=B^RA\ (S=AB,length(B)=x),0 \leq x \leq length(S)\]

        例如字符串\(S=bcacab\)经过操作shift 4后变为\(S'=bacabc\)。给出两个长度为\(n\)的字符串\(S,T\)，要求在6100步之内将\(S\)变成\(T\)，求操作方案。\((n \leq 2000\)

        题解：可以从数据范围中看出来，如果能每次将一个字符在3步内移到正确的位置的话，就肯定能完成。

        如果我已经将最后m位字符放在了合适的位置，现在我要把本应在第m+1位的字符x移动进来，设它的位置为pos，则当前有\[S=AxBC,length(A)=pos-1,length(C)=m\]

        我可以进行三次操作：1.shift n-pos-1   2.shift 1   3.shift n

        三次操作后S分别变化为：\[S_1=C^R B^R A x\] \[S_2=x C^R B^R A\] \[S_3=A^R B C x\]

        三次操作之后，变到了最后，而\(C\)字符串保持不变。也就是说，只要我们每次将本应在第i位的字符（i从n到1）换到最后一位，我们就能够在\(3n\)次操作之后得到\(T^R\)，最后再执行一次shift n即可得到\(T\)。

#include <bits/stdc++.h>
using namespace std;
const int maxn=2010;

int cnt[26][2];
char s[maxn],t[maxn],tmp[maxn];
int ans[maxn<<2],ansn;
int n;

void Reverse(int N)
{
	for (int i=0;i<N;i++) tmp[i]=s[n-i-1];
	for (int i=N;i<n;i++) tmp[i]=s[i-N];
	for (int i=0;i<n;i++) s[i]=tmp[i];
}

int main()
{
	scanf("%d",&n);
	scanf("%s%s",s,t);
	for (int i=0;i<n;i++) cnt[s[i]-'a'][0]++;
	for (int i=0;i<n;i++) cnt[t[i]-'a'][1]++;
	for (int i=0;i<26;i++) if (cnt[i][0]!=cnt[i][1])
	{
		printf("-1\n");
		return 0;
	}
	for (int i=n-1;i>=0;i--)
	{
		int pos=0;
		while (s[pos]!=t[i]) pos++;
		if (i==n-1)
		{
			Reverse(n-1-pos);
			ans[++ansn]=n-1-pos;
			continue;
		}
		Reverse(n-pos-1);
		Reverse(1);
		Reverse(n);
		ans[++ansn]=n-pos-1;
		ans[++ansn]=1;
		ans[++ansn]=n;
	}
	Reverse(n);
	ans[++ansn]=n;
	printf("%d\n",ansn);
	for (int i=1;i<=ansn;i++) printf("%d ",ans[i]);
	printf("\n");
	return 0;
}

        题解的做法为\(\frac{5}{2}n\)的，做法和一个操作次数为\(2n\)的做法差不多，就说一下\(2n\)的做法。\[S=AxByCD\] \[S_1=d^RC^RyB^RAx\] \[S_2=xD^RC^RyB^RA\] \[S_3=A^RByxD^RC^R\] \[S_4=CA^RByxD^R\]