题目链接：CF936C Lock Puzzle ↗
题目描述#
探险家发现了一个保险箱，里面有大量的宝藏。
保险箱上有一个密码锁，初始时显示的是一个长度为的小写字母字符串。探险家发现，当密码锁上显示的是字符串时，这个密码锁就会打开。
密码锁显示的字符串可以通过形如shift x的指令改变。要执行这个指令，探险家需要在到的范围内（包含和）选择一个。此时，设屏幕上显示的字符串（其中的长度为），那么这个字符串会变为（表示反转后的结果）。
比如，如果屏幕上当前显示，那么执行shift 4后屏幕上会显示，因为，，。
探险家担心如果执行了太多了shift操作，这个密码锁就会永远锁定。因此，他会给你和字符串和，并且请你给出一个步骤数不大于的解锁方案。请注意无需最小化步骤数。
输入格式#
第一行一个整数，为字符串和的长度。
随后两行分别输入小写字母构成的字符串和，表示初始时屏幕显示的字符串以及解锁前需要得到的字符串。
输出格式#
如果不可能打开密码锁，输出-1。
否则，第一行输出一个整数，表示需要的操作数量。第二行输出个空格隔开的整数，其中代表执行操作。
数据范围#
无解情况#
显然，只有当构成的可重集合与不同时，问题是无解的。
设计递归#
假设当前屏幕上字符串（此后称为）前缀是，我们考虑再将两个指定的字符和加进前缀。
手玩一下，很容易就可以发现一个非常好的做法：
------ Add 2 chars ------
abc....x..... Find x
~~~~~~ Step 1
.....xabc....
~~~~ Step 2
..y......xabc Find y
~~~~~~~~~~ Step 3
cbax........y
~ Step 4
ycbax........此时前缀变成了。
整理一下信息，我们发现，若要在的前缀上构造出长度为的字符串，那么只要先在的前缀上构造出，然后再令，，执行上述步骤即可。这样，我们就可以递归解决问题。
边界条件#
不难发现，以上递归不能处理的情况是和。
对于，无需执行任何操作，直接返回即可。
对于，我们要将（下面称之为）字符放到开头。使用下面方法即可：
------ Get init char ------
......x..... Find x
~~~~~ Step 1
...........x
~ Step 2
x...........分析步骤数#
如果是奇数，那么需要先使用步来将第一个字符放到开头（边界条件），然后随后还要使用步进行递归构造。最大可以取到，那么步骤数是，完全没问题。
如果是偶数，只需要使用步进行递归构造。最大可以取到，步骤数是，同样没问题。
分析复杂度#
只论递归的话，复杂度。
如果考虑使用暴力算法进行操作和字符查找，总时间复杂度为。而时限有秒，因此
具体实现#
可以发现，递归时要求构造为前缀的字符串，要么是的子串，要么是的子串反转。
设计递归函数时，传入三个参数l,r,d，其中为时表示是子串，为时表示子串反转。如果，那么子串区间为，否则为。
这种设计比较容易实现。
代码#
// status: [Accepted]
// oj: [luogu]
#include<bits/stdc++.h>
using namespace std;
/*
------ Get init char ------
......x..... int idx = lastIndexOf(x);
~~~~~ do_shift(n-idx-1);
...........x
~ do_shift(1);
x...........
------ Add 2 chars ------
abc....x..... int idx = lastIndexOf(x);
~~~~~~ do_shift(n-idx);
.....xabc....
~~~~ do_shift(idx-len+2);
..y......xabc idx = indexOf(y);
~~~~~~~~~~ do_shift(n-idx-1);
cbax........y
~ do_shift(1);
ycbax........
*/
int n;
string s;
string t;
// 存储答案
vector<int> ans;
// 进行shift操作，并记录到答案中 （此处直接在s串上操作）
void do_shift(int x) {
ans.push_back(x);
string tmp = s.substr(s.length()-x);
s = string(x,' ') + s.substr(0,s.length()-x);
for(unsigned i=0;int(i)<x;i++) {
s[x-i-1] = tmp[i];
}
}
// 检查能否完成任务。如果能，正常返回，否则直接输出-1并结束程序
void test() {
int st[26];
for(int i=0;i<26;i++) {
st[i] = 0;
}
for(int i=0;i<n;i++) {
st[s[i]-'a'] ++;
st[t[i]-'a'] --;
}
for(int i=0;i<26;i++) {
if(st[i]) {
cout<<-1<<endl;exit(0);
}
}
return;
}
// 将t的子串或子串反转形式构造为s的前缀（此处直接在s串上操作）
void buildString(int l,int r,int d) {
int len = (r-l)*d+1;
// 边界判断
if(len==0) return;
if(len==1) {
int idx = s.find_last_of(t[l]);
// 直接忽略掉x==0的shift操作
if(n-idx-1 > 0) do_shift(n-idx-1);
do_shift(1);
return;
}
// 递归构造
buildString(r-d,l+d,-d);
// 加入2个新的字符
char x = t[r];
char y = t[l];
int idx = s.find_last_of(x);
do_shift(n-idx);
if(idx-len+2 > 0) do_shift(idx-len+2);
idx = s.find(y);
do_shift(n-idx-1);
do_shift(1);
return;
}
// 输出最终答案
void print() {
cout<<ans.size()<<'\n';
for(unsigned i=0;i<ans.size();i++) {
if(i) cout<<' ';
cout<<ans[i];
}
cout<<endl;
}
int main() {
ios::sync_with_stdio(false);
cin>>n>>s>>t;
// 测试能否完成
test();
// 构造
buildString(0,n-1,1);
// 该函数在s!=t时会RE，用于在调试时快速判断是否写挂
assert(s==t);
// 输出结果
print();
}
评测记录：R24483982 ↗