Educational Codeforces Round 150 (Div. 2)

传送门：Educational Codeforces Round 150 (Rated for Div. 2)

A. Game with Board

题意：

​ 给定初始序列为 $n$ 个 $1$ ，两人轮流行动，每次可以选择序列中若干个相同的数，剔除，并将他们的和加入序列。第一位无法行动的一方获胜。假设二人都绝对聪明，试问先手是否必胜。

题解：

​ 分类讨论一下：

• $2\leq n \leq 4$，有限轮模拟易得后手必胜。
• $n\geq5$ ，则先手取 $n-2$ 个 $1$， 后手只能取 $2$ 个 $1$ ， 之后序列变为 $\{n-2, 2\}$ ，故先手必胜。

code：

void solve() {
    int n;
    cin >> n;
    if (n >= 5) cout << "Alice" << endl;
    else cout << "Bob" << endl;
}

C. Ranom Numbers

题意：

​ A, B, C, D, E 分别代表 $1, 10, 100, 1000, 10000$ 。给定一由大写字母 ABCDE 组成的串，对于某一字符，若字符串后方有严格大于它的字符，则符号为负，否则为正。字符串权值为所有字母乘上符号的权值之和。

​ 现可以修改至多一字符，求可能的最大权值。

题解：

​ 据说 DP 和贪心均可，这里思路是 DP 。

​ 为了方便起见，先将字符串反转，规则也对应修正。

​ 然后设计状态： $F[i][j][0/1]$ 代表到第 $i$ 位，目前前缀最大值为 $j$ ，且已经/未修改的最大权值。 $i$ 这一位用滚动数组滚掉，然后枚举状态的转移即可。

​ 复杂度 $O(nMK)$ ，其中 $M=5, K=2$ 。

void solve() {
    int n;
    string s;
    cin >> s;
    n = s.length();
    reverse(s.begin(), s.end());
    int f[2][5][2];
    for (int i = 0; i < 5; i++) f[0][i][0] = f[0][i][1] = -inf;
    f[0][0][0] = 0;
    int p = 0, q = 1;
    for (auto c: s) {
        p ^= 1;
        q ^= 1;
        for (int i = 0; i < 5; i++) f[p][i][0] = f[p][i][1] = -inf;
        int x = c - 'A';
        for (int j = 0; j < 5; j++) {   //i-1位前缀最大
            for (int t = 0; t <= 1; t++) {   //
                for (int y = 0; y < 5; y++) {
                    int nt = t + (y != x);
                    int nj = max(y, j);
                    if (nt < 2) {
                        f[p][nj][nt] = max(f[p][nj][nt], f[q][j][t] + (y == nj ? digit[y] : -digit[y]));
                    }
                }
            }
        }
    }
    int ans = -inf;
    for (int i = 0; i < 5; i++) {
        ans = max(ans, f[p][i][0]);
        ans = max(ans, f[p][i][1]);
    }
    cout << ans << endl;
    return;
}

D. Pairs of Segments

题意：

​ 给定 $n$ 条线段，用区间表示 $[l,r]$ 。若 $n$ 为偶数，且可以将 $n$ 条线段分为 $\frac{n}{2}$ 对， 每一对线段相交， 不成一对的线段相交，则称其 beautiful 。现问至少删去多少线段，使得剩下的线段可以 beautiful 。

题解：

​ $n$ 比较小。一开始以为是 $dp$ 但怎么都消除不了后效性。实际解法是——直接暴力。

​ 首先考虑两对线段，共四条。不成对线段不相交的等价条件可以表示为： 成对线段取并集，所得两条线段不相交。

​ 因此可以直接求出 $C_n^2$ 对线段中，相交对的并集。然后找出尽量多的并线段，使其互不相交即可。互不相交可以天然保证每条线段至多用了一次。求不相交线段数目，这里用了动态开点线段树。

​ 复杂度 $O(n^2logn)$ 。

code：

const int N = 1e6 + 5;
int lc[N << 4], rc[N << 4], dat[N << 4], cnt;
 
inline void update(int &p, int l, int r, int k, int val) {
    if (!p) p = ++cnt;
    dat[p] = max(dat[p], val);
    if (l == r) return;
    int mid = l + r >> 1;
    if (k <= mid) update(lc[p], l, mid, k, val);
    else update(rc[p], mid + 1, r, k, val);
}
 
inline int query(int p, int l, int r, int u, int v) {
    if (!p || u > v) return 0;
    if (u <= l && r <= v) return dat[p];
    int mid = l + r >> 1, ans = 0;
    if (u <= mid) ans = max(ans, query(lc[p], l, mid, u, v));
    if (v > mid) ans = max(ans, query(rc[p], mid + 1, r, u, v));
    return ans;
}
 
