【解题报告】Educational Codeforces Round 21

题目链接

---

A. Lucky Year（Codeforces 808A）

思路

本题的入手点是，想明白一个正整数只有一个非零位是什么概念。
一个正整数只有一个非零位，那么这个数就只有最高位有非零位，也就可以表示成表示成这样： $a * 10 ^ b$ ，其中 $a \in [1, 9]$ 。
那么我们可以设计出这样的算法：将正整数 $n$ 的最高位增加 $1$ （如果是 $9$ 的话就增加到 $10$ ），然后将所有其它为清零得到一个新的数 $k$ ，最后 $k - n$ 就是答案。

代码

#include <bits/stdc++.h>
using namespace std;typedef long long ll;
string s;
ll k, d;int main() {ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);cin >> s;k = s[0] - '0' + 1;for(int i = 1; i <= s.size() - 1; i++) {k *= 10;}stringstream ss;ss << s;ss >> d;cout << k - d << endl;return 0;
}

---

B. Average Sleep Time（Codeforces 808B）

思路

本题的入手点在于，熟悉前缀和数组或能够构造出所需数列。
这道题要求的东西实际上是一个“奇怪的平均值”：“奇怪的和 $s$ ”除以 $(n - k + 1)$ 。其中 $s$ 为一个长度为 $k$ 的滑窗（也就是一个“可以滑动的区间”，其轨迹为 $[1, k], [2, k + 1], ...$ ）扫过长度为 $n$ 的数组，在每个状态中将滑窗中的数求和，再将所有和求和的结果。也就是说，如果我们可以模拟滑窗的前进，并能够实时高效地查询滑窗内的和就能够将本题解决。设 $b[i] = \sum_limits_{j = 1}^i a[i]$ ，也就是设 $b$ 为 $a$ 的前缀和数组，那么当我们的滑窗走到 $[i, i + k - 1]$ 这个区间的时候其区间的和为 $b[i + k - 1] - b[i - 1]$ 将其累加进答案即可。
当然，除了前缀和外，还可以直接计算答案。直接计算答案的思路是考虑数组中每个元素在 $s$ 中的贡献度。我们可以先考察 $n = 7，k = 3$ 时各个元素在 $s$ 中的加和次数，将其写成数列的形式为：

$1, 2, 3, 3, 3, 2, 1$

现在根据规律尝试推广，于是尝试求推广后数列的通项公式设 $f(n, k, i)$ 为数组长度为 $n$ ，滑窗大小为 $k$ 时数列第 $i$ 项的元素，那么 $f(n, k, i) = min{k, n - k + 1, i, n - i + 1}$ 。
（以下代码为方法 $2$ 的代码）

代码

#include <bits/stdc++.h>
using namespace std;const int maxn = 2e5 + 10;
int n, k, a;
double ans;int main() {ios::sync_with_stdio(false);cout.tie(0);cin.tie(0);cin >> n >> k;for(int i = 1; i <= n; i++) {cin >> a;ans += 1.0 * a * min(min(k, n - k + 1), min(i, n - i + 1));}cout << setprecision(7) << fixed;cout << ans / (n - k + 1) << endl;return 0;
}

---

C. Tea Party（Codeforces 808C）

思路

本题的入手点在于逐步地满足条件。
首先，我们一定可以给每个杯子倒上一半的水，如果不行的话就无解。那么接下来只剩下把水壶中的水全部倒出来这一个条件需要满足了。显然，可以通过贪心地从大杯子到小杯子依次将杯子倒满来满足条件。

代码

#include <bits/stdc++.h>
using namespace std;typedef pair <int, int> p;
const int maxn = 110;
int n, w, a, idx, cur, tmp, ans[maxn];
p ps[maxn];int main() {ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);cin >> n >> w;for(int i = 1; i <= n; i++) {cin >> a;ps[i] = p(a, i);}sort(ps + 1, ps + n + 1);for(int i = 1; i <= n; i++) {a = ps[i].first;idx = ps[i].second;cur = max(cur, a / 2 + (a % 2 > 0));ans[idx] = cur;w -= cur;if(w < 0) {cout << -1 << endl;return 0;}if(i == n && w > 0) {ans[idx] += w;}}for(int i = n; i >= 1; i--) {a = ps[i].first;idx = ps[i].second;ans[idx] += tmp;if(ans[idx] > a) {tmp = ans[idx] - a;ans[idx] = a;}else {tmp = 0;}}for(int i = 1; i <= n; i++) {cout << ans[i] << ' ';}return 0;
}

---

D. Array Division（Codeforces 808D）

思路

本题的入手点在于考察将一个元素移动后会对结果有什么影响。
假设有下面的数组：

$2 2 3 4 5$

我们将其做一个划分（用竖线）：

$2 2 3 4 | 5$

显然，将 $3$ 移动到竖线右边就能使得竖线左右两边的和相等。

