APIO2019试机题khx
下面记(R(A))为(A)的反串
首先字符数量不相等可以直接判掉.考虑增量构造,每次把一个字符接到构造好的串后面,枚举到目标串的第(i)个字符(x),然后在前面没构造好的串里找到一个(x),记(x)前面为(A)串,后面为(B)串以及构造好的(C)串,然后可以做如下变化
[egin{matrix}& Axunderline{BC}\ o& R(C)R(B)Aunderline{b}\ o& underline{bR(C)R(B)A}\ o& R(A)BCxend{matrix}
]
做(n)次就好了,次数为(O(3n))
#include<bits/stdc++.h>
#define LL long long
#define il inline
#define re register
#define db double
using namespace std;
const int N=2000+10;
il int rd()
{
int x=0,w=1;char ch=0;
while(ch<'0'||ch>'9') {if(ch=='-') w=-1;ch=getchar();}
while(ch>='0'&&ch<='9') {x=(x<<3)+(x<<1)+(ch^48);ch=getchar();}
return x*w;
}
char cc[N],ss[N],tmp[N];
int n,c1[26],c2[26],an[N*3],ta;
int main()
{
//qwq
n=rd();
scanf("%s%s",cc+1,ss+1);
for(int i=1;i<=n;++i) ++c1[cc[i]-'a'];
for(int i=1;i<=n;++i) ++c2[ss[i]-'a'];
for(int i=0;i<26;++i)
if(c1[i]!=c2[i]) {puts("-1");return 0;}
for(int i=1;i<=n;++i)
{
int j=n-i+1;
while(cc[j]!=ss[i]) --j;
if(j==n) continue;
an[++ta]=n-j,an[++ta]=1,an[++ta]=n;
int m=0;
for(int k=j-1;k;--k) tmp[++m]=cc[k];
for(int k=j+1;k<=n;++k) tmp[++m]=cc[k];
tmp[++m]=cc[j];
memcpy(cc,tmp,sizeof(tmp));
}
printf("%d
",ta);
for(int i=1;i<=ta;++i) printf("%d ",an[i]);
return 0;
//qwq
}