锐评

这把打的有点sb了，太着急了，A题吃了4发，最后才读清题40分钟过，B题看出结论了，二十多分钟就过了，C感觉有点贪心模拟的意思。没码出来，看了人家的代码感觉真简单，D听说也不难，也没有做到。

A.Strong Password

题意

Monocarp 在 Codeforces 上的当前密码是一个由小写拉丁字母组成的字符串 s 。Monocarp 认为他当前的密码太弱，所以他想在密码中插入一个小写拉丁字母，使密码更强。Monocarp 可以选择任何字母，并将其插入任何地方，甚至是第一个字符之前或最后一个字符之后。

Monocarp 认为密码的强度与他输入密码的时间成正比。输入密码所需的时间计算如下：

输入第一个字符的时间为 2 秒；
第一个字符以外的每个字符，如果与前一个字符相同，则输入时间为 1 秒，否则为 2 秒。

例如，输入密码 abacaba 所需的时间为 14 ；输入密码 a 所需的时间为 2 ；输入密码 aaabacc 所需的时间为 11 。

您必须帮助 Monocarp - 在他的密码中插入一个小写拉丁字母，使输入密码所需的时间尽可能短。

输入描述

第一行包含一个整数 t ( 1 \le t \le 1000 ) - 测试用例数。

每个测试用例包含一行字符串 s ( 1 \le |s| \le 10 )，由小写拉丁字母组成。

输出描述

为每个测试用例打印一行包含新密码的字符串，该字符串可以通过插入一个小写拉丁字母从 s 中获得。打印的字符串应尽可能长。如果有多个答案，则打印其中任何一个。

样例输入

4
a
aaa
abb
password

样例输出

wa
aada
abcb
pastsword

思路

只是在两个相同字母之间加一个不同字母，如果没有相同字母就随便加一个只要加的位置不再出现相同的即可，当时没读明白题错了三发。

#include<iostream>
#include<map>
#include<cstring>
using namespace std;
#define ll long long
const int N = 1e6 + 9;
const int MOD = 998244353;
int n, m;
void solve() {
	string s; 
    cin >> s;
    bool ok = true;
    for (int i = 0; i < s.size(); ++ i) {
        if (s[i] == s[i + 1]) {
            s.insert(i + 1, 1, s[i] == 'a' ? 'b' : 'a');
            ok = false;
            break;
        }
    }
    if (ok) {
        s = (s[0] == 'a' ? 'b' : 'a') + s;
    }
    cout << s << "\n";
}

signed main() {
	ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
	int _ = 1;
	cin >> _;
	while (_--) {
		solve();
	}
	return 0;
}

B.Make Three Regions

题意

有一个由 2 行和n 列组成的网格。网格中的每个单元格要么是空闲的，要么是受阻的。
如果至少有一个条件成立，则可以从自由单元格 x 到达自由单元格y：

x 和 y 共享一条边；
存在一个自由单元 z ，使得z 可以从x到达y，y可以从 z 到达。

连通区域是网格中自由单元格的集合，其中的所有单元格都可以相互连通，但是在该集合中添加任何其他自由单元格都会违反这一规则。

输入描述

第一行包含一个整数 t ( 1 \le t \le 10^4 ) - 测试用例数。

每个测试用例的第一行包含一个整数 n ( 1 \le n \le 2 \cdot 10^5 ) - 列数。

接下来两行中的 i/-th 行包含对网格第 i/-th 行的描述——字符串 s_i ，由 n 个字符组成。每个字符要么是 .(表示自由单元格)，要么是 x(表示阻塞单元格)。

请注意，以上文本已经进行了所需的替换，并且没有包含代码块。如果您有具体的测试用例数据，您可以提供给我，以便进行进一步的讨论。

输出描述

对于每个测试用例，打印一个整数 - 如果该单元格被阻塞，则连接区域数变为 3 的单元格数。

样例输入

4
8
.......x
.x.xx...
2
..
..
3
xxx
xxx
9
..x.x.x.x
x.......x

样例输出

思路

其实注意给出的联通快最多只有一个，因此我们要加一个阻塞块将一个变成三个，只有两个结构可以
. . . x . x
x. x . x .
只需要找这两个结构的数量即可

#include<iostream>
#include<map>
#include<algorithm>
#include<cstring>
using namespace std;
#define ll long long
const int N = 1e6 + 9;
const int MOD = 998244353;

