Educational Codeforces Round 69 题解

发表于 | 分类于 |
字数统计: 599 字

过于失败的一场比赛。。。

A

题目大意：长度为 $k$ 的梯子由两根 $k+1$ 长度的木板和 $k$ 个正长度的木板构成。给出所有可以用的木板，求出最长的梯子。

理解错了题意导致开门红。
实际上就是对所有木板长度排序，然后在第二长木板长 -1 和 木板数目 -2 中取 $\min$。

B

题目大意：有 $n$ 个盘子排成一列。盘子的半径各不相同，半径小的盘子可以放在半径大的盘子上，但可以移动的只有一个盘子（也就是说叠起来的盘子不能移动），且只能移动到相邻的位置。判定若干次移动后能不能移动成只有一堆盘子。

如果盘子构成的序列是单峰的就可以。证明显然。

C

题目大意：给定一个长度是 $n$ 的有序序列，需要将其切分成 $k$ 个连续的非空部分，要求最小化：每一部分中，最大值和最小值的差，的和。

一开始被样例“骗”了，以为是非常简单的题目，结果交了两发 WA。
因为是有序序列所以可以直接考察最大值和最小值之间的差，这个差可以看作是差分序列中的部分和，所以转而考虑差分序列。发现选取 $k$ 个部分等价于选取差分序列中的 $n-k$ 个数，代价就是这些数的和，那么就选取其中最小的 $n-k$ 个即可。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
int n, k, a[300005], d[300005];
void init(){
    n = read(), k = read();
    for (int i = 1; i <= n; ++i)
        a[i] = read();
    for (int i = 2; i <= n; ++i)
        d[i - 1] = a[i] - a[i - 1];
    sort(d + 1, d + n);
}
void solve(){
    ll ans = 0;
    for (int i = 1; i <= n - k; ++i)
        ans += 1ll * d[i];
    printf("%I64d\n", ans);
}

（后面的题目就不会做了。。。）

D

题目大意：给定数列 $a$，定义代价函数，对于空子列代价为 0，对于 $[l, r]$ 区间内的代价函数为

（$k$ 是一个常数）
最大化代价。

先按照 $m$ 为单位长度求出最大子段和，然后因为是向上取整，所以可以对于每一个右端点，都额外向右增加一段长在 $[1, m)$ 之间的序列，加上其的代价。