Educational Codeforces Round 150 (Rated for Div. 2) A-E

比赛链接

A

代码

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

bool solve() {
    int n;
    cin >> n;
    if (n <= 4) cout << "Bob" << '\n';
    else cout << "Alice" << '\n';
    return true;
}

int main() {
    std::ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
    int t = 1;
    cin >> t;
    while (t--) {
        if (!solve()) cout << -1 << '\n';
    }
    return 0;
}

B

代码

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

bool solve() {
    int q;
    cin >> q;

    bool ok = 1;
    int limit = -1;
    int pre = 0;
    while (q--) {
        int x;
        cin >> x;
        if (limit < 0) limit = x;
        if (ok) {
            if (pre <= x || x <= limit) {
                if (pre > x) ok = 0;
                cout << 1;
                pre = x;
            }
            else cout << 0;
        }
        else {
            if (pre <= x && x <= limit) cout << 1, pre = x;
            else cout << 0;
        }
    }
    cout << '\n';
    return true;
}

int main() {
    std::ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
    int t = 1;
    cin >> t;
    while (t--) {
        if (!solve()) cout << -1 << '\n';
    }
    return 0;
}

C

题目

给定一个字符串 \(s\) ，仅含有 A-E \(5\) 个大写字母，其中字母代表一个值 |A| = 1, ..., |E| = 10000 。

一个字符串的值为 \(\displaystyle \sum_{i=1}^n (-1)^{\left[s_i < \max\limits_{i+1 \leq j \leq n}(s_i)\right]} \cdot |s_i|\) 。

题解

方法一

知识点：线性dp，枚举。

考虑枚举每个位置作为修改的位置。

对于位置 \(i\) 的修改，只会影响到 \([1,i-1]\) 之间字符值的符号，而 \([i+1,n]\) 是不会被影响的。因此，我们需要预先知道， \([1,i-1]\) 在 \([i,n]\) 最大值确定时的值。

设 \(f_{i,j}\) 表示 \([1,i-1]\) 在 \([i,n]\) 的最大字符为 \(j\) 时的值。转移方程为：

\[f_{i,j} = f_{i-1,\max(s_{i-1},j)} + (-1)^{[s_{i-1}<j]} \cdot |s_{i-1}|\]