题目链接：CF936C Lock Puzzle
题目描述
探险家发现了一个保险箱，里面有大量的宝藏。
保险箱上有一个密码锁，初始时显示的是一个长度为n的小写字母字符串s。探险家发现，当密码锁上显示的是字符串t时，这个密码锁就会打开。
密码锁显示的字符串可以通过形如shift x的指令改变。要执行这个指令，探险家需要在0到n的范围内（包含0和n）选择一个x。此时，设屏幕上显示的字符串p = \alpha\beta（其中\beta的长度为x），那么这个字符串会变为\beta^{R}\alpha（\beta^{R}表示\beta反转后的结果）。
比如，如果屏幕上当前显示abcacb，那么执行shift 4后屏幕上会显示bcacab，因为\alpha=ab，\beta=cacb，\beta^{R}=baca。
探险家担心如果执行了太多了shift操作，这个密码锁就会永远锁定。因此，他会给你n和字符串s和t，并且请你给出一个步骤数不大于6100的解锁方案。请注意无需最小化步骤数。
输入格式
第一行一个整数n，为字符串s和t的长度。
随后两行分别输入小写字母构成的字符串s和t，表示初始时屏幕显示的字符串以及解锁前需要得到的字符串。
输出格式
如果不可能打开密码锁，输出-1。
否则，第一行输出一个整数k\ (0\leq k \leq 6100)，表示需要的操作数量。第二行输出k个空格隔开的整数x_i\ (0\leq x_i \leq n)，其中x_i代表执行操作shift\ x_i。
数据范围
1 \leq n \leq 2000
无解情况
显然，只有当s构成的可重集合与t不同时，问题是无解的。
设计递归
假设当前屏幕上字符串（此后称为p）前缀是abc，我们考虑再将两个指定的字符x和y加进前缀。
手玩一下，很容易就可以发现一个非常好的做法：
------ Add 2 chars ------
abc....x..... Find x
~~~~~~ Step 1
.....xabc....
~~~~ Step 2
..y......xabc Find y
~~~~~~~~~~ Step 3
cbax........y
~ Step 4
ycbax........
此时前缀变成了{\color{red}y}cba{\color{red}x}。
整理一下信息，我们发现，若要在p的前缀上构造出长度为len\ (len \geq 2)的字符串t_1[0..len-1]，那么只要先在p的前缀上构造出t_1[1..len-2]^{R}，然后再令x=t_1[len-1]，y=t_1[0]，执行上述步骤即可。这样，我们就可以递归解决问题。
边界条件
不难发现，以上递归不能处理的情况是len=0和len=1。
对于len=0，无需执行任何操作，直接返回即可。
对于len=1，我们要将t_1[0]（下面称之为x）字符放到p开头。使用下面方法即可：
------ Get init char ------
......x..... Find x
~~~~~ Step 1
...........x
~ Step 2
x...........
分析步骤数
如果n是奇数，那么需要先使用2步来将第一个字符放到p开头（边界条件），然后随后还要使用4 \times ((n-1)/2)步进行递归构造。n最大可以取到1999，那么步骤数是4000，完全没问题。
如果n是偶数，只需要使用4 \times (n/2)步进行递归构造。n最大可以取到2000，步骤数是4000，同样没问题。
分析复杂度
只论递归的话，复杂度O(n)。
如果考虑使用暴力算法进行shift操作和字符查找，总时间复杂度为O(n^2)。而时限有2秒，因此O(\text{能过})
具体实现
可以发现，递归时要求构造为前缀的字符串，要么是t的子串，要么是t的子串反转。
设计递归函数时，传入三个参数l,r,d，其中d为1时表示是子串，d为-1时表示子串反转。如果d=1，那么子串区间为[l..r]，否则为[r..l]。
这种设计比较容易实现。
代码
Talk\ is\ cheap,\ show\ me\ the\ code
// 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
Comments | NOTHING