CodeForces 1006D
10302 단어 VJ 트레이닝 문제Codeforces
You are given two strings a and b consisting of lowercase English letters, both of length n. The characters of both strings have indices from 1 to n, inclusive.
You are allowed to do the following changes:
Choose any index i (1≤i≤n) and swap characters ai and bi; Choose any index i (1≤i≤n) and swap characters ai and an−i+1; Choose any index i (1≤i≤n) and swap characters bi and bn−i+1. Note that if n is odd, you are formally allowed to swap a⌈n2⌉ with a⌈n2⌉ (and the same with the string b) but this move is useless. Also you can swap two equal characters but this operation is useless as well.
You have to make these strings equal by applying any number of changes described above, in any order. But it is obvious that it may be impossible to make two strings equal by these swaps.
In one preprocess move you can replace a character in a with another character. In other words, in a single preprocess move you can choose any index i (1≤i≤n), any character c and set ai:=c.
Your task is to find the minimum number of preprocess moves to apply in such a way that after them you can make strings a and b equal by applying some number of changes described in the list above.
Note that the number of changes you make after the preprocess moves does not matter. Also note that you cannot apply preprocess moves to the string b or make any preprocess moves after the first change is made.
Input
The first line of the input contains one integer n (1≤n≤105) — the length of strings a and b.
The second line contains the string a consisting of exactly n lowercase English letters.
The third line contains the string b consisting of exactly n lowercase English letters.
Output
Print a single integer — the minimum number of preprocess moves to apply before changes, so that it is possible to make the string a equal to string b with a sequence of changes from the list above.
Examples
Input 7 abacaba bacabaa Output 4
Input 5 zcabd dbacz Output 0
Note
In the first example preprocess moves are as follows: a1:=‘b’, a3:=‘c’, a4:=‘a’ and a5:=‘b’. Afterwards, a=“bbcabba”. Then we can obtain equal strings by the following sequence of changes: swap(a2,b2) and swap(a2,a6). There is no way to use fewer than 4 preprocess moves before a sequence of changes to make string equal, so the answer in this example is 4.
In the second example no preprocess moves are required. We can use the following sequence of changes to make a and b equal: swap(b1,b5), swap(a2,a4).
사고의 방향
제목의 뜻은 두 개의 문자열이 있는데 우리는 세 가지 조작을 할 수 있다. 첫 번째는 a[i]와 b[i]의 단일 문자를 교차시키는 것이다.두 번째, a[i]와 a[n-i-1]의 단일 문자를 교환한다.세 번째, b[i]와 b[n-i-1]의 단일 문자를 교환한다.그러나 제목의 요구는 우리가 먼저 a의 문자를 미리 처리하고 위의 세 가지 조작을 하면 문자열 a==b로 하여금 미리 처리하는 횟수를 구할 수 있다는 것이다.상술한 후 두 가지 조작은 모두 양쪽에서 가운데로 아치형이기 때문에 하나의 규칙을 찾을 수 있다. a[i], a[n-i-1], b[i], b[n-i-1] 이 네 글자를 비교할 수 있다. 왜냐하면 a만 바꿀 수 있기 때문에 b[i]=b[n-i-1]를 고려하지 않는 전제에서 네 글자는 n이 같은 (교차할 수 없다. 예를 들어 a[i]=b[n-i-1]와 a[n-i-1]=b[i])가 있다.같은 그룹 수가 있으면 2~n회 예처리를 줄일 수 있다(전체 처리 그룹은 2회 처리해야 한다).
코드
#include
using namespace std;
#define INF 0x3f3f3f3f
#define maxn 100000+5
typedef long long ll;
char a[maxn];
char b[maxn];
int main() {
int n;
cin >> n;
cin >> a >> b;
ll total = 0;
for (int i = 0; i < n / 2; i++) {
int l = i;
int r = n - i - 1;
if (a[l] == b[l] && a[r] == b[r] || a[l] == b[r] && a[r] == b[l] || a[l] == a[r] && b[l] == b[r]) {
continue;
}
else if (a[l] == b[l] || a[l] == b[r] || a[r] == b[l] || a[r] == b[r] || b[l] == b[r]) {
total ++;
}
else {
total += 2;
}
}
if (n % 2 == 1 && a[n / 2] != b[n / 2]) {
total ++;
}
cout << total << endl;
}
제목 출처
CodeForces 1006D Two Strings Swaps
이 내용에 흥미가 있습니까?
현재 기사가 여러분의 문제를 해결하지 못하는 경우 AI 엔진은 머신러닝 분석(스마트 모델이 방금 만들어져 부정확한 경우가 있을 수 있음)을 통해 가장 유사한 기사를 추천합니다:
[CF 817F] MEX Queries(라인 트리)길이 1018 1018의 0101 서열을 유지하고 도자기 구간에 값을 부여하고 구간에서 반전을 취하며 첫 번째 0의 위치를 조회해야 한다. 이산화 후 라인 트리로 역표기, 부치표기를 유지하면 됩니다....
텍스트를 자유롭게 공유하거나 복사할 수 있습니다.하지만 이 문서의 URL은 참조 URL로 남겨 두십시오.
CC BY-SA 2.5, CC BY-SA 3.0 및 CC BY-SA 4.0에 따라 라이센스가 부여됩니다.