Educational Codeforces Round #182

B

题目大意：定义排列的代价为：将其变为递增序列时，需要排序的最短连续子段长度。给定一个由 $0$ 到 $n$ 的整数构成的数组 $p$，其中没有任何正整数（大于零）出现超过一次。需要用整数替换所有的 $0$，使得数组 $p$ 变成一个排列。需要计算，所能构造的排列的最大可能代价。

数据范围：$1 \le t \le 10^4$，$1 \le n \le 2 \cdot 10^5$，$0 \le p_i \le n$，$\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
void solve() {
    int n;
    cin >> n;
    vi a(n);
    rep(i, 0, n - 1) cin >> a[i];
    vector<bool> vis(n + 1, false);
    rep(i, 0, n - 1) {
        if (a[i] != 0) vis[a[i]] = true;
    }
    int re = n;
    rep(i, 0, n - 1) {
        if (a[i]) continue;
        while (re >= 1 && vis[re]) re--;
        a[i] = re;
        vis[re] = true;
    }
    int l = 0, r = n - 1;
    while (l <= n - 1 && a[l] == l + 1) l++;
    while (r >= 0 && a[r] == r + 1) r--;
    if (r <= l)
        cout << 0 << endl;
    else
        cout << r - l + 1 << endl;
    return;
}

C

题目大意：给定两个长度为 $n$ 的整数数组 $a$ 和 $b$。你可以选择任意一组下标的子集，并将这些位置上的元素进行交换（即对于每个下标 $i$，执行 swap($a_i$, $b_i$)）。如果在交换之后，两个数组都按非递减顺序排列，则该下标子集被认为是“好的子集”。需要计算“好子集”的数量。

数据范围：$1 \leq t \leq 500$，$1 \leq n \leq 100$，$1 \leq a_i \leq 1000$，$1 \leq b_i \leq 1000$。

思路：

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
const ll MOD = 998244353;
void solve() {
    int n;
    cin >> n;
    vi a(n);
    vi b(n);
    rep(i, 0, n - 1) cin >> a[i];
    rep(i, 0, n - 1) cin >> b[i];
    vvl dp(n, vl(2, 0));
    dp[0][0] = 1, dp[0][1] = 1;
    rep(i, 1, n - 1) {
        if (a[i] >= a[i - 1] && b[i] >= b[i - 1]) dp[i][0] = (dp[i][0] + dp[i - 1][0]) % MOD;
        if (a[i] >= b[i - 1] && b[i] >= a[i - 1]) dp[i][0] = (dp[i][0] + dp[i - 1][1]) % MOD;
        if (a[i] >= b[i - 1] && b[i] >= a[i - 1]) dp[i][1] = (dp[i][1] + dp[i - 1][0]) % MOD;
        if (a[i] >= a[i - 1] && b[i] >= b[i - 1]) dp[i][1] = (dp[i][1] + dp[i - 1][1]) % MOD;
    }
    cout << (dp[n - 1][0] + dp[n - 1][1]) % MOD << endl;
    return;
}

D

题目大意：假设你是一家商店的老板。为了新一季到来之前清理库存，你决定举行一次全面大促销。你的店里有 $n$ 种不同的商品，第 $i$ 种商品的售价为 $c_i$ 个金币。每种商品都贴有价格标签，标签上的价格就是 $c_i$。你决定举办一次这样的促销：“我们将所有商品的价格除以 $x$。” 形式上，这意味着你选择一个公约数 $x$，促销期间，第 $i$ 件商品的新价格将变为 $\left\lceil \frac{c_i}{x} \right\rceil$ 个金币（这里 $\left\lceil y \right\rceil$ 表示向上取整）。为了避免顾客混淆，需要为所有商品重新贴上印有新价格的标签，但打印新标签是有成本的。

数据范围：$1 \le t \le 10$，$1 \le n \le 2 \cdot 10^5$，$1 \le y \le 10^9$，$1 \le c_i \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
33
34
35
void solve() {
    ll n, y;
    cin >> n >> y;
    vl a(n);
    rep(i, 0, n - 1) cin >> a[i];
    ranges::sort(a);
    int maxx = *max_element(all(a));
    if (maxx == 1) {
        cout << n << endl;
        return;
    }
    vl pre(maxx + 1);
    rep(i, 0, n - 1) pre[a[i]]++;
    rep(i, 1, maxx) pre[i] += pre[i - 1];
    vl cnt(maxx + 1);
    rep(i, 0, n - 1) cnt[a[i]]++;
    ll ans = LLONG_MIN;
    rep(i, 2, maxx) {
        ll tem = 0;
        for (int j = i; j < maxx + i; j += i) {
            if (j >= maxx) {
                ll tem2 = pre[maxx] - pre[j - i];
                if (tem2 == 0) continue;
                tem += 1LL * (j / i) * tem2 - y * max(0LL, (tem2 - cnt[(j / i)]));
            } else {
                ll tem2 = pre[j] - pre[j - i];
                if (tem2 == 0) continue;
                tem += 1LL * (j / i) * tem2 - y * max(0LL, (tem2 - cnt[(j / i)]));
            }
        }
        ans = max(ans, tem);
    }
    cout << ans << endl;
    return;
}

