[洛谷题解] CF936C Lock Puzzle

题目链接:CF936C Lock Puzzle


题目描述

探险家发现了一个保险箱,里面有大量的宝藏。

保险箱上有一个密码锁,初始时显示的是一个长度为n的小写字母字符串s。探险家发现,当密码锁上显示的是字符串t时,这个密码锁就会打开。

密码锁显示的字符串可以通过形如shift x的指令改变。要执行这个指令,探险家需要在0n的范围内(包含0n)选择一个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和字符串st,并且请你给出一个步骤数不大于6100的解锁方案。请注意无需最小化步骤数。

输入格式

第一行一个整数n,为字符串st的长度。

随后两行分别输入小写字母构成的字符串st,表示初始时屏幕显示的字符串以及解锁前需要得到的字符串。

输出格式

如果不可能打开密码锁,输出-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,我们考虑再将两个指定的字符xy加进前缀。

手玩一下,很容易就可以发现一个非常好的做法:

------ 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=0len=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,其中d1时表示是子串,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

点赞

发表评论

电子邮件地址不会被公开。必填项已用 * 标注