SSL-OI夏日合宿 2020.08.23 A组

今天的题略水, 可能是因为最后一天了, 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.

口胡

题意没仔细看, 大概就是会用一种特殊的方法生成边权, 求单源最短路.