AtCoder Beginner Contest 285【A - F】

鸽了一周的题解。

比赛链接：https://atcoder.jp/contests/abc285

A - Edge Checker 2

题解

利用完全二叉树结点序号的性质判断。

代码

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

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int a, b;
    cin >> a >> b;

    cout << (b / 2 == a ? "Yes" : "No") << "\n";

    return 0;
}

B - Longest Uncommon Prefix

题解

模拟。

代码

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

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int n;
    cin >> n;

    string s;
    cin >> s;

    for (int i = 1; i < n; i++) {
        int res = 0;
        for (int j = 0; j < n; j++) {
            if (j + i < n and s[j + i] != s[j]) {
                res += 1;
            } else {
                break;
            }
        }
        cout << res << "\n";
    }

    return 0;
}

C - abc285_brutmhyhiizp

题解

二十六进制数。

代码

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

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    string s;
    cin >> s;

    long long ans = 0;
    for (auto ch : s) {
        ans = ans * 26 + (ch - 'A' + 1);
    }
    cout << ans << "\n";

    return 0;
}

D - Change Usernames

题解

反向拓扑排序。

代码

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

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int n;
    cin >> n;

    map<string, vector<string>> G;
    map<string, int> deg;
    for (int i = 0; i < n; i++) {
        string u, v;
        cin >> u >> v;
        G[v].push_back(u);
        deg[u] += 1;
        deg[v] += 0;
    }

    queue<string> que;
    for (auto [str, x] : deg) {
        if (x == 0) {
            que.push(str);
        }
    }

    map<string, bool> vis;
    while (not que.empty()) {
        auto u = que.front();
        que.pop();

        vis[u] = true;

        for (auto v : G[u]) {
            if (--deg[v] == 0) {
                que.push(v);
            }
        }
    }

    bool ok = true;
    for (auto [str, x] : deg) {
        if (not vis[str]) {
            ok = false;
        }
    }
    cout << (ok ? "Yes" : "No") << "\n";

    return 0;
}

E - Work or Rest

题解

当两个假期相隔 $1$ 天时，之间的工作日有 $a_1$

当两个假期相隔 $2$ 天时，之间的工作日有 $a_1 + a_1$

当两个假期相隔 $3$ 天时，之间的工作日有 $a_1 + a_2 + a_1$

当两个假期相隔 $4$ 天时，之间的工作日有 $a_1 + a_2 + a_2 + a_1$

当两个假期相隔 $5$ 天时，之间的工作日有 $a_1 + a_2 + a_3 + a_2 + a_1$

…………

设 $dp[i][j]$ 表示已经确定前 $i$ 天，目前有 $j$ 天连续的工作日，则有状态转移方程：

• $dp[i + 1][j + 1] = max(dp[i + 1][j + 1], dp[i][j])$ ，含义为第 $i + 1$ 天为工作日

• $dp[i + 1][0] = max(dp[i + 1][0], dp[i][j] + pre[j])$ ，含义为第 $i + 1$ 天为假期

其中， $pre[i]$ 为连续 $i$ 天工作日的产能，递推公式为： $pre[i] = pre[i - 1] + a_{\lfloor \frac{(i + 1)}{2} \rfloor}$ 。

答案即 $max(dp[n][i] + pre[i])$ 。

代码

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

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int n;
    cin >> n;

    vector<int> a(n);
    for (int i = 0; i < n; i++) {
        cin >> a[i];
    }

    vector<long long> pre(n);
    for (int i = 1; i < n; i++) {
        pre[i] = pre[i - 1] + a[(i + 1) / 2 - 1];
    }

    vector dp(n + 1, vector<long long>(n, -1));
    dp[1][0] = 0;
    for (int i = 1; i < n; i++) {
        for (int j = 0; j < n; j++) {
            if (dp[i][j] == -1) {
                continue;
            }
            dp[i + 1][j + 1] = max(dp[i + 1][j + 1], dp[i][j]);
            dp[i + 1][0] = max(dp[i + 1][0], dp[i][j] + pre[j]);
        }
    }

    long long ans = LLONG_MIN;
    for (int i = 0; i < n; i++) {
        ans = max(ans, dp[n][i] + pre[i]);
    }
    cout << ans << "\n";

    return 0;
}

F - Substring of Sorted String

题解

符合条件的子串的含义：

• 字母排列为升序
• 除去首尾种类的字母，中间其余类型字母的个数与整个字符串的相同

第一个条件可以用树状数组 query(l, l + query(l, r) - 1) == query(l, r) 逐个字母判断；

第二个条件可以用 query(l, r) == cnt[i] 逐个判断。

代码

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

struct Fenwick_tree {
    vector<int> bit;

    Fenwick_tree(int n) : bit(n) {}

    void update(int pos, int val) { 
        for (int i = pos; i <= (int)bit.size(); i += i & (-i)) {
            bit[i - 1] += val;
        }
    }

    int query(int l, int r) {
        return query(r) - query(l - 1);
    }

    int query(int pos) {
        int res = 0;
        for (int i = pos; i >= 1; i -= i & (-i)) {
            res += bit[i - 1];
        }
        return res;
    }
};

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int n;
    cin >> n;

    string s;
    cin >> s;

    vector F(26, Fenwick_tree(n));
    vector<int> cnt(26);
    for (int i = 0; i < n; i++) {
        F[s[i] - 'a'].update(i + 1, 1);
        cnt[s[i] - 'a'] += 1;
    }

    int q;
    cin >> q;

    while (q--) {
        int op;
        cin >> op;

        if (op == 1) {
            int x;
            char c;
            cin >> x >> c;

            F[s[x - 1] - 'a'].update(x, -1);
            cnt[s[x - 1] - 'a'] -= 1;
            
            s[x - 1] = c;

            F[c - 'a'].update(x, 1);
            cnt[c - 'a'] += 1;
        } else {
            int l, r;
            cin >> l >> r;

            vector<int> ret(26);
            for (int i = 0; i < 26; i++) {
                ret[i] = F[i].query(l, r);
            }

            auto occurence_equal = [&](int l, int r) {
                int pl = 0, pr = 25;
                while (ret[pl] == 0) {
                    pl += 1;
                }
                while (ret[pr] == 0) {
                    pr -= 1;
                }

                for (int i = pl + 1; i <= pr - 1; i++) {
                    if (ret[i] != cnt[i]) {
                        return false;
                    }
                }
                return true;
            };

            auto is_increasing = [&](int l, int r) {
                for (int i = 0; i < 26; i++) {
                    if (F[i].query(l, l + ret[i] - 1) != ret[i]) {
                        return false;
                    }
                    l += ret[i];
                }
                return true;
            };

            cout << (occurence_equal(l, r) and is_increasing(l, r) ? "Yes" : "No") << "\n";
        }
    }

    return 0;
}