目录
Contest Info
| Solved | A | B | C | D | E | F |
|---|---|---|---|---|---|---|
| 5/6 | O | O | O | O | O | Ø |
- O 在比赛中通过
- Ø 赛后通过
- ! 尝试了但是失败了
- - 没有尝试
Solutions
A. DIY Wooden Ladder
签到题。
#include <bits/stdc++.h>
using namespace std;
#define N 100010
int n, a[N];
int main() {
int T; scanf("%d", &T);
while (T--) {
scanf("%d", &n);
for (int i = 1; i <= n; ++i) scanf("%d", a + i);
sort(a + 1, a + 1 + n);
int res = 0;
for (int i = 2; i < n; ++i) {
res = max(res, min(a[i] - 1, i - 1));
}
printf("%d\n", res);
}
return 0;
}B. Pillars
题意：
有\(n\)根柱子，每根柱子上有一个磁盘，一个磁盘能从第\(i\)根柱子移动到第\(j\)根柱子的前提是：
- 第\(j\)根柱子上没有磁盘
- 或者第\(i\)根柱子上的磁盘半径颜色小于第\(j\)根柱子的磁盘
现在给出每根柱子上磁盘的半径，问能够存在一种方案使得将所有的磁盘都移动的一根柱子上
思路：
考虑假设能将所有磁盘移动到一根柱子上，那么最终肯定是移动到初始磁盘半径最大的那根柱子上。
那么考虑从这个柱子开始，每次往两边扩展，取大的贪心往这根柱子上移动。
如果不能移动就是不行。
因为考虑最后那根柱子上的磁盘半径肯定是递增的，所以不可能存在跨越移动的情况。
代码：
#include <bits/stdc++.h>
using namespace std;
#define N 200010
int n, a[N];
int main() {
while (scanf("%d", &n) != EOF) {
for (int i = 1; i <= n; ++i) scanf("%d", a + i);
int pos = 1;
for (int i = 2; i <= n; ++i) {
if (a[i] > a[pos]) pos = i;
}
int l = pos - 1, r = pos + 1;
bool F = 1;
int lst = a[pos];
while (l >= 1 || r <= n) {
if (l < 1) {
if (a[r] >= lst) {
F = 0;
break;
}
lst = a[r];
++r;
} else if (r > n) {
if (a[l] >= lst) {
F = 0;
break;
}
lst = a[l];
--l;
} else {
if (a[l] > a[r]) {
if (a[l] >= lst) {
F = 0;
break;
}
lst = a[l];
--l;
} else {
if (a[r] >= lst) {
F = 0;
break;
}
lst = a[r];
++r;
}
}
}
puts(F ? "YES" : "NO");
}
return 0;
}C. Array Splitting
题意：
有一个长度为\(n\)的序列\(a_i\)，要将序列分成\(k\)段，使得下式最小：
\[
\begin{eqnarray*}
\sum\limits_{i = 1}^k (max(i) - min(i))
\end{eqnarray*}
\]
其中\(max(i)\)表示第\(i\)段中最大的数，\(min(i)\)表示第\(i\)段中最小的数，保证\(a_i\)是单调非降序的。
思路：
考虑\(a_i\)是单调非降的，那么\(max(i) - min(i)\)这个东西肯定是区间的末尾减去区间的开头，那么注意到区间的末尾的下一个数即为下一个区间的开头，变换式子有：
\[
\begin{eqnarray*}
a_n - a_1 + \sum\limits_{i = 1}^{k - 1} a_{b_i} - a_{b_i + 1}
\end{eqnarray*}
\]
其中\(b_i\)表示第\(i\)段末尾的下标。
然后这个东西用堆维护一下，贪心取\(k - 1\)个即可。
代码：
#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define N 300010
int n, k, a[N];
int main() {
while (scanf("%d%d", &n, &k) != EOF) {
for (int i = 1; i <= n; ++i) {
scanf("%d", a + i);
}
ll res = a[n] - a[1];
vector <int> vec;
for (int i = 1; i < n; ++i) {
vec.push_back(a[i] - a[i + 1]);
}
sort(vec.begin(), vec.end());
for (int i = 0; i < k - 1; ++i) {
res += vec[i];
}
printf("%lld\n", res);
}
return 0;
}D. Yet Another Subarray Problem
题意：
有一个序列\(a_i\)，定义一个子区间的价值：
\[
\begin{eqnarray*}
\sum\limits_{i = l}^r a_i - k \left\lceil \frac{r - l + 1}{m} \right\rceil
\end{eqnarray*}
\]
问所有子区间中最大的价值是多少?
思路：
维护一个前缀和\(S\)，那么变换式子有：
\[
\begin{eqnarray*}
S_r - S_l - k \left\lceil \frac{r - l}{m} \right\rceil
\end{eqnarray*}
\]
我们希望将\(\left\lceil \frac{r - l}{m} \right\rceil\)拆开成\(\left\lceil \frac{r}{m} \right\rceil - \left\lceil \frac{l}{m} \right\rceil\)，但是这样是不行的。
注意到\(m\)很小，所以可以通过分类讨论一下将\(\left\lceil \frac{x}{m} \right\rceil\)按\(x \bmod m\)进行分类，然后讨论一下合并即可。
代码：
#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define N 300010
int n, m, k;
ll a[N];
ll f[20];
int main() {
while (scanf("%d%d%d", &n, &m, &k) != EOF) {
for (int i = 1; i <= n; ++i) scanf("%lld", a + i);
ll res = 0;
for (int i = 0; i < m; ++i) f[i] = 0;
f[0] = -k;
for (int i = 1; i <= n; ++i) {
a[i] += a[i - 1];
for (int j = 0; j < m; ++j) {
if (m - i % m >= m - j) {
res = max(res, a[i] - f[j] - 1ll * k * (i / m + 1));
} else {
res = max(res, a[i] - f[j] - 1ll * k * (i / m + 2));
}
}
f[i % m] = min(f[i % m], a[i] - 1ll * k * (i / m + 1));
}
printf("%lld\n", res);
}
return 0;
}E. Culture Code
题意：