Educational Codeforces Round 69 (Rated for Div. 2) 解题报告
Nickel_Angel
2019-07-25 13:56:29
[题目总览请点击这里(๑¯∀¯๑)](http://codeforces.com/contest/1197)
**由于作者太弱了QAQ，部分题目参考了其他 OIer 的题解，并放上了原题解的链接**
***
### A [DIY Wooden Ladder](http://codeforces.com/contest/1197/problem/A)
#### Description
我们定义 $k$ 阶楼梯是由满足下述条件的 $k + 2$ 块木板组成的：
$1.$ 由两块长度至少为 $k + 1$ 的木板组成楼梯的底部。
$2.$ 剩下 $k$ 块木板长度至少为 $1$ 的木板组成阶梯。
现在有 $T$ 次询问，每次询问给你 $n$ 个木板和它们的长度，其中第 $i$ 个木板的长度为 $a_i$ 。
问用这些木板最多能组成几阶楼梯？
#### Solution
不难发现，组成楼梯的阶数是由木板中长度的次大值决定的。
故只需找出这个次大值，就知道最多能组成几阶楼梯。但注意有可能出现木板不够用的情况，故最终答案为 $min(max_{sec} - 1,n - 2)$ （其中 $max_{sec}$ 为次大值）。
#### Code
```cpp
#include <cstdio>
#include <cstring>
#include <cctype>
#include <iostream>
#include <algorithm>
using namespace std;
namespace IO
{
char ch;
bool f;
template<typename T>
inline void input(T &x)
{
x = 0;
ch = getchar();
f = false;
while (!isdigit(ch))
{
f |= (ch == '-');
ch = getchar();
}
while (isdigit(ch))
{
x = (x << 1) + (x << 3) + (ch ^ 48);
ch = getchar();
}
x = f ? -x : x;
}
}
using namespace IO;
namespace Primary
{
const int maxn = 1e5 + 10;
int T, n, max1, max2, x;
void main()
{
input(T);
while (T--)
{
max1 = 0, max2 = 0;
input(n);
for (int i = 1; i <= n; ++i)
{
input(x);
if (x > max1)
{
max2 = max1;
max1 = x;
}
else if (x > max2)//注意,本题找到是非严格的次大值,即次大值和最大值可以相等
max2 = x;
}
printf("%d\n", min(max2 - 1, n - 2));
}
}
}
int main()
{
Primary::main();
return 0;
}
```
***
### B [Pillars](http://codeforces.com/contest/1197/problem/B)
#### Description
给定 $n$ 个柱子，柱子的编号从 $1$ 到 $n$ 。
每个柱子上有一个盘子，其中编号为 $i$ 的柱子上的盘子的半径为 $a_i$，各个盘子的半径互不相同。
你每次可以将柱子 $i$ 上的盘子移动至柱子 $j$ 的条件是：
$1.$ $i,j$ 两个柱子必须相邻。
$2.$ 柱子 $i$ 上仅有一个盘子。
$3.$ 要么柱子 $j$ 上没有盘子，要么柱子 $j$ 上的盘子半径大于柱子 $i$ 上的盘子半径。
现在问能否把所有盘子均移动到同一柱子上。
#### Solution
考虑一种策略：我们每次将半径次大的盘子移动至半径最大的盘子上，由于半径次大的盘子移动后不会对其他盘子的移动造成影响，故我们可以视为将这个盘子删除，在找到当前的次大值，重复这个步骤即可。
注意到如果 $i,j$ 两个柱子不相邻，但它们之间的柱子上没有盘子，这和它们相邻是没有区别的。故可以用链表模拟这个过程即可。
```cpp
#include <cstdio>
#include <cstring>
#include <cctype>
#include <iostream>
#include <algorithm>
using namespace std;
namespace IO
{
char ch;
bool f;
template<typename T>
inline void input(T &x)
{
x = 0;
ch = getchar();
f = false;
while (!isdigit(ch))
{
f |= (ch == '-');
ch = getchar();
}
while (isdigit(ch))
{
x = (x << 1) + (x << 3) + (ch ^ 48);
ch = getchar();
}
x = f ? -x : x;
}
}
using namespace IO;
namespace Primary
{
const int maxn = 2e5 + 10;
int n, a[maxn], pre[maxn], next[maxn], pos[maxn];
inline void del(int x)
{
next[pre[x]] = next[x];
pre[next[x]] = pre[x];
}
void main()
{
scanf("%d", &n);
a[0] = -1;
for (int i = 1; i <= n; ++i)
{
scanf("%d", a + i);
pre[i] = i - 1;
next[i] = i + 1;
pos[a[i]] = i;
}
next[n] = 0;//防止越界
for (int i = n; i > 1; --i)
{
if (a[pre[pos[i]]] == i - 1 || a[next[pos[i]]] == i - 1)
del(pos[i]);//链表的删除操作
else
{
puts("NO");//若不能将当前的次大值移动至最大值,则一定无解
return;
}
}
puts("YES");
}
}
int main()
{
Primary::main();
return 0;
}
```
***
### C [Array Splitting](http://codeforces.com/contest/1197/problem/C)
#### Description
有一个长度为 $n$ 的单调不减的序列，其中第 $i$ 个元素为 $a_i$ 。
现在你需将该序列分成互不相交且非空的 $k$ 段，设第 $j$ 段中的最大值为 $max(j)$，最小值为 $min(j)$，则该段的代价为 $max(j) - min(j)$。现在你需要使分成这 $k$ 段的总代价尽可能小，问最小总代价。
#### Solution
由于这个序列单调不减，设一段 $j$ 的起始位置为 $start_j$，末尾位置为 $end_j$，则对于这段显然有 $max(j) = a_{end_j}$，$min(j) = a_{start_j}$，故这段的代价为 $a_{end_j} - a_{start_j}$ 。
则这 $k$ 段的总代价为：
$$\sum_{i = 1}^{k} a_{end_i} - a_{start_i}$$
据题意可知，第一段的起始位置一定是 $1$，最后一段的末尾位置一定是 $n$ 。故 $k$ 段的总代价可重写为：
$$a_n - a_1 + \sum_{i = 1}^{k - 1} a_{end_i} - a_{start_{i + 1}}$$
不难发现 $a_1,a_n$ 是确定的，只需考虑后面的和式的计算，而中间各段之间是相邻的，即对于相邻的两段 $i,i + 1$，均有 $end_i + 1 = start_{i + 1}$，故上式可以写成：
$$a_n - a_1 + \sum_{i = 1}^{k - 1} a_{end_i} - a_{end_i + 1} \text{(注意 $end_i + 1$ 的 $ +1$ 不在下标 $i$ 中)}$$
故我们只需考虑序列中 $a_i - a_{i + 1}$的前 $k - 1$ 小的值即可。不妨将其依次算出，并从小到大排序，取前 $k - 1$ 个即是最优解。
#### Code
```cpp
#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>
using namespace std;
namespace Primary
{
const int maxn = 3e5 + 10;
int n, k, a[maxn], d[maxn];
long long ans = 0;
void main()
{
scanf("%d%d", &n, &k);
for (int i = 1; i <= n; ++i)
{
scanf("%d", a + i);
d[i - 1] = a[i - 1] - a[i];
}
sort(d + 1, d + n + 1);
ans = a[n] - a[1];//记得统计a[n],a[1]的贡献
for (int i = 1; i < k; ++i)
ans += d[i];
printf("%I64d", ans);
}
}
int main()
{
Primary::main();
return 0;
}
```
***
### D [Yet Another Subarray Problem](http://codeforces.com/contest/1197/problem/D)
#### Description
给定一个长度为 $n$ 的序列 $a_i$ 和两个正整数 $m,k$。
你可以选择其中的一段子序列 $a_l,a_{l + 1},\cdots,a_{r - 1},a_r$。
这段子序列的代价为 $\sum_{i = l}^{r} a_i - k \lceil \frac{r - l + 1} {m} \rceil$（特殊的，对于一个空的序列，其代价为 $0$）。
对于给定序列，你需选出一个子序列，使其代价尽可能大，求最大代价。
#### Solution
（参考了[这篇题解](https://www.luogu.org/blog/Hakuryu/solution-cf1197d)（by Mital）的思路）
先应用一下前缀和，原式为：
$$sum[r] - sum[l - 1] - k\lceil \frac{r - l + 1} {m} \rceil$$
设 $x = l - 1$，故原式：
$$sum[r] - sum[x] - k\lceil \frac{r - x} {m} \rceil$$
而 $r = \lfloor \frac {r} {m} \rfloor m+ r\,mod\,m$，$x = \lfloor \frac x m \rfloor m+ x\,mod\,m$，故原式：
$$sum[r] - sum[x] - k\lceil \frac{\lfloor \frac {r} {m} \rfloor m+ r\,mod\,m - \lfloor \frac x m \rfloor m+ x\,mod\,m} {m} \rceil$$
即：
$$sum[r] - sum[x] - k \lceil \lfloor \frac r m \rfloor - \lfloor \frac x m \rfloor + \frac {r\,mod\,m + x\,mod\,m} {m} \rceil$$
考虑到 $\lfloor \frac{r} {m} \rfloor$，$\lfloor \frac {x} {m} \rfloor$ 为整数，故可直接提出，得到：
$$sum[r] - k \lfloor \frac {r} {m} \rfloor - (sum[x] - k \lfloor \frac {x} {m} \rfloor) - k \lceil \frac {r\,mod\,m - x\,mod\,m} {m} \rceil$$
设 $f(x) = sum[x] - k \lfloor \frac {x} {m} \rfloor$，则：
$$f(r) - f(x) - k \lceil \frac {r\,mod\,m - x\,mod\,m} {m} \rceil$$
将式子化至这里，我们发现可以考虑枚举子序列右端点 $r$，这样 $f(r)$ 和 $r\,mod\,m$ 就固定了，发现 $m$ 很小，故可以维护对于模 $m$ 剩余系中的 $i\,(i \in [0,m - 1])$ 维护最小的 $f(x)$，使 $x$ 与 $i$ 在模 $m$ 意义下同余，记作 $f_{ min}(i)$，每次枚举 $r$ 时遍历一遍 $f_{min}$ 更新答案，后用 $f(r)$ 更新 $f_{min}(r\,mod\,m)$ 即可。
```cpp
#include <cstdio>
#include <cstring>
#include <cmath>
#include <algorithm>
#include <iostream>
using namespace std;
namespace Primary
{
const long long inf = 1e14;
const int maxn = 3e5 + 10;
long long n, m, k, a[maxn];
long long sum[maxn], f[maxn], f_min[maxn];
void main()
{
scanf("%I64d%I64d%I64d", &n, &m, &k);
sum[0] = 0;
for (int i = 1; i <= n; ++i)
{
scanf("%I64d", a + i);
sum[i] = sum[i - 1] + a[i];
f[i] = sum[i] - k * ((long long)i / m);
}
for (int i = 1; i < m; ++i)
f_min[i] = inf;
f_min[0] = 0;
long long res, ans = 0, tmp;
for (int i = 1; i <= n; ++i)//枚举右端点
{
res = -inf;
for (int j = 0; j < m; ++j)
{
tmp = ceil(1.0 * ((i % m) - j) / m);
res = max(res, f[i] - f_min[j] - k * tmp);//更新当前答案
}
f_min[i % m] = min(f_min[i % m], f[i]);//用f[i]更新f_min[i % m]
ans = max(ans, res);
}
printf("%I64d", ans);
}
}
int main()
{
Primary::main();
return 0;
}
```
***
### E [Culture Code](http://codeforces.com/contest/1197/problem/E)
#### Description
有一些俄罗斯套娃，第 $i$ 个套娃的外部体积为 $out_i$，内部空心体积为 $in_i$，显然有 $in_i < out_i$。
你想将一些套娃放入包中，但包中没有太多的空闲空间，但幸运的是你可以将它们套起来带走。具体的，若 $out_i \leq in_j$ 你可以将套娃 $i$ 套在 $j$ 中。
现在你套了一些套娃，设这些套娃的编号为 $i_1,i_2,\cdots,i_k$，则剩余空间为：
$$in_{i_1} + (in_{i_2} - out_{i_1}) + \cdots + (in_{i_k} - out_{i_{k - 1}})$$
设所有方案中剩余空间最小的方案为 $m$，你需要求出剩余空间等于 $m$ 且套娃数量尽可能多的方案数是多少。由于答案可能很大，需对 $10^9 + 7$ 取模。
#### Solution
（参考了[这篇题解](https://www.luogu.org/blog/Ynoi/solution-cf1197e)（by 树链剖分）的思路）
本题为 $dp$ 题。
先将所有套娃按 $out_i$ 从小到大排序。定义 $f[i]$ 表示最外面使用第 $i$ 个套娃，剩余的最小空间，$g[i]$ 表示最小空间的方案数，则：
$$f[i] = min(f[j] + in[i] - out[j])\,(in[i] \geq out[j])$$
$$g[i] = \sum g[j]\,(in[i] \geq out[j],f[i] = f[j] + in[i] - out[j])$$
设 $in_{max}$ 为所有 $in$ 中的最大值，$out_{min}$ 为所有 $out$ 中的最小值。
由于要保证剩余空间最小，故 $\forall i,in[i] < out_{min}$ 都恒有 $g[i] = 1$ 。
设 $ans_f$ 为满足条件的最小剩余空间，由于要确保该套娃数量尽可能多，即装到装不下为止，故有：$ans_f = min(f[i])\,(out[i] \geq in_{max})$ 。
故答案为：$ans = \sum g[i]\,(out_i \geq in_{max}, f[i] = ans_f)$
时间复杂度为 $O(n^2)$，显然无法通过 $2 \times 10^5$ 的数据，故考虑优化：
由于 $f[i]$ 是由 $f[j] - out[j] + in[i]\,(in[i] \geq out[j])$ 转移过来的，且 $f[j] - out[j]$ 的值一定是 $j \in[1, i - 1]$ 中最小的，故可以先二分找到一个最大的 $j$ 使得 $in[i] \geq out[j]$，由于 $out_i$ 是从小到大排序过的，故对于 $k \in [1,j]$，均符合 $in[i] \geq out[k]$ 的要求，故我们可以维护一个 $f[i] - out[i]$ 前缀最小值 $pre_{min}[i]$ 以及最小值的方案数之和 $sum[i]$，就能在 $O(\log n)$ 的时间内完成一次转移。
由于需转移 $n$ 次，故总时间复杂度为 $O(n \log n)$ 。
#### Code
```cpp
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <iostream>
using namespace std;
namespace Primary
{
const int p = 1e9 + 7;
const int maxn = 2e5 + 10;
int n, in_max = 0, out_min = p, out[maxn], g[maxn], f[maxn];
int pre_min[maxn], sum[maxn], ans_f = p;
struct doll
{
int in, out;
bool operator < (const doll &rhs) const
{
if (out < rhs.out || out > rhs.out) return out < rhs.out;
return in < rhs.in;
}
}e[maxn];
void main()
{
scanf("%d", &n);
for (int i = 1; i <= n; ++i)
{
scanf("%d%d", &e[i].out, &e[i].in);
in_max = max(in_max, e[i].in);
out_min = min(out_min, e[i].out);
}
sort(e + 1, e + n + 1);
for (int i = 1; i <= n; ++i)
{
out[i] = e[i].out;//将排完序的 out 复制出来,便于用 upper_bound 二分
if (e[i].in < out_min)
g[i] = 1;
}
for (int i = 1, pos; i <= n; ++i)
{
pos = upper_bound(out + 1, out + n + 1, e[i].in) - out - 1;
f[i] = ((long long)pre_min[pos] + e[i].in) % p;
if (!g[i]) g[i] = sum[pos];
if (f[i] - e[i].out == pre_min[i - 1] && i != 1)
sum[i] = ((long long)sum[i - 1] + g[i]) % p;//若当前方案就为最优方案,直接求和
else if (f[i] - e[i].out < pre_min[i - 1] || i == 1)
sum[i] = g[i];//若当前方案更优,则记录当前方案的方案数
else sum[i] = sum[i - 1];//否则直接继承目前最优方案的方案数
pre_min[i] = min(pre_min[i - 1], f[i] - e[i].out);
if (e[i].out > in_max) ans_f = min(ans_f, f[i]);
}
int ans = 0;
for (int i = 1; i <= n; ++i)
{
if (e[i].out > in_max && f[i] == ans_f)
{
ans = ((long long)ans + g[i]) % p;
}
}
printf("%d", ans);
}
}
int main()
{
Primary::main();
return 0;
}
```
***
### F [Coloring Game](http://codeforces.com/contest/1197/problem/F)
~~由于涉及到了博弈论，线性代数的知识，作者太弱了，先咕咕咕~~