E1

题目大意：这是该问题的简单版本。简单版与困难版的唯一区别在于 $t$ 和 $n$ 的约束条件。现有一排 $m$ 个塔，第 $i$ 个塔的高度为 $h_i$。如果你从左侧观察这排塔，你能看到所有严格高于前面所有塔的塔。同理，如果你从右侧观察这排塔，你能看到所有严格高于其右侧所有塔的塔。设 $L(h)$ 为从左侧能看到的塔的高度集合，$R(h)$ 为从右侧能看到的塔的高度集合，当这排塔的高度序列为 $h$ 时。对于上述例子，$L(h) = \{3, 5, 7\}$，$R(h) = \{4, 7\}$。现给定一个序列 $a_1, a_2, \dots, a_n$。

数据范围：$1 \leq t \leq 100$，$1 \leq n \leq 5000$，$1 \leq a_i \leq 10^9$，$\sum n \le 5000$。

思路：

 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
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
constexpr int MOD = 998244353;
int mul(int x, int y) { return x * 1LL * y % MOD; }
int qpow(int x, int y) {
    int z = 1;
    while (y > 0) {
        if (y & 1) z = mul(z, x);
        x = mul(x, x);
        y >>= 1;
    }
    return z;
}  // 求x**y%MOD

// 注意：当MOD为质数时， (x/y)%MOD=(x*(y**(MOD-2)))%MOD，即y在模MOD意义下的逆元为b^{-1} \equiv b^{p-2} mod p

void solve() {
    int n;
    cin >> n;
    vi a(n);
    rep(i, 0, n - 1) cin >> a[i];
    ll ans = 0;
    int tem = a[0];
    vi l;
    l.push_back(a[0]);
    rep(i, 1, n - 1) {
        if (a[i] > tem) {
            l.push_back(a[i]);
            tem = a[i];
        }
    }
    int lz = sz(l);
    tem = a[n - 1];
    vi r;
    r.push_back(a[n - 1]);
    frep(i, n - 2, 0) {
        if (a[i] > tem) {
            r.push_back(a[i]);
            tem = a[i];
        }
    }
    int rz = sz(r);
    int maxx = *max_element(all(a));
    vi te;
    rep(i, 0, n - 1) {
        if (a[i] == maxx) te.push_back(i);
    }
    int m = sz(te);
    vvl dp1(n + 1, vl(lz + 1));
    rep(i, 0, n) dp1[i][0] = 1;
    rep(i, 1, n) {
        rep(j, 1, lz) {
            dp1[i][j] = (dp1[i][j] + dp1[i - 1][j]) % MOD;
            if (a[i - 1] <= l[j - 1]) {
                dp1[i][j] = (dp1[i][j] + dp1[i - 1][j]) % MOD;
            }
            if (a[i - 1] == l[j - 1]) {
                dp1[i][j] = (dp1[i][j] + dp1[i - 1][j - 1]) % MOD;
            }
        }
    }
    ranges::reverse(a);
    vvl dp2(n + 1, vl(rz + 1));
    rep(i, 0, n) dp2[i][0] = 1;
    rep(i, 1, n) {
        rep(j, 1, rz) {
            dp2[i][j] = (dp2[i][j] + dp2[i - 1][j]) % MOD;
            if (a[i - 1] <= r[j - 1]) {
                dp2[i][j] = (dp2[i][j] + dp2[i - 1][j]) % MOD;
            }
            if (a[i - 1] == r[j - 1]) {
                dp2[i][j] = (dp2[i][j] + dp2[i - 1][j - 1]) % MOD;
            }
        }
    }
    rep(i, 0, m - 1) {
        rep(j, i, m - 1) {
            if (i == j) {
                int tem3 = te[i];
                ans += 1LL * dp1[tem3][lz - 1] * dp2[n - 1 - tem3][rz - 1] % MOD;
                ans %= MOD;
            } else {
                int le = te[i];
                int re = te[j];
                ll tem4 = dp1[le][lz - 1] * dp2[n - 1 - re][rz - 1] % MOD;
                ans += mul(qpow(2, re - le - 1), tem4);
                ans %= MOD;
            }
        }
    }
    cout << ans << endl;
    return;
}