被b坑了
A题：Strong Password
题意
Monocarp的密码强度在于打字所耗的时间多少，如果当前字符与前一个字符相同，需要1s，否则需要2s，你现在可以在任意位置插入一个任意字符，请你帮忙构造一个最强密码
思路
贪心，最好的方式是将两个连续的给拆开，这样就能使得增加的最多，为3（2+2-1）
否则就直接在最前面加一个与第一个不同的，加2
代码
inline void solve() {string s; cin >> s;bool ok = false;for (int i = 1; i < s.size(); i ++ ) {if (s[i] == s[i - 1]) {s.insert(i, s[i] == 'a' ? "b" : "a");ok = true;break;}}if (!ok) s = (s[0] == 'a' ? 'b' : 'a') + s;cout << s << endl;return;
}B题：Make Three Regions
题意
给定一个2xn的网格，网格上有若干个阻塞单元格，你可以选定一个自由单元格，使其变成阻塞单元格，问有多少这样的自由单元格能够使得连通块数量变成3？
思路
题目限定了给定的连通块数量不超过1，
0的话就是0
那么我们就要找一个点，在它变成阻塞单元格的时候能够使得连通块数量增加2
这样有且仅有
x.x ...
... x.x
两种情况，只需判断即可
代码
inline void solve() {int n; cin >> n;string s[2];cin >> s[0] >> s[1];int ans = 0;for (int i = 1; i < n - 1; i ++ ) {for (int j = 0; j < 2; j ++ ) {if (s[j][i] == '.' && s[j][i - 1] == '.' && s[j][i + 1] == '.'&& s[j ^ 1][i] == '.' && s[j ^ 1][i - 1] == 'x' && s[j ^ 1][i + 1] == 'x') ans += 1;}}cout << ans << endl;return;
}C题：Even Positions
题意
一对（）的贡献为(和)之间的距离，已知偶数位上的)和(情况分布，请你进行构造使得各个（）的贡献之和最小
思路
从左往右看
对于当前位置，要增加的贡献为之前的(数量
那么我们只需要控制(的数量最小即可，最后一位肯定是），那我们只需要在（数量为0时加1即可
代码
inline void solve() {int n; cin >> n;string s; cin >> s;int ans = 0, add = 0;for (int i = 0; i < s.size(); i ++ ) {if (i % 2 == 0) {add ? add -= 1 : add += 1;}else {s[i] == '(' ? add += 1 : add -= 1;}ans += add;}cout << ans << endl;return;
}D题：Maximize the Root
题意
对于任意一个节点u，可以使得其值加1，其子树上的节点的值减一（本身除外）
在此过程中要确保任意一个节点的值不小于0
问根节点的值最大为多少？
思路
因为是使得整个子树减1，那么就要确保整个树平均大
何为平均大？
比如
5
｜
8
我们只能让其变成
6
｜
7
因为根节点增加1，是要使得整个树减去1的，那我们就要确保能够增加上这个值（除根节点外的所有节点都要大于等于这个值）
而对于
8
｜
5
要变成
5
｜
5
还是上面的那一个道理
上面的都是一个子节点的情况，我们再按多个进行分析即可
多个是按照短板效应的
5
｜
6，7，8，9，10000
这个5不会增加值
最后我们再分析根节点
因为我们从叶节点往上推的过程中，满足了根节点的所有子节点的值是其对应的子树最小的
那么只要将根节点加上其中的最小值即可
inline void solve() {int n; cin >> n;vector<int> a(n + 1);for (int i = 1; i <= n; i ++ ) cin >> a[i];vector<vector<int>> e(n + 1);for (int i = 2; i <= n; i ++ ) {int x; cin >> x;e[x].push_back(i);}function<void(int)> dfs = [&](int u) {for (int v : e[u]) dfs(v);if (e[u].empty()) return;if (u == 1) {int minv = 1e9 + 7;for (int v : e[1]) minv = min(minv, a[v]);a[1] += minv;}else {int minv = 1e9 + 7;for (int v : e[u]) minv = min(minv, a[v]);if (minv > a[u]) a[u] = (a[u] + minv) / 2;else a[u] = minv;}};dfs(1);cout << a[1] << endl;return;
}
