Game with Reversing

题面翻译

小 L 和小 S 在玩游戏。他们有两个长度均为 $n(1 \le n \le 10^5)$ 的字符串 $S, T$，小 L 和小 S 轮流操作，小 L 先手。

小 L 的回合，他可以选择 $1 \to n$ 中的一个整数 $i$，再选择串 $S$ 或 $T$，把其中的第 $i$ 个字符改成任意一个字符 $c$。

小 S 的回合，她可以选择 $S$ 或 $T$，并将它进行翻转。

如果两个串 $S, T$ 经过若干次操作后相等，则游戏立即结束。小 L 希望总操作次数最小，小 S 希望总操作次数最大。两人都采取最优策略，问最终操作次数。

题目描述

Alice and Bob are playing a game. They have two strings $ S $ and $ T $ of the same length $ n $ consisting of lowercase latin letters. Players take turns alternately, with Alice going first.

On her turn, Alice chooses an integer $ i $ from $ 1 $ to $ n $ , one of the strings $ S $ or $ T $ , and any lowercase latin letter $ c $ , and replaces the $ i $ -th symbol in the chosen string with the character $ c $ .

On his turn, Bob chooses one of the strings $ S $ or $ T $ , and reverses it. More formally, Bob makes the replacement $ S := \operatorname{rev}(S) $ or $ T := \operatorname{rev}(T) $ , where $ \operatorname{rev}(P) = P_n P_{n-1} \ldots P_1 $ .

The game lasts until the strings $ S $ and $ T $ are equal. As soon as the strings become equal, the game ends instantly.

Define the duration of the game as the total number of moves made by both players during the game. For example, if Alice made $ 2 $ moves in total, and Bob made $ 1 $ move, then the duration of this game is $ 3 $ .

Alice's goal is to minimize the duration of the game, and Bob's goal is to maximize the duration of the game.

What will be the duration of the game, if both players play optimally? It can be shown that the game will end in a finite number of turns.

输入格式

Each test contains multiple test cases. The first line contains the number of test cases $ t $ ( $ 1 \le t \le 10^4 $ ). The description of the test cases follows.

The first line of each test case contains a single integer $ n $ ( $ 1 \le n \le 10^5 $ ) — the length of the strings $ S $ and $ T $ .

The second line of each test case contains a string $ S $ of length $ n $ consisting of lowercase latin letters.

The third line of each test case contains a string $ T $ of length $ n $ consisting of lowercase latin letters.

It is guaranteed that the sum of $ n $ over all test cases does not exceed $ 10^5 $ .

输出格式

For each test case, output a single number on a separate line — the duration of the described game, if both players play optimally.

样例 #1

样例输入 #1

7
5
abcde
abxde
5
hello
olleo
2
ab
cd
7
aaaaaaa
abbbbba
1
q
q
6
yoyoyo
oyoyoy
8
abcdefgh
hguedfbh

样例输出 #1

分析

我们只需要盯着一个字符串看, 然后把另一个字符串改成和这个字符串或者和这个字符串的翻转一样就好了, 不要想太复杂

简单说明一下正确性: B的翻转对于答案是没有影响的, 比如B翻转了字符串S两次, 相当于没翻转, 或者B翻转了一次S一次T, 也相当于没翻转

我们判断一下两种情况有几个不同的地方要改即可, 分奇偶讨论, 要注意的是如果 dif1 = 0, 那么直接结束, dif1 = 1, A改一次也结束. 但是 dif2 = 0, 先轮到A再到B, 是两次, dif2 = 1, 还是两次. 其他情况就很简单了

注意: 要理解好两次翻转相当于没有翻转, 不管是作用在一个字符串还是两个, 这让我们想到B是没影响的, 才可以只统计不同的字符串个数

代码

#include <iostream>
#include <algorithm>
using namespace std;
int main()
{
	ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
	
	int t; cin >> t;
	while(t--)
	{
		int n; cin >> n;
		string a, b; cin >> a >> b;
		
		int dif1 = 0, dif2 = 0, ans = 1e9;
		for(int i = 0; i < n; i++)
		{
			if(a[i] != b[i]) dif1++;
			if(a[i] != b[n - 1 - i]) dif2++;
		}
		if(dif1 <= 1)
		{
			cout << dif1 << endl;
			continue;
		}
		if(dif2 <= 1)
		{
			cout << 2 << endl;
			continue;
		}
		if(dif1 % 2) ans = min(2 * dif1 - 1, ans);
		else if(dif1 % 2 == 0) ans = min(2 * dif1, ans);
		if(dif2 % 2) ans = min(ans, 2 * dif2);
		else if(dif2 % 2 == 0) ans = min(ans, dif2 * 2 - 1);
		cout << ans << endl;
	}
}

JZTXT

CF1834C