SSL-OI夏日合宿 2020.08.23 A组

摘要： A 组选手在三道题中表现不佳，尤其是在失落情绪下导致一道结论题做错。B 组选手通过魔改 Floyd 算法解决了最优路线问题。C 组选手因未提交代码而未得分。

打开知乎: 如何接受自己的平凡?
三道水题, ZZY已AK. 而我, 连100分都拿得难看.

A 失落

题意

给出一个数的集合, 问子集求和不能得到的最小的数是多少?

$n\leq100000$, $1 \leq a_i \leq 10^9$

故事

写这题确实挺失落的.

肯定是一道结论题, 所以我选择打部分分. 人还是要有志向的, 所以就想了一个钟, 推出了一个错误的结论. (明明结论那么显然)

虽然后面艰难地改过来了: 设$ans$为目前最小不能达成的数字, 那么$ans-1$就是最大能达成的数字. 我们升序加入数字: 现在加入一个数$x$, 若有小于$x$的数没有达成, 那么加入$x$后, 加入$x$后面的数, 都不可能达成那个数, 所以此时$ans$即为答案.

若$ans\geq x$, 显然将$[0,ans)$内的数分别加上$x$, 可以达成的数集变为了$[0,ans+x)$, 如此更新$ans$即可.

#define MXN (1000000)

#include <stdio.h>

#include <algorithm>

long long n, a[MXN], ans = 1;

signed main() {
#ifndef ONLINE_JUDGE
    freopen("A.in", "r", stdin);
#endif

    scanf("%lld", &n);
    for (int i = 0; i < n; ++i)
        scanf("%lld", &a[i]);

    std::sort(a, a + n);

    for (int i = 0; i < n && ans >= a[i]; ++i)
        ans += a[i];

    printf("%lld", ans);

    return 0;
}

B 最优路线

题意

给一张$n$点$m$边的图, 有边权点权. 路径值的计算方法是: 路径上最大点权乘上路径上最大边权. 问: 所有点对之间的路径最小值是多少?

$n\leq500$, 边权点权和不超过$10^9$. (要开long long)

题解

没有故事, 我觉得Floyd很麻烦还必挂就没打了. 于是:

考虑Floyd是逐渐加点的过程, 我们按点权升序加点, 这样每次加入后这个点必是当前路径中(除开两个端点)最大值, 不用考虑路径中其他点的影响. 如果加入这个点后使边权最大值变小, 则尝试更新答案(最大边权乘上当前点权和两个端点点权的最大值). 否则不更新, 因为我们升序枚举了点权.

#include <stdio.h>
#include <string.h>

#include <algorithm>
#include <queue>

#define MXN (520)

int n, m;

struct Edge {
    int v, w;
};
std::vector<Edge> edge[MXN];

unsigned long long node[MXN], f[MXN][MXN], ans[MXN][MXN], bcp;

int rk[MXN];
bool cmp(int x, int y) { return node[x] < node[y]; }

signed main() {
#ifndef ONLINE_JUDGE
    freopen("B.in", "r", stdin);
#endif

    memset(f, -1, sizeof(f));
    memset(ans, -1, sizeof(ans));
    bcp = f[0][0];

    scanf("%d%d", &n, &m);

    for (int i = 1; i <= n; ++i)
        scanf("%lld", &node[i]);
    for (int i = 0, u, v, w; i < m; ++i)
        scanf("%d%d%d", &u, &v, &w), f[u][v] = f[v][u] = w;

    for (int i = 1; i <= n; ++i)
        rk[i] = i;
    std::sort(rk + 1, rk + 1 + n, cmp);

    for (int i = 1, j; i <= n; ++i)
        for (j = 1; j <= n; ++j)
            ans[i][j] = f[i][j] * std::max(node[i], node[j]);

    for (int i = 1, j, k, x; i <= n; ++i)
        for (x = rk[i], j = 1; j <= n; ++j)
            for (k = 1; k <= n; ++k)
                if (std::max(f[j][x], f[x][k]) <= f[j][k])
                    f[j][k] = std::max(f[j][x], f[x][k]), ans[j][k] = std::min(ans[j][k], f[j][k] * std::max(node[x], std::max(node[j], node[k])));

    for (int i = 1; i <= n; ++i)
        ans[i][i] = 0;
    for (int i = 1, j, k; i <= n; ++i, putchar('\n'))
        for (j = 1; j <= n; ++j)
            printf("%lld ", (ans[i][j] == bcp) ? (-1) : (ans[i][j]));

    return 0;
}

在预处理部分可能需要再研究一下, 我是后来该题的时候加了unsigned, 预处理成-1才过的, 可能有一些奇怪的地方需要注意.

C 传送爸爸

传送我
这题没写, 是BFS/SPFA水题