本文共 1614 字，大约阅读时间需要 5 分钟。
给个串，只能用操作shift x表示把后面x个字符翻转后放到串的前面。问s串怎么操作能变t串。n<=2000，操作次数<=6100。
打VP时这转来转去的有点晕。。。
可以想一种逐步构造的方法，即从一个小的完成构造的部分通过一顿操作，在不影响这部分的前提下扩展。
好吧我看题解了，直接丢图，是从abc扩展成xabcy的方法，如果反了就把他最后再倒过来。
操作次数是$\frac{5}{2}n$的，复杂度$kn$，$k$指操作次数。
1 //#include 2 #include 3 #include 4 #include 5 //#include 6 #include 7 //#include 8 //#include 9 #include 10 using namespace std;11 12 int n;13 #define maxn 1001114 char s[maxn],t[maxn];int cnts[30],cntt[30],ans[maxn],lans=0;15 16 char tmp[maxn];17 void shift(int x)18 {19 if (x==0) {lans--; return;}20 memcpy(tmp,s,sizeof(char)*(n+3));21 int cnt=0; x=n-x+1;22 for (int i=n;i>=x;i--) s[++cnt]=tmp[i];23 for (int i=1;i >1,p2=p1;41 int p=findpos(p1,n); p1--; p2++;42 if (p!=n) {ans[++lans]=n-p; shift(n-p);}43 bool rev=0;44 for (int now=1,p;p1;p1--,p2++,now+=2,rev^=1)45 {46 if (rev==0) p=findpos(p1,n-now); else p=findpos(p2,n-now);47 shift(ans[++lans]=n-p);48 shift(ans[++lans]=n);49 shift(ans[++lans]=now);50 if (rev==0) p=findpos(p2,n); else p=findpos(p1,n);51 shift(ans[++lans]=n-p+1);52 shift(ans[++lans]=p-now-2);53 }54 if (n&1) { if (rev) shift(ans[++lans]=n);}55 else56 {57 if (rev) shift(ans[++lans]=n-1);58 else59 {60 shift(ans[++lans]=n-1);61 shift(ans[++lans]=1);62 shift(ans[++lans]=n);63 }64 }65 66 printf("%d\n",lans);67 for (int i=1;i<=lans;i++) printf("%d ",ans[i]);68 return 0;69 }
还有一种好理解的逐个字符构造，也是从后往前。
比如说现在串是AzB，A的前缀已经是t的一个后缀，z是想加在A前面的字符，B是剩下的。然后这样：AzB->B'zA'->AB'z->zAB'。搞定。操作次数3*n。
（好吧这是写的）
转载于:https://www.cnblogs.com/Blue233333/p/8477002.html
