Note: This article is available in Chinese only. 本文暂无英文版本。
View original
题目链接: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<<" ";
52
53 #ifndef ONLINE_JUDGE
54 fclose(stdin);
55 #endif
56 return 0;
57}