CF 936C Lock Puzzle—

题目：http://codeforces.com/contest/936/problem/C

　　玩了一个小时，只能想出 5*n 的方法。

　　经过一番观察？考虑这样构造：已经使得 A 串的一个后缀 = B 串的一个前缀，考虑再把一个正确的字符挪到 A 串的最后面。

　　设该字符为 x 、它之前有 len 个字符、当前已经弄好的结尾长度为 l2 。

　　进行这5个操作：n-len , len , n-len-l2 , l2 , n-l2+1 。

　　思路就是：

　　1&2：使得 x 变成结尾；

　　3：使 x 变成开头、原来做好的部分变成结尾；

　　4：原来做好的部分拼到 x 前面；

　　5：新的做好的部分变成后缀。

#include<cstdio>

#include<cstring>

#include<algorithm>

using namespace std;

const int N=,K=;

int n,m,ct[K];

char a[N],b[N];

void Rv(int l,int r)

{

  for(int i=l,j=r;i<j;i++,j--)

    swap(a[i],a[j]);

}

void To_tail(int x)

{

  char w=a[x];

  for(int i=x;i<n;i++)a[i]=a[i+];

  a[n]=w;

}

int main()

{

  scanf("%d%d",&n,&m);

  scanf("%s",a+); scanf("%s",b+);

  for(int i=;i<=n;i++)

    ct[a[i]-'a']++;

  for(int i=;i<=n;i++)

    ct[b[i]-'a']--;

  for(int i=;i<K;i++)

    if(ct[i]!=){puts("-1");return ;}

  if(m<*(n-)+){puts("-1");return ;}

  printf("%d\n",*(n-)+*(b[]!=a[n]));//not +2!!!

  int len=;

  if(b[]!=a[n])

    {

      for(int i=;i<=n;i++)

    if(a[i]==b[]){len=i-;break;}

      printf("%d %d ",n-len,len);

      Rv(,len); Rv(len+,n);

    }

  for(int l2=,ps=;l2<n;l2++,ps++)

    {

      for(int i=;i<=n;i++)

    if(a[i]==b[ps]){len=i-;break;}

      printf("%d %d %d %d %d ",n-len,len,

         n-len-l2,l2,n-l2-);

      Rv(len+,n-l2); To_tail(n-l2);

    }

  puts(""); return ;

}

　　刚才写着题解，忽然发现可以随随便便变成 3*n 的嘛！

　　1.n-len-1，使得 x 变成结尾，并且原来做好的部分倒序变成开头；

　　2.1，使 x 接在最前面；

　　3.n，整体翻转，就变成正序的“原来做好的部分”后面添了一个 x 了！

　　题解是 2.5*n 的。考虑做好的部分允许在过程中变成倒序的，然后一次5个操作往上添2个字符。

　　设现在 A 串的后缀是 B 串的 [ L , R ] 部分。考虑扩充成 [ L-1 , R+1 ] 。设 y 是要往 A 的最后面放的、 x 是要往“已经做好的部分”的前面放的。

　　1.把 x 露出来（放到结尾），此时原来做好的部分倒序在开头；

　　2.翻转整个序列，现在原来部分正序在结尾， x 在开头；

　　　　这一步很巧妙！这样可以让再做一步之后，原来部分的另一端露在开头；

　　3.原来部分接在最前面；此时原来部分是倒序；

　　4.找到 y 的位置，操作含 y 的对应后缀，这样 y 接在了“倒序的原来部分”的前面，并且整个部分在序列里面；

　　　　这一步的思想很大胆！允许做好的部分埋在序列中部；

　　5.操作后缀，使得做好的部分成为后缀；此时的做好部分是翻转过的状态，即原来按顺序对应的是 [ L , R ] 的话，现在是 [ R , L ] 。

#include<cstdio>

#include<cstring>

#include<algorithm>

using namespace std;

const int N=,M=,K=;

int n,m,ct[K],p[M],tot;

char a[N],b[N],c[N];

void cz(int x)

{

  for(int i=n-x+,j=x;i<=n;i++,j--)

    c[j]=a[i];

  for(int j=x+,i=;j<=n;i++,j++)

    c[j]=a[i];

  memcpy(a,c,sizeof c); p[++tot]=x;

}

int main()

{

  scanf("%d%d",&n,&m);

  scanf("%s",a+); scanf("%s",b+);

  for(int i=;i<=n;i++)

    ct[a[i]-'a']++;

  for(int i=;i<=n;i++)

    ct[b[i]-'a']--;

  for(int i=;i<K;i++)

    if(ct[i]!=){puts("-1");return ;}

  int l,r,x,y; l=r=(n+)>>;

  if(a[n]!=b[l])

    {

      for(int i=;i<=n;i++)

    if(a[i]==b[l]){x=i;break;}

      cz(n-x);

    }

  bool fx=;

  for(l--,r++;l>=;l--,r++)

    {

      for(int i=;i<=n;i++)

    if(a[i]==b[l]){x=i;break;}

      for(int i=;i<=n;i++)

    if(a[i]==b[r]&&i!=x){y=i;break;}

      if(fx)swap(x,y); fx=!fx; char tp=a[y];

      cz(n-x); cz(n); cz(r-l-);

      for(int i=r-l+;i<=n;i++)

    if(a[i]==tp){y=i;break;}

      int tmp=n-y; cz(n-y+); cz(n-tmp-(r-l+));

    }

  if((n&)==&&!fx){ cz(n-); cz(); fx=!fx;}

  if(fx)cz(n);

  printf("%d\n",tot);

  for(int i=;i<=tot;i++)printf("%d ",p[i]);puts("");

  return ;

}

巴特西

CF 936C Lock Puzzle——构造

最新文章

热门文章