题意略。
思路:
这个题目没做出来是因为缺少一个整体的构造思路。
正确的构造思路是不断地在s中去构造并且扩大t的后缀,构造好的后缀总是放在前面,然后不断地把它往后挤,最后将s构造成t。
比如:
现在在s中构造好的t的后缀为a(在s中体现为前缀),包含在了s的前缀中,为了继续扩大这个t的后缀,我们需要将z添加到A前。
也就是AzB,要把z添加到A前,保持a不动,a为A的前缀,也是t的构造好的后缀。
AzB — B`zA` — AB`z — zAB` 一共需要3次动作。
如果t的长度为len,那么我只需要3 * n次动作就可以完成了。
n最长又是2000,所以我们最多只需要6000次动作就可以了。小于6100,因此只要s和t的字符种类和个数一样就可以合法构造了。
详见代码:
#include<bits/stdc++.h>
using namespace std;string s,t,s1,t1,str1,str2,str3;
int len;
vector<int> ans;int main(){
std::ios::sync_with_stdio(false);
cin.tie();
cout.tie();
cin>>len;
cin>>s>>t;
s1 = s,t1 = t;
sort(s1.begin(),s1.end());
sort(t1.begin(),t1.end());
if(s1 != t1){
cout<<-<<endl;
return ;
}
for(int i = len - ;i >= ;--i){
str1 = str2 = str3 = "";
bool jud = false;
str2 = t[i];
for(int j = ;j < len;++j){
if(jud){
str3 += s[j];
continue;
}
if(s[j] == t[i] && j >= (len - - i)){
jud = true;
continue;
}
if(!jud) str1 += s[j];
}
reverse(str3.begin(),str3.end());
s = str2 + str1 + str3;
ans.push_back(len);
ans.push_back(str1.length());
ans.push_back();
}
cout<< * len<<endl;
for(int i = ;i < ans.size();++i){
cout<<ans[i];
if(i < ans.size() - ) cout<<' ';
else cout<<endl;
}
return ;
}