1997(EDU168div2)

A. Strong Password

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

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

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

求加入一个字母使得时间变得最长

void solve() {
    string s;cin >> s;
    int ok = 0;
    vector<char> ans;ans.push_back(s[0]);
    for (int i = 1;i < s.size();i++) {
        if (s[i] == s[i - 1] && !ok) {
            ok = 1;
            ans.push_back(s[i - 1] == 'z' ? 'a' : 'z');
            ans.push_back(s[i - 1]);
        } else {
            ans.push_back(s[i]);
        }
    }
    if (!ok) {
        cout << s << (s[s.size() - 1] == 'z' ? 'a' : 'z') << '\n';
    } else {
        for (auto x : ans)cout << x;cout << '\n';
    }
}

B. Make Three Regions

有一个由 $2$ 行和 $n$ 列组成的网格。网格中的每个单元格要么是空闲的，要么是受阻的。

方向有: 上下左右，能到达的都叫同一个连接区域。

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

在给出的网格中加入一个阻塞网格使得该网格恰好有 3 个连接区域。(给出的网格最多有一个连接区域)

按照样例给出的可以发现满足情况时就恰好 3 个区域.

x.x
...

变为

x.x
.x.

就恰好 3 个区域，其他情况则不满足要求

void solve() {
    int n;cin >> n;
    vector <array<char, 3>> g(n + 1);
    for (int i = 1;i <= n;i++) {
        cin >> g[i][1];
    }
    for (int i = 1;i <= n;i++) {
        cin >> g[i][2];
    }
    if (n < 3) {
        cout << "0\n";return;
    }
    int ans = 0;
    for (int i = 2;i < n;i++) {
        if (g[i - 1][1] == g[i + 1][1] && g[i - 1][1] == 'x' && g[i][1] == '.' && g[i][2] == '.' && g[i - 1][2] == '.' && g[i + 1][2] == '.') {
            ans++;
        }
        if (g[i - 1][2] == g[i + 1][2] && g[i - 1][2] == 'x' && g[i][2] == '.' && g[i][1] == '.' && g[i - 1][1] == '.' && g[i + 1][1] == '.') {
            ans++;
        }
    }
    cout << ans << '\n';
}

C. Even Positions

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

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

不幸的是，由于数据损坏，Monocarp 丢失了奇数位置上的所有字符 $s_{1}, s_{3}, \dots, s_{n - 1}$ 。只保留了偶数位置上的字符（ $s_{2}, s_{4}, \dots, s_{n}$ ）。例如，(())() 变成了 _(_)_)。

求代价最小的 RBS 串。

赛时总结的规律，但是不知道如何证明？

void solve() {
    int n;cin >> n;
    string s;cin >> s;
    cout << n / 2 + 2 * count(s.begin(), s.end(), '(') << '\n';
}

D. Maximize the Root

给你一棵有根的树，由 $n$ 个顶点组成。树中的顶点编号为 $1$ 至 $n$ ，根顶点为 $1$ 。数值 $a_{i}$ 写在第 $i$ 个顶点上。

您可以执行以下任意次数（可能为零）的操作：选择一个顶点 $v$ 该顶点至少有一个子顶点。对 $v$ 的子树（ $v$ 本身除外）中的所有顶点 $u$ ，将 $a_{v}$ 增加 $1$ ，并将 $a_{u}$ 减少 $1$ 。但是，每次操作后，所有顶点上的值都应该是非负值。

您的任务是通过上述操作计算出写入根的最大可能值。

Solution

树形 DP/二分

这个题目一眼二分，但是可惜自己的图论方面的代码能力太差，没写出来。(似乎有许多解法)

$O (n \log n)$

dfs 判断是否能够在 $u$ 的子树中得到至少 $x$ 的值

dfs 思路是：对于 1 的子树而言，需要满足大于等于 mid 的需求，若不满足，则子树的节点需要被增加一些才能满足需求，而这里增加了对于该子树节点的子树会提出更高的要求，即 $x$ 会增加。

#define int long long
void solve() {
    int n;cin >> n;
    vector<int> a(n + 1);
    for (int i = 1;i <= n;i++)cin >> a[i];
    vector<vector<int>> g(n + 1);
    for (int i = 2;i <= n;i++) {
        int x;cin >> x;
        g[x].push_back(i);
    }

    auto dfs = [&](auto self, int u, int x)->bool {
        if (x > 1e9)return 0;
        bool leaf = 1;
        if (u != 1) {
            x += max(0ll, x - a[u]);
        }
        for (auto v : g[u]) {
            leaf = 0;
            if (!self(self, v, x))return 0;
        }
        return (!leaf || x <= a[u]);
        };

    int l = 0, r = 1e10;
    while (l < r) {
        int mid = l + r >> 1;

        if (!dfs(dfs, 1, mid))r = mid;
        else l = mid + 1;
    }
    cout << a[1] + l - 1 << '\n';
}

$O (n)$

思路和我刚开始的想法接近，尽量让上下两层最小值接近,

若 $u$ 子树的最小值 $m i$ 比 $a_{u}$ 还小，则证明子树没什么能提交给 $a_{u}$ 的了，这个子树最多能凑出 $m i$ 的值，

若 $u$ 子树的最小值 $m i$ 比 $a_{u}$ 大，则可以按照题目要求将子树中的值整体提交给父亲一些，当接近的时候最优

搜索之后，根节点的子树则为下面的节点提交后的值，则答案就是 $a_{1}$ 加上子树的最小值。

#define int long long
void solve() {
    int n;cin >> n;
    vector<int> a(n + 1), val(n + 1);
    for (int i = 1;i <= n;i++)cin >> a[i];
    vector<vector<int>> g(n + 1);
    for (int i = 2;i <= n;i++) {
        int x;cin >> x;
        g[x].push_back(i);
    }
    int inf = 1e18;
    auto dfs = [&](auto self, int u)->void {
        val[u] = a[u];
        int mi = inf;
        for (auto v : g[u]) {
            self(self, v);mi = min(mi, val[v]);//mn是求的u节点子树的最小值
        }
        if (mi != inf) {// 不是叶子节点
            if (val[u] > mi) {
                val[u] = mi;
            } else {
                val[u] = val[u] + mi >> 1;
            }
        }
        };
    dfs(dfs, 1);
    int ans = inf;
    for (auto v : g[1]) {
        ans = min(ans, val[v]);
    }
    cout << ans + a[1] << '\n';
}