codeforces 501 B. Obtaining the String

题目链接:http://codeforces.com/contest/1015/problem/B

题意: 给出字符串s和字符串t,问一个将s变为t的策略。 可以做的变换为,交换s中相邻的字符串,该操作最多不能超过4000次,字符串长度最大为50.

思路:

首先可以确定,当两个字符串的组成相同时(也就是有同样的字符组成,只是位置可能有所不同)一定有解。

考虑最坏情况,每个字符都要交换到最远的地方,总的操作数<50*50<4000,因此一定有解。

判断组成是否相同可以用multiset

 1/* ***********************************************
 2Author :111qqz
 3mail: renkuanze@sensetime.com
 4Created Time :2018年10月03日 星期三 16时11分29秒
 5File Name :b.cpp
 6************************************************ */
 7#include <bits/stdc++.h>
 8#define ms(a,x) memset(a,x,sizeof(a))
 9typedef long long LL;
10#define pi pair < int ,int >
11#define MP make_pair
12using namespace std;
13const double eps = 1E-8;
14const int dx4[4]={1,0,0,-1};
15const int dy4[4]={0,-1,1,0};
16const int inf = 0x3f3f3f3f;
17int n;
18string s,t;
19multiset<char>A,B;
20int main()
21{
22        #ifndef  ONLINE_JUDGE 
23        freopen("./in.txt","r",stdin);
24  #endif
25  cin>>n;
26  cin>>s>>t;
27  for ( auto x : s) A.insert(x);
28  for (auto x: t) B.insert(x);
29  if (A!=B)
30  {
31    puts("-1");
32    return 0;
33  }
34  vector<int>ans;
35  //可以保证处理过的一定相等
36  for ( int i = 0 ; i < n ; i++)
37  {
38    if (s[i]==t[i]) continue;
39    string sub_str = s.substr(i,50);
40    // cout<<"sub_str:"<<sub_str<<endl;
41    int pos = sub_str.find(t[i])+i;
42    //  cout<<"pos:"<<pos<<endl;
43    for ( int j = pos; j  >= i+1 ; j-- )
44    {
45      ans.push_back(j);
46      swap(s[j-1],s[j]);
47      //  cout<<s<<endl;
48    }
49  }
50  cout<<ans.size()<<endl;
51  for ( auto x : ans) cout<<x<<" ";
1  #ifndef ONLINE_JUDGE  
2  fclose(stdin);
3  #endif
4    return 0;
5}