解题以及补题报告。
原题链接：Codeforces1313A（✔）
题意：有三种物品，分别有 $a,b,c$ 个，给这些物品进行分组，要求得到尽可能多互不相同的组，满足每组至少有一种物品，且这种物品只能选 $1$ 个。求最多能分成多少组？
分析：假如都是无限个，稍加分析，最大值只能达到 $7$，贪心即可，先考虑 $1$ 个 $1$ 组，再考虑 $2$ 个一组，最后考虑 $3$ 个一组。然后凭感觉贪。
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
|
#include <bits/stdc++.h>
using namespace std;
int x[3], T, ans;
void solve() {
ans = 0;
cin >> x[0] >> x[1] >> x[2];
sort(x, x + 3);
int a = x[0], b = x[1], c = x[2];
if (a) ans++, a--;
if (b) ans++, b--;
if (c) ans++, c--;
if (b && c) ans++, b--, c--;
if (a && b) ans++, a--, b--;
if (a && c) ans++, a--, c--;
if (a && b && c) ans++;
cout << ans << endl;
}
int main() {
cin >> T;
while (T--) solve();
return 0;
}
|
原题链接：Codeforces1313B（✔）
题意：共两场比赛，有 $n$ 个人。第一场 Nikolay 排名为 $x$，第二场排名为 $y$，那么就得到一个分数 $x+y$，分数小于等于 $x+y$ 的人数就作为 Nikolay 的排名。需要求 Nikolay 的最好排名和最坏排名。
分析：这显然又是一个贪心，先考虑如何使得排名最小。那么就是需要让分数小于等于 $x+y$ 的人尽可能少，反过来考虑就是让分数大于 $x+y$ 的人尽可能多。现在有 $1\text{~}n$，每个数有两个，去掉 $x,y$，就是 $2n-2$ 个。我们需要用这些数，配对出尽可能多的大于 $x+y$ 的值，很显然只要找到一个合适的区间按大小首尾匹配即可，区间长度除以二就得到了大于 $x+y$ 的分数个数 $\rm tot$，$n-\rm tot$ 就是最好排名。
同样地，考虑最差排名，就是用 $2n-2$ 个数配对出最多的小于等于 $x+y$ 的值。那么只需要考虑 $[1,x+y-1]$ 区间内去除 $x,y$，首尾配对即可。
最后，两种排名都需要考虑边界问题。详见代码 $\text{line10,15}$。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
|
#include <bits/stdc++.h>
using namespace std;
int T, n, x, y;
void solve() {
scanf("%d%d%d", &n, &x, &y);
int t = x + y;
int m = max(1, t - n + 1);
int tot = (n - m + 1) * 2;
if (x >= m) tot--;
if (y >= m) tot--;
cout << n - tot / 2 << " ";
if (t - 1 <= n) tot = (t - 1) * 2 - 2;
else tot = 2 * n - 2;
cout << tot / 2 + 1 << endl;
}
int main() {
cin >> T;
while (T--) solve();
return 0;
}
|
原题链接：Codeforces1313C1（✔）
题意：有连续的 $n$ 块地，每块建的高楼最多能建 $m_i$ 层，$a_i$ 为实际层数，需要保证任意 $i < j < k$，不能出现 $a_i > a_j < a_k$ 的情况，求能使得高楼层数总和最大的 $a$ 序列。
分析：意思就是 $a$ 序列中不能出现“山谷”状。暴力枚举每一个点作为峰，向两边非递增延伸即可，求和之后，更新答案，$O(n^2)$。先交了一发贪心，结果 WA 掉了，还以为能一举过掉 C2，还是太菜了，写暴力就水个 C1 吧。
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
|
#include <bits/stdc++.h>
using namespace std;
typedef long long LL;
const int N = 1010;
int n;
int a[N], b[N], temp[N];
LL sum, maxs;
void check(int p) {
temp[p] = b[p];
sum = temp[p];
for (int i = p - 1; i; i--) {
if (b[i] <= temp[i + 1]) temp[i] = b[i];
else temp[i] = temp[i + 1];
sum += temp[i];
}
for (int i = p + 1; i <= n; i++) {
if (b[i] <= temp[i - 1]) temp[i] = b[i];
else temp[i] = temp[i - 1];
sum += temp[i];
}
if (sum > maxs) {
maxs = sum;
for (int i = 1; i <= n; i++) a[i] = temp[i];
}
}
int main() {
cin >> n;
for (int i = 1; i <= n; i++) scanf("%d", &b[i]);
for (int i = 1; i <= n; i++) check(i);
for (int i = 1; i <= n; i++) printf("%d ", a[i]);
puts("");
return 0;
}
|