Featured image of post Educational Codeforces Round #190

Educational Codeforces Round #190

B

题目大意：你有一个由数字 1 到 4 组成的字符串 $s$。如果无法从字符串中选择某些元素并按原顺序写出一个 4 的倍数，则称该字符串是美丽的。空字符串被认为是美丽的。需要计算为了使字符串变得美丽，至少需要从字符串 $s$ 中删除多少个元素。

数据范围：$1 \le t \le 10^4$，$1 \le |s| \le 3 \cdot 10^5$，$\sum |s| \le 3 \cdot 10^5$。

思路：

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21

using i128 = __int128_t;
void solve() {
    string s;
    cin >> s;
    int n = sz(s);
    if (s == "21" || s == "23") {
        cout << 0 << endl;
        return;
    }
    vl pre(n), suf(n);
    pre[0] = (s[0] == '2');
    suf[n - 1] = (s[n - 1] == '1' || s[n - 1] == '3');
    rep(i, 1, n - 1) pre[i] = pre[i - 1] + (s[i] == '2');
    frep(i, n - 2, 0) suf[i] = suf[i + 1] + (s[i] == '1' || s[i] == '3');
    ll ans = LLONG_MIN;
    ans = max(ans, suf[0]);
    ans = max(ans, pre[n - 1]);
    rep(i, 0, n - 2) { ans = max(ans, pre[i] + suf[i + 1]); }
    cout << n - ans << endl;
    return;
}

C

题目大意：你有若干张数字卡片：数字 $1$ 有 $c_1$ 张，数字 $2$ 有 $c_2$ 张，……，数字 $n$ 有 $c_n$ 张。你必须从手中至少取出三张卡片，并将它们排成一个圆圈，使得以下条件成立： - 在任意连续的三张卡片中，至少有两张卡片上的数字相等。形式化地说，设选出的卡片按圆圈顺序为 $a_0, a_1, \dots, a_{k-1}$，那么必须满足： - 对于每个 $i$ 从 $0$ 到 $k-1$，在 $a_i, a_{(i+1) \bmod k}, a_{(i+2) \bmod k}$ 这三个数中，至少有两个相等。问最多可以排列多少张卡片？

数据范围：$1 \le t \le 10^4$，$1 \le n \le 2 \cdot 10^5$，$1 \le c_1 \le c_2 \le \dots \le c_n \le 10^9$，$\sum n \le 2 \cdot 10^5$。

思路：

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32

using i128 = __int128_t;
void solve() {
    ll n;
    cin >> n;
    vl a(n);
    rep(i, 0, n - 1) cin >> a[i];
    ll maxx = *max_element(all(a));
    ll tot = 0;
    rep(i, 0, n - 1) tot += a[i];
    if (tot <= 2) {
        cout << 0 << endl;
        return;
    }
    ll tot2 = 0;
    ll tot3 = 0;
    rep(i, 0, n - 1) {
        if (a[i] == 1)
            tot3++;
        else if (a[i] == 2 || a[i] == 3)
            tot2 += a[i];
        else {
            tot2 += a[i];
            ll tem = min(tot3, a[i] / 2 - 1);
            tot2 += tem;
            tot3 -= tem;
        }
    }
    ll tot4 = 0;
    rep(i, 0, n - 1) tot4 += (a[i] == 1);
    cout << tot2 + (tot4 == n - 1 && tot3 >= 1) << endl;
    return;
}

D

题目大意：Alice 和 Bob 决定看一部电视剧，该剧共有 $n$ 集，编号为 $1$ 到 $n$。这部电视剧将在接下来的 $n$ 天内在电视上播出。不幸的是，他们住在不同的城市，因此各集的播出时间表可能不同。第 $i$ 天，在 Alice 所在城市播出第 $a_i$ 集，在 Bob 所在城市播出第 $b_i$ 集。他们计划选择一段连续的日子 $[L, R]$（$1 \le L \le R \le n$）来观看这部剧。起初，他们两人都一集未看。

数据范围：$1 \le t \le 10^4$，$1 \le n \le 5 \cdot 10^5$，$1 \le a_i \le n$，$1 \le b_i \le n$，$\sum n \le 5 \cdot 10^5$。

思路：

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28

using i128 = __int128_t;
void solve() {
    ll n;
    cin >> n;
    vl a(n), b(n);
    rep(i, 0, n - 1) cin >> a[i];
    rep(i, 0, n - 1) cin >> b[i];
    vl dp(n + 1);
    ll ans = 0;
    vl sum(n + 1);
    rep(i, 0, n - 1) {
        if (i >= 1)
            sum[i] = sum[i - 1] + 1;
        else
            sum[i] = 1;
        dp[0] += 1;
        if (a[i] == b[i]) {
            dp[a[i]] += dp[a[i] - 1];
            dp[a[i] - 1] = 0;
        } else {
            sum[i] -= dp[a[i] - 1] + dp[b[i] - 1];
            dp[a[i] - 1] = 0, dp[b[i] - 1] = 0;
        }
    }
    rep(i, 0, n - 1) ans += sum[i];
    cout << ans << endl;
    return;
}

