Codeforces Round #501(Div.3) B(폭력)
3300 단어 codeforces
time limit per test
1 second
memory limit per test
256 megabytes
input
standard input
output
standard output
You are given two strings ss and tt. Both strings have length nn and consist of lowercase Latin letters. The characters in the strings are numbered from 11 to nn.
You can successively perform the following move any number of times (possibly, zero):
You can't apply a move to the string tt. The moves are applied to the string ss one after another.
Your task is to obtain the string tt from the string ss. Find any way to do it with at most 104104 such moves.
You do not have to minimize the number of moves, just find any sequence of moves of length 104104 or less to transform ss into tt.
Input
The first line of the input contains one integer nn (1≤n≤501≤n≤50) — the length of strings ss and tt.
The second line of the input contains the string ss consisting of nn lowercase Latin letters.
The third line of the input contains the string tt consisting of nn lowercase Latin letters.
Output
If it is impossible to obtain the string tt using moves, print "-1".
Otherwise in the first line print one integer kk — the number of moves to transform ss to tt. Note that kk must be an integer number between 00and 104104 inclusive.
In the second line print kk integers cjcj (1≤cj
If you do not need to apply any moves, print a single integer 00 in the first line and either leave the second line empty or do not print it at all.
Examples
input
Copy
6
abcdef
abdfec
output
Copy
4
3 5 4 5
input
Copy
4
abcd
accd
output
Copy
-1
Note
In the first example the string ss changes as follows: "abcdef" →→ "abdcef" →→ "abdcfe" →→ "abdfce" →→ "abdfec".
In the second example there is no way to transform the string ss into the string tt through any allowed moves.
각 자모가 두 열 안에 나타나는 횟수가 같은지 먼저 판단하고, 다르면 분명히 -1이다.
그러면 우리는 각str2[i]에 대응하는str1[i]의 위치를 직접 폭력적으로 찾아서 옮기면 된다.
직렬 길이가 최대 50회, 최악의 경우 50*50회이기 때문에 분명히 조건에 부합된다.
(Break을 적게 쓰면 hack을 당한다. 역시 요리의 인색하다)
#include
#define mp make_pair
#define fir first
#define se second
#define ll long long
#define pb push_back
using namespace std;
const int maxn=2e5+10;
const ll mod=1e9+7;
const int maxm=1e6+10;
const double eps=1e-7;
const int inf=0x3f3f3f3f;
const double pi = acos (-1.0);
int n;
string str1,str2;
int num[30],num1[30];
vector ans;
int main(){
cin>>n;
cin>>str1>>str2;
for (int i=0;ii;k--){
ans.pb(k);
swap(str1[k],str1[k-1]);
}
break;
}
}
}
cout<
이 내용에 흥미가 있습니까?
현재 기사가 여러분의 문제를 해결하지 못하는 경우 AI 엔진은 머신러닝 분석(스마트 모델이 방금 만들어져 부정확한 경우가 있을 수 있음)을 통해 가장 유사한 기사를 추천합니다:
Codeforces Round #715 Div. 2C The Sports Festival: 구간 DP전형구간 DP의 초전형. 이하, 0-indexed. 입력을 정렬하여 어디서나 시작하고 최적으로 좌우로 계속 유지하면 좋다는 것을 알 수 있습니다. {2000})$의 주문이 된다. 우선, 입력을 소트하여 n개의 요소를 $...
텍스트를 자유롭게 공유하거나 복사할 수 있습니다.하지만 이 문서의 URL은 참조 URL로 남겨 두십시오.
CC BY-SA 2.5, CC BY-SA 3.0 및 CC BY-SA 4.0에 따라 라이센스가 부여됩니다.