void solve() {
#define mp(x, y) make_pair(x, y)
#define pb(x) push_back(x)
    int n;
    cin >> n;
    vector<pair<int, int> > Line(n);
    vector<pair<int, int> > Uline;
    for (int i = 0; i < n; i++) {
        cin >> Line[i].first >> Line[i].second;
    }
    auto check = [](const pair<int, int> a, const pair<int, int> b) {
        return max(a.first, b.first) <= min(a.second, b.second);
    };
    auto uni = [](const pair<int, int> a, const pair<int, int> b) {
        return mp(min(a.first, b.first), max(a.second, b.second));
    };
    for (int i = 0; i < n; i++) {
        for (int j = i + 1; j < n; j++) {
            if (!check(Line[i], Line[j])) continue;
            Uline.pb(uni(Line[i], Line[j]));
        }
    }
 
    auto cmp = [](const pair<int, int> a, const pair<int, int> b) {
        return a.second < b.second;
    };
    sort(Uline.begin(), Uline.end(), cmp);
    int ans = 0, rt = 0;
    const int inf = 1e9;
    for (auto line: Uline) {
        int rem = query(rt, -1, inf, -1, line.first - 1);
        update(rt, -1, inf, line.second, rem + 1);
        ans = max(ans, rem + 1);
    }
    cout << n - (ans << 1) << endl;
    return;
}
 

E. Fill the Matrix

题意：

​ 给定一 $n*n$ 的矩阵，其中第 $i$ 列的第 $1-a_i$ 行为黑格， $a_i-n$ 行为白格，仅白格可以填数。当一个格填数 $x$ 且其正右侧格填数 $x+1$ 时，贡献一 beauty 。填入 $1-m$ 共 $m$ 个数，求最大 beauty 值。

题解：

​ 看起来似乎比其他几道好想很多。上层所有线段都是下层线段的子集，因此从最底层线段开始枚举，填数，分裂即可。

​ 这里还是用的线段树。注意细节。

code：

#include <bits/stdc++.h>

using namespace std;

long long ans = 0;
const int N = 2e5 + 5;
int dat[N << 2], a[N];

void build(int p, int l, int r) {
    if (l == r) return (void) (dat[p] = a[l]);
    int mid = l + r >> 1;
    build(p << 1, l, mid);
    build(p << 1 | 1, mid + 1, r);
    dat[p] = min(dat[p << 1], dat[p << 1 | 1]);
}

int ask(int p, int l, int r, int u, int v) {
    if (u <= l && r <= v) return dat[p];
    int mid = l + r >> 1, ans = N;
    if (u <= mid) ans = min(ans, ask(p << 1, l, mid, u, v));
    if (v > mid) ans = min(ans, ask(p << 1 | 1, mid + 1, r, u, v));
    return ans;
}

void solve() {
#define mp(x, y) make_pair(x, y)
#define pb(x) push_back(x)
#define pii pair<int, int>

    int n;
    cin >> n;
    vector<vector<int> > pos(n + 1);
    for (int i = 1; i <= n; i++) {
        cin >> a[i];
        a[i] = n - a[i];
        pos[a[i]].pb(i);
    }
    //pos[i] 值为i的位置集合(补上界n+1)
    for (int i = 0; i <= n; i++) {
        pos[i].pb(n + 1);
        sort(pos[i].begin(), pos[i].end());
    }
    long long m;
    cin >> m;

    build(1, 1, n);
    struct node {
        int l, r, pre_min;

        node(int l, int r, int pre_min) : l(l), r(r), pre_min(pre_min) {}

        bool operator<(const node X) const {
            return this->r - this->l < X.r - X.l;
        }
    };
#define Ask(l, r) ask(1, 1, n, l, r)
    priority_queue<node> q;
    q.push(node(1, n, 0));
    long long ans = 0;
    while (!q.empty()) {
        auto p = q.top();
        q.pop();
        if (p.l == p.r) continue;
        int min_num = Ask(p.l, p.r);
        if (1ll * (min_num - p.pre_min) * (p.r - p.l + 1) > m) {
            ans += (m / (p.r - p.l + 1) * (p.r - p.l)) + max(0ll, m % (p.r - p.l + 1) - 1);
            break;
        } else {
            m -= 1ll * (min_num - p.pre_min) * (p.r - p.l + 1);
            ans += 1ll * (min_num - p.pre_min) * (p.r - p.l);
            int L = std::lower_bound(pos[min_num].begin(), pos[min_num].end(), p.l) - pos[min_num].begin();
            int R = std::upper_bound(pos[min_num].begin(), pos[min_num].end(), p.r) - pos[min_num].begin();
            int pre_l = p.l;
            for (int i = L; i < R; pre_l = pos[min_num][i] + 1, i++) {
                if (pre_l < pos[min_num][i]) q.push(node(pre_l, pos[min_num][i] - 1, min_num));
            }
            if (pre_l <= p.r) q.push(node(pre_l, p.r, min_num));
        }
    }
    cout << ans << endl;
}

int main() {
    int T;
    cin >> T;
    while (T--) solve();
}