E

题目大意：假设你是一家新闻网站的所有者，想要研究某些选定的新闻如何影响你的用户。你有 $n$ 条新闻，每条新闻已经确定了两个参数：涉及政治的强度 $p_i$ 和涉及文化的强度 $c_i$。你还有 $m$ 个用户，你想研究他们对新闻的反应。对于每个用户，你已经确定了三个参数：政治新闻的容忍度 $tp_j$、文化新闻的容忍度 $tc_j$ 以及“影响力区间” $d_j$。

数据范围：$1 \le n \le 2 \cdot 10^5$，$0 \le p_i \le 10^6$，$0 \le c_i \le 10^6$，$1 \le m \le 4 \cdot 10^5$，$0 \le tp_j \le 10^6$，$0 \le tc_j \le 10^6$，$0 \le d_j \le 10^6$。

思路：

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70

using i128 = __int128_t;
void solve() {
    ll n;
    cin >> n;
    vector<pll> ma(n);
    rep(i, 0, n - 1) cin >> ma[i].first;
    rep(i, 0, n - 1) cin >> ma[i].second;
    ll m;
    cin >> m;
    auto ma2 = ma;
    sort(all(ma), [&](const pll& x, const pll& y) { return x.first < y.first; });
    sort(all(ma2), [&](const pll& x, const pll& y) { return x.second < y.second; });
    ll mixx = LLONG_MAX;
    int idx = -1;
    rep(i, 0, n - 1) {
        if (ma[i].first + ma[i].second < mixx) {
            mixx = ma[i].first + ma[i].second;
            idx = i;
        }
    }
    vl prep(n), sufp(n);
    vl prec(n), sufc(n);
    prep[0] = ma[0].second;
    rep(i, 1, n - 1) prep[i] = min(prep[i - 1], ma[i].second);
    sufp[n - 1] = ma[n - 1].second;
    frep(i, n - 2, 0) sufp[i] = min(sufp[i + 1], ma[i].second);
    prec[0] = ma2[0].first;
    rep(i, 1, n - 1) prec[i] = min(prec[i - 1], ma2[i].first);
    sufc[n - 1] = ma2[n - 1].first;
    frep(i, n - 2, 0) sufc[i] = min(sufc[i + 1], ma2[i].first);
    vl tp(m), tc(m), d(m);
    rep(i, 0, m - 1) cin >> tp[i];
    rep(i, 0, m - 1) cin >> tc[i];
    rep(i, 0, m - 1) cin >> d[i];
    rep(i, 0, m - 1) {
        ll ans = 0;
        if (ma[idx].first >= tp[i]) ans += min(ma[idx].first, tp[i] + d[i]);
        if (ma[idx].second >= tc[i]) ans += min(ma[idx].second, tc[i] + d[i]);
        int x1 = ranges::lower_bound(ma, make_pair(tp[i], -1)) - ma.begin() - 1;
        int x2 = ranges::lower_bound(ma, make_pair(tp[i] + d[i], -1)) - ma.begin();
        int y1 = lower_bound(all(ma2), tc[i], [&](const pll& x, ll tem) { return x.second < tem; }) - ma2.begin() - 1;
        int y2 = lower_bound(all(ma2), tc[i] + d[i], [&](const pll& x, ll tem) { return x.second < tem; }) - ma2.begin();
        if (x1 >= 0) {
            if (prep[x1] < tc[i])
                ans = min(ans, 0LL);
            else
                ans = min(ans, min(prep[x1], tc[i] + d[i]));
        }
        if (x2 < n) {
            if (sufp[x2] < tc[i])
                ans = min(ans, tp[i] + d[i]);
            else
                ans = min(ans, tp[i] + d[i] + min(sufp[x2], tc[i] + d[i]));
        }
        if (y1 >= 0) {
            if (prec[y1] < tp[i])
                ans = min(ans, 0LL);
            else
                ans = min(ans, min(prec[y1], tp[i] + d[i]));
        }
        if (y2 < n) {
            if (sufc[y2] < tp[i])
                ans = min(ans, tc[i] + d[i]);
            else
                ans = min(ans, tc[i] + d[i] + min(sufc[y2], tc[i] + d[i]));
        }
        cout << ans << endl;
    }
    return;
}