A16066 | Game with Reversing
时间限制1s
内存限制256MB
通过 / 提交0/0
题目描述
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.
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$ .
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
7 5 abcde abxde 5 hello olleo 2 ab cd 7 aaaaaaa abbbbba 1 q q 6 yoyoyo oyoyoy 8 abcdefgh hguedfbh
输出 #1
1 2 3 9 0 2 6
In the first test case, in her turn, Alice can replace the third symbol of the string $S$ with x. After that, both strings will become equal to "abxde" and the game will end after one move. Since Alice's goal is to finish the game in as few moves as possible, this move will be one of her optimal first moves, and the final answer will be $1$ .
In the second test case, in her turn, Alice can replace the fifth symbol of the string $T$ with h. After this move, $S =$ "hello", $T =$ "olleh". Then Bob makes his turn. In his turn, he must reverse one of the strings. If Bob chooses the string $S$ , then after his turn both strings will be equal to "olleh", and if he chooses the string $T$ , then after his turn both strings will be equal to "hello". Thus, after the presented first move of Alice, the game will definitely end in $2$ moves. It can be shown that there is no strategy for Alice to finish the game in less than $2$ moves, with both players playing optimally. The final answer is $2$ .
In the third test case, in her first move, Alice can replace the second symbol of the string $S$ with c. After this move, $S =$ "ac", $T =$ "cd". Then Bob makes his turn. If Bob reverses the string $S$ , then after his turn $S =$ "ca", $T =$ "cd". Then it is easy to see that in this case Alice can definitely finish the game on the $3$ -rd move, by replacing the second symbol of the string $T$ with a, after which both strings will become equal to "ca". If Bob reverses the string $T$ , then after his turn $S =$ "ac", $T =$ "dc". In this case, Alice can also definitely finish the game on the $3$ rd move, by replacing the first symbol of the string $S$ with d, after which both strings will become equal to "dc". Thus, Alice can definitely finish the game in $3$ moves regardless of Bob's moves. It can be shown that the game cannot end in less than $3$ moves, with both players playing optimally.
In the fifth test case, the strings $S$ and $T$ are equal, so the game will end without starting, in $0$ moves.
In the second test case, in her turn, Alice can replace the fifth symbol of the string $T$ with h. After this move, $S =$ "hello", $T =$ "olleh". Then Bob makes his turn. In his turn, he must reverse one of the strings. If Bob chooses the string $S$ , then after his turn both strings will be equal to "olleh", and if he chooses the string $T$ , then after his turn both strings will be equal to "hello". Thus, after the presented first move of Alice, the game will definitely end in $2$ moves. It can be shown that there is no strategy for Alice to finish the game in less than $2$ moves, with both players playing optimally. The final answer is $2$ .
In the third test case, in her first move, Alice can replace the second symbol of the string $S$ with c. After this move, $S =$ "ac", $T =$ "cd". Then Bob makes his turn. If Bob reverses the string $S$ , then after his turn $S =$ "ca", $T =$ "cd". Then it is easy to see that in this case Alice can definitely finish the game on the $3$ -rd move, by replacing the second symbol of the string $T$ with a, after which both strings will become equal to "ca". If Bob reverses the string $T$ , then after his turn $S =$ "ac", $T =$ "dc". In this case, Alice can also definitely finish the game on the $3$ rd move, by replacing the first symbol of the string $S$ with d, after which both strings will become equal to "dc". Thus, Alice can definitely finish the game in $3$ moves regardless of Bob's moves. It can be shown that the game cannot end in less than $3$ moves, with both players playing optimally.
In the fifth test case, the strings $S$ and $T$ are equal, so the game will end without starting, in $0$ moves.
C++ 编辑器
输入
输出
可保存默认模板；新题优先使用已保存模板。
当前快捷键仅展示，暂不支持修改。
- 撤销
Ctrl / ⌘ + Z - 重做
Ctrl / ⌘ + Y - 查找
Ctrl / ⌘ + F - 全选
Ctrl / ⌘ + A - 复制
Ctrl / ⌘ + C - 剪切
Ctrl / ⌘ + X - 粘贴
Ctrl / ⌘ + V - 自动排版
工具栏排版按钮 - 草稿保存
编辑时自动保存到本机
历史
提交记录
状态说明时间源码
AI
作答助手
你好，我是作答助手。可以问思路、复杂度、样例含义或代码报错原因；不会直接给出完整 AC 代码。
确定要清空代码吗？
提交通过
评测结果：Accepted