int n, m;
char g[3][N];
void solve() {
	cin >> n;
    map<char, int> mp;
	for (int i = 1; i <= 2; ++ i) {
        for (int j = 1; j <= n; ++ j) {
            cin >> g[i][j];    
            mp[g[i][j]] ++;
        }
    }
    if (!mp['.']) {
        cout << "0\n";
        return;
    }
    int ans = 0;
    for (int i = 2; i < n; ++ i) {
        if (g[1][i - 1] == '.' && g[1][i] == '.' && g[1][i + 1] == '.') {

            if (g[2][i - 1] == 'x' && g[2][i] == '.' && g[2][i + 1] == 'x') {
                ans ++;
            }
        }
        if (g[1][i - 1] == 'x' && g[1][i] == '.' && g[1][i + 1] == 'x') {
            if (g[2][i - 1] == '.' && g[2][i] == '.' && g[2][i + 1] == '.') {
                ans ++;
            }
        }
    }
    cout << ans << "\n";
}

signed main() {
	ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
	int _ = 1;
	cin >> _;
	while (_--) {
		solve();
	}
	return 0;
}

C.Even Positions

题意

莫诺卡普有一个长度为 n (n 为偶数)的正则括号序列 s。他甚至想出了自己的计算方法。

他知道，在正则括号序列(RBS)中，每个开头括号都与相应的结尾括号配对。因此，他决定将 RBS 的成本计算为对应括号对之间的距离之和。

例如，我们来看看 RBS (())() 。它有三对括号：

(____)__: 位于 1 和 4 位置的括号之间的距离是 4 - 1 = 3 ；
__()____: 距离是 3 - 2 = 1 ；
______(): 距离是 6 - 5 = 1 。

所以 (())() 的成本是 3 + 1 + 1 = 5 。不幸的是，由于数据损坏，Monocarp 丢失了奇数位置上的所有字符 s_1, s_3, \dots, s_{n-1} 。只保留了偶数位置上的字符(s_2, s_4, \dots, s_n)。例如，(())() 变成了 _(_)_)。单卡普想通过在奇数位置上放置括号来恢复他的 RBS。但由于恢复后的 RBS 可能不是唯一的，所以他想选择一个代价**最小的。这对 Monocarp 来说太难了，你能帮帮他吗？

提醒：正则括号序列是一个仅由括号组成的字符串，当这个序列插入 1-s 和 +-s 时，会给出一个有效的数学表达式。例如，()、(()())或(()()()())是正则表达式，而(()、()()或()()())则不是。

以上文本已经按照您的要求进行了替换，并且没有包含代码块。如果您有更具体的问题或需要进一步的帮助，请告诉我。

输入描述

第一行包含一个整数 t ( 1 \le t \le 5000 ) - 测试用例数。接下来是 t 个案例。

每个测试用例的第一行都包含一个整数 n ( 2 \le n \le 2 \cdot 10^5 ； n 为偶数) ——字符串 s 的长度。

每个测试用例的第二行包含长度为 n 的字符串 s ，其中奇数位置上的所有字符都是"_"，偶数位置上的所有字符都是"("或")"。

其他限制条件

s 可以还原为至少一个正则括号序列；
所有测试用例中 n 的总和不超过 2 \cdot 10^5 。

以上文本已经按照您的要求进行了替换，并且没有包含代码块。如果您有具体的测试用例数据或者其他相关问题，您可以提供给我，以便进行进一步的讨论。

输出描述

对于每个测试用例，打印一个整数 - 通过用括号替换'_'-s 从 s 得到的正则括号序列的最小成本。

样例输入

4
6
_(_)_)
2
_)
8
_)_)_)_)
8
_(_)_(_)

样例输出

思路

这道题其实蛮简单的，只需要将左括号的下标减掉，右括号的下标加上即可，至于每个地方该加什么，我们要让值最小，说明右括号应提前放，所以从左到右有限放右括号。只有左边没有左括号的时候才放左括号。

#include<iostream>
#include<algorithm>
#include<cstring>
#include<map>
using namespace std;
#define ll long long
const int N = 1e6 + 9;
int n, m;
void solve() {
	cin >> n;
    string s; cin >> s;
    s = '?' + s;
    int c0 = 0;
    int ans = 0;
    for (int i = 1; i <= n; ++ i) {
        if (s[i] == '_') {
            if (c0 == 0) c0 ++,ans -= i;
            else c0 --,ans += i;
        }else if (s[i] == '(') c0 ++,ans -= i;
        else c0 -- ,ans += i;
    }
    cout << ans << "\n";
	
}

signed main() {
	ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
	int _ = 1;
	cin >> _;
	while (_--) {
		solve();
	}
	return 0;
}