SSL-OI夏日合宿 2020.08.23 A组
摘要： SSL-OI 夏日合宿 A 组题目难度较低，前三道题是中山市选 2012 的原题，第四题是北爷出的附加题。作者 C 打挂，最后得分 180 分。下午发动学长限定技能，快速讲评快速下班。
今天的题略水, 可能是因为最后一天了, AJ让我么轻松一点.
前三道题是AJ直接拿的中山市选2012, 第四题是北爷挑的附加题. (但我没写)
C打挂了, 最后100+80+0+0=180
然后下午发动了学长限定技能: 快速讲评快速下班.
A 这是一棵树吗?
题意
给出一张图$n$个点的度数, 问是否可能是一棵树.
故事
超级大水题, 显然一棵树上有$n-1$条边, 每加入一条边会使整张图的度数和增加$2$. 判断度数和是否为$2n-2$, 特判如果$n>2$, 任一点的读书不能为0.
#include <stdio.h>
long long n, s;
bool pos = true;
signed main() {
#ifndef ONLINE_JUDGE
freopen("A.in", "r", stdin);
#endif
scanf("%lld", &n);
for (long long i = 0, a; i < n; ++i)
scanf("%lld", &a), pos &= (a > 0), s += a;
if (s == (n - 1) * 2 && (n == 1 || pos))
printf("Possible");
else
printf("Impossible");
return 0;
}B 选数排列
题意
给出$n$个数, 从中选出$R$组, 每组$C$个. 每组的贡献是其中的最大值减最小值, 问这$R$组的最大值最小是多少.
故事
还是那句话: 不贪心的人在比赛中也不会贪心.
为什么我一直对贪心的正确性那么怀疑呢? 还是因为对没能证明的东西总会有莫名的恐惧?
最后我打了$O(n^2)$的暴力, 因为数据年代久远所以拿了80? (这次我没在暴力外面套数据范围判断)
一个显然的结论: 每次选的数比是排完序后数组内的一段数. 如果有两组数所属的区间相交, 肯定可以通过交换元素使两者的最大值/最小值变优.
设$f_{i,j}$为选了$i$组, 选到了第$j$个数, 每组贡献的最大值的最小值. 转移如下:
$$ f_{i,j}=min_{k=0}^{k \leq j-C}f_{i-1,k} \ + \ P_j - P_{j-C} $$
#define MXN (500020)
#include <stdio.h>
#include <string.h>
#include <algorithm>
int N, R, C;
int P[MXN];
// Sub1
int a[MXN], f[1024][1024], min, ans = 1e9;
signed main() {
#ifndef ONLINE_JUDGE
freopen("B.in", "r", stdin);
#endif
scanf("%d%d%d", &N, &R, &C);
for (int i = 0; i < N; ++i)
scanf("%d", &P[i]);
std::sort(P, P + N);
for (int i = C - 1; i < N; ++i)
a[i] = P[i] - P[i - C + 1];
memset(f, 0x3f, sizeof(f));
for (int i = 0; i <= N; ++i)
f[0][i] = 0;
for (int i = 1, j; i <= R; ++i)
for (min = 1e9, j = C - 1; j < N; ++j)
f[i][j] = std::max(min = std::min(min, f[i - 1][j - C]), a[j]);
for (int i = 0; i < N; ++i)
ans = std::min(ans, f[R][i]);
printf("%d", ans);
return 0;
}题解
二分答案+贪心判断
跟前几天那个B......组题几乎一样, 我也几乎一样的不会.
我们二分出每组的最大和, 然后贪心地选出尽量多组数.
C 捡金子
考场没想清楚, 挂了.
题意
题意没说Trie, 但是很明显是Trie.
给出$M$个字符串, 每个串在Trie上的节点权值++. 在Trie上选出$n$条不相交的链, 问最大权值和是多少.
$M \leq 50000$, $N \leq 10$
题解
故事就是正解打挂了, 所以标题倔强地写成了题解.
对于每个点, 设$f_i$为在它的子树内选了$i$条链的最大权值和.
考虑将一棵子树$S$并入父亲: 我们从大到小枚举父亲被更新的$f_i$, 然后再枚的$j \in (0,i]$, 尝试用$f_j+S->f_{i-j}$更新父亲的$f_i$.
最后将父亲节点接入链中, 将权值直接加入$f_i$中即可. ($i \in [1,N]$)
D 魔术 (附加题)
开场1h后, 比赛描述中出现了这句话:
由于今天的题目过于简单，现为AK或即将AK的同学准备一道附加题。建议在完成前面所有题目之后再来做。不算很难，请同学们放心食用。
Z爷不屑于AB题, 直接切爆CD题QwQ. 而我只苟了ABC, 最后卑微Rank10.
口胡
题意没仔细看, 大概就是会用一种特殊的方法生成边权, 求单源最短路.