$2 2 4 | 3 5$

可以观察到，将$3$从竖线左边移动到竖线右边，使得竖线左边的数字之和减少了$3$，而右边增加了$3$。也就是说，左右两边的和的差值减少了$6$。
那么显然，如果已经知道了竖线的位置，同时分别知道了竖线左边的数字之和$s1$，也知道了竖线右边的数字之和$s2$，如果竖线左边存在数字$(s1 - s2) / 2$，或竖线右边存在数字$(s2 - s1) / 2$的话，就表示可以通过将元素右移或左移来使得竖线两边之和相等。
所以我们可以预处理出前缀和数组与后缀和数组，枚举竖线的位置的同时用$STL$的$set$维护竖线左右两边元素的位置，就可以为上面提到的算法高效地提供所有所需数据了。

代码

#include <bits/stdc++.h>
using namespace std;typedef long long ll;
const int maxn = 1e5 + 10;
int n, a[maxn];
ll d, L[maxn], R[maxn];
set <ll> ls, rs;int main() {ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);cin >> n;for(int i = 1; i <= n; i++) {cin >> a[i];}for(int i = 1; i <= n; i++) {L[i] = L[i - 1] + a[i];}for(int i = n; i >= 1; i--) {R[i] = R[i + 1] + a[i];}for(int i = 1; i <= n; i++) {d = R[i + 1] - L[i];if(d == 0 || d < 0 && d % 2 == 0 && ls.count(-d / 2)) {cout << "YES" << endl;return 0;}ls.insert(a[i]);}for(int i = n; i >= 1; i--) {d = L[i - 1] - R[i];if(d == 0 || d < 0 && d % 2 == 0 && rs.count(-d / 2)) {cout << "YES" << endl;return 0;}rs.insert(a[i]);}cout << "NO" << endl;return 0;
}

---

E. Selling Souvenirs（Codeforces 808E）

思路

本题的入手点是，在动态规划中选用贪心策略。
虽然本题长得很像背包问题，但是因为物品数量和背包容量的乘积太大，所以不能用传统的方法来做。跟传统的问题相比，物品的种类只有三种（重量分别为$1， 2， 3$），这给了我们优化的契机。对于每种物品，我们显然会先拿价值比较高的。
因此我们可以将三种物品的价值分别放入数组$tab[1], tab[2], tab[3]$中，然后分别对这三个数组排序。用$tab[1]，tab[2]$和动态规划预处理出$d[]$数组，其中$d[i]$表示只考虑重量为$1$和$2$的物品，并且已经拿了总重为$i$的物品时，能拿到的物品最大价值，在动态规划的过程中每次要向背包加入某种重量中最大价值的物品。然后对于第三种物品，将其加入背包的方法是，枚举结果中拿的第三种物品的数量$j$，那么对于$j$，答案就是$d[m - 3j] + sum_{tab[3]}(1, j)$。$sum$函数代表对某个数组求区间内元素的和，这里的意思是对$tab[3]$数组的前j个元素求和（可以用前缀和数组优化一下）。
那么可不可以在动态规划的过程中考虑三种物品而不是两种物品呢？答案是可以，但是要考虑的情况就要复杂一些，比如，当要向背包加入重量为$3$的物品时，有可能是加入三件重量为$1$的物品，一件重量为$2$和一件重量为$1$的物品或一件重量为 3 <script type="math/tex" id="MathJax-Element-1212">3</script>的物品。

代码

#include <bits/stdc++.h>
using namespace std;typedef long long ll;
const int maxm = 3e5 + 5;
vector <ll> tab[4];
int n, m, w, x, c[3][maxm];
ll ans, d[maxm], sum[maxm];bool cmp(ll a, ll b) {return a > b;
}int main() {ios::sync_with_stdio(false);cout.tie(0);cin.tie(0);cin >> n >> m;for(int i = 1; i <= n; i++) {cin >> w >> x;tab[w].push_back(x);}for(int i = 1; i <= 3; i++) {sort(tab[i].begin(), tab[i].end(), cmp);}for(int j = 0; j < m; j++) {sum[j + 1] = sum[j];if(j < tab[3].size()) {sum[j + 1] += tab[3][j];}}if(tab[1].size() > 0) {d[1] = tab[1][0];c[1][1] = 1;}for(int i = 2; i <= m; i++) {for(int j = 1; j <= 2; j++) {if(c[j][i - j] >= tab[j].size()) {continue;}if(d[i] < d[i - j] + tab[j][c[j][i - j]]) {d[i] = d[i - j] + tab[j][c[j][i - j]];c[j][i] = c[j][i - j] + 1;c[j^3][i] = c[j^3][i - j];}}}for(int i = 0; i <= m; i++) {ans = max(ans, d[i] + sum[(m - i) / 3]);}cout << ans << endl;return 0;
}

---

（其它题目略）