Educational Codeforces Round 168 (Rated for Div. 2) A-E 题解

Educational Codeforces Round 168 (Rated for Div. 2)

A - Strong Password

Solution

找到两个相同的往里面插入一个不同的即可

Code

#include <bits/stdc++.h>
using namespace std;

void solve() {
    string s; cin >> s;
    for (int i = 1; i < s.size(); i++) {
        if (s[i] == s[i - 1]) {
            string t = s;
            char c = s[i] == 'a' ? 'b' : 'a';
            t.insert(t.begin() + i, c);
            cout << t << '\n';
            return;
        }
    }
    char c = s[0] == 'a' ? 'b' : 'a';
    cout << c << s << '\n';
}

int main() {
    // freopen ("A.in", "r", stdin);
    ios::sync_with_stdio(false);
    int T; cin >> T;
    while (T--) solve();
    return 0;
}

B - Make Three Regions

Solution

找到这样一个区块

...
x.x

说明在第一行的中间可以放置一个

然后交换一二行再跑一次

Code

#include <bits/stdc++.h>
using namespace std;

int calc(vector<int> a, vector<int> b, int n) {
    int res = 0;
    for (int i = 2; i + 1 <= n; i++) {
        if (a[i] == 0 && a[i - 1] == 0 && a[i + 1] == 0)
        if (b[i] == 0 && b[i - 1] == 1 && b[i + 1] == 1)
            res += 1;
    }
    return res;
}

void solve() {
    int n; cin >> n;
    vector<int> a(n + 2, 0), b(n + 2, 0);
    a[0] = a[n + 1] = b[0] = b[n + 1] = 1;
    for (int i = 1; i <= n; i++) {
        char x; cin >> x;
        if (x == 'x') a[i] = 1;
        else a[i] = 0;
    }
    for (int i = 1; i <= n; i++) {
        char x; cin >> x;
        if (x == 'x') b[i] = 1;
        else b[i] = 0;
    }
    int ans = calc(a, b, n) + calc(b, a, n);
    cout << ans << '\n';
}

int main() {
    freopen ("B.in", "r", stdin);
    ios::sync_with_stdio(false);
    int T; cin >> T;
    while (T--) solve();
    return 0;
}

C - Even Positions

Solution

贪心得想，左括号和右括号肯定越近越好

所以对于一个 _ 如果里面的左括号较多，我们放置左括号，否则放置右括号，然后我们把右括号的位置塞入一个栈中

对于一个给定的右括号，如果前面的左括号个数不够了，就需要把栈内的一个右括号变成左括号来弥补左括号较少的情况

最后 $O (n)$ 计算结果即可

Code

#include <bits/stdc++.h>
using namespace std;

void solve() {
    int n; cin >> n;
    string s; cin >> s;
    int cnt = 0;
    stack<int> st;
    for (int i = 0; i < s.size(); i++) {
        if (s[i] == '(') cnt += 1;
        else if (s[i] == '_') {
            if (cnt > 0) {
                s[i] = ')'; cnt -= 1; st.push(i);
            }
            else {
                cnt += 1; s[i] = '(';
            }
        }
        else if (s[i] == ')') {
            cnt -= 1;
            if (cnt < 0) {
                int pos = st.top(); st.pop();
                s[pos] = '(';
                cnt += 2;
            }
        }
    }
    while (cnt < 0) {
        int pos = st.top(); st.pop();
        s[pos] = '(';
        cnt += 2;
    }
    while (!st.empty()) st.pop();
    long long ans = 0;
    for (int i = 0; i < s.size(); i++) {
        if (s[i] == '(') st.push(i);
        else {
            int pos = st.top(); st.pop();
            ans += i - pos;
        }
    }
    cout << ans << '\n';
}

int main() {
    freopen ("C.in", "r", stdin);
    ios::sync_with_stdio(false);
    int T; cin >> T;
    while (T--) solve();
    return 0;
}

D - Maximize the Root

Question

你将得到一棵有根树，共有 $n$ 个顶点。树中的顶点编号从 $1$ 到 $n$ ，根是顶点 $1$ 。在第 $i$ 个顶点上写有值 $a_{i}$ 。

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

您的任务是计算使用上述操作可能写在根上的最大可能值。

Solution

显然二分答案，考虑如何 check

对于一个 mid，根节点和 mid 的差为 $d$ ，那么就需要把子树都减少 $d$

对于一个节点，如果前面减少了 $p r e$ ，当前节点的值为 $a [u]$ ，那么 $u$ 的子树就需要减少 $p r e - a [u]$

这样递归处理，直到处理到叶子节点即可

Code

#include <bits/stdc++.h>
using namespace std;

void solve() {
    int n; cin >> n;
    string s; cin >> s;
    int cnt = 0;
    stack<int> st;
    for (int i = 0; i < s.size(); i++) {
        if (s[i] == '(') cnt += 1;
        else if (s[i] == '_') {
            if (cnt > 0) {
                s[i] = ')'; cnt -= 1; st.push(i);
            }
            else {
                cnt += 1; s[i] = '(';
            }
        }
        else if (s[i] == ')') {
            cnt -= 1;
            if (cnt < 0) {
                int pos = st.top(); st.pop();
                s[pos] = '(';
                cnt += 2;
            }
        }
    }
    while (cnt < 0) {
        int pos = st.top(); st.pop();
        s[pos] = '(';
        cnt += 2;
    }
    while (!st.empty()) st.pop();
    long long ans = 0;
    for (int i = 0; i < s.size(); i++) {
        if (s[i] == '(') st.push(i);
        else {
            int pos = st.top(); st.pop();
            ans += i - pos;
        }
    }
    cout << ans << '\n';
}

int main() {
    ios::sync_with_stdio(false);
    int T; cin >> T;
    while (T--) solve();
    return 0;
}

E - Level Up

Question

Monocarp 从等级 $1$ 开始游戏。他即将与 $n$ 只怪物进行战斗，按照从 $1$ 到 $n$ 的顺序。第 $i$ 只怪物的等级为 $a_{i}$

对于给定顺序中的每只怪物，Monocarp 的遭遇如下：

如果 Monocarp 的等级严格高于怪物的等级，则怪物会逃跑；
否则，Monocarp 会与怪物战斗。

在每次与怪物战斗 $k$ 次后，Monocarp 的等级会增加 $1$

给出 $q$ 个查询

$i x$ ：如果参数 $k$ 等于 $x$ ，Monocarp 是否会与第 $i$ 只怪物战斗（或者这只怪物会逃跑）

Solution

可以说，根号分治非常强大

首先，肯定要把询问离线下来，按照 $k$ 分组

对于一个 $k$ 如果 $k \leq B$ 那么直接暴力跑就好了

如果 $k > B$ ，那么总的等级数不会超过 $\frac{n}{B}$ ，我们可以开 $\frac{n}{B}$ 个前缀和 $p r e [j] [i]$ 表示表示前 $i$ 个数中大于 $j$ 的数的个数

那么对于每个询问，假设我们现在的位置是 $p o s$ ，等级为 $n o w$ ，那么我们下一个升级的位置就是第一个满足 $p r e [j] [i] >= p r e [n o w] [p o s] + k$ 的位置，显然可以二分得出，这部分的时间复杂度是个调和计数，大约为 $O (n \log^{2} n)$

取 $B = 1000$ 可以通过此题

#include <bits/stdc++.h>
using namespace std;

constexpr int M = 300, B = 1000;

void solve() {
    int n, q; cin >> n >> q;
    vector<int> a(n + 1);
    for (int i = 1; i <= n; i++) cin >> a[i];
    vector<vector<int>> pre(M, vector<int>(n + 1, 0)); // pre[j][i] 表示前 i 个数中大于 j 的数的个数
    for (int j = 0; j < M; j++)
        for (int i = 1; i <= n; i++) 
            pre[j][i] = pre[j][i - 1] + (a[i] > j); 
    
    vector<vector<pair<int, int>>> ask(n + 1);
    vector<int> ans(q + 1, 0);
    for (int i = 1; i <= q; i++) {
        int id, k; cin >> id >> k;
        ask[k].push_back({id, i});
    }

    for (int k = 1; k <= n; k++) {
        if (ask[k].empty()) continue;
        sort(ask[k].begin(), ask[k].end());

        if (k <= B) {
            int now = 1, cnt = 0, it = 0;
            for (int i = 1; i <= n; i++) {
                while (it < ask[k].size() && ask[k][it].first == i) {
                    ans[ask[k][it].second] = a[i] >= now;
                    ++it;
                }
                if (a[i] >= now && ++cnt == k) ++now, cnt = 0;
            }
        }
        else {
            int pos = 0, now = 0, it = 0;
            while (pos <= n) {
                pos = lower_bound(pre[now].begin(), pre[now].end(), pre[now][pos] + k) - pre[now].begin();
                // 跳到第一个大于 pre[now][pos] + k 的位置
                now += 1;
                while (it < ask[k].size() && ask[k][it].first <= pos) {
                    ans[ask[k][it].second] = a[ask[k][it].first] >= now;
                    ++it;
                }
            }
        }
    }

    for (int i = 1; i <= q; i++) cout << (ans[i] ? "YES" : "NO") << "\n";
}

int main() {
    ios::sync_with_stdio(0);
    int T; T = 1;
    while (T--) solve();
    return 0;
}