SSL-OI Summer Camp 2020.08.23 Group A

Open Zhihu: How to accept your own ordinariness? Three easy problems, ZZY has AK'd. And me, even getting 100 points is ugly.

A Lost

Meaning

Given a set of numbers, what is the smallest number that cannot be obtained by summing a subset?

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

Story

Writing this problem is indeed quite disheartening.

It must be a conclusion problem, so I chose to write partial scores. People still need ambition, so I thought for an hour and derived a wrong conclusion. (Clearly the conclusion is so obvious)

Although later with difficulty corrected it: Let $ans$ be the current smallest unattainable number, then $ans-1$ is the largest attainable number. We add numbers in ascending order: now adding a number $x$, if there is a number smaller than $x$ that has not been achieved, then after adding $x$, adding numbers after $x$ cannot achieve that number, so at this point $ans$ is the answer.

If $ans\geq x$, obviously adding $x$ to each number in $[0,ans)$ makes the achievable set become $[0,ans+x)$, so update $ans$ accordingly.

#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 Optimal Route

Meaning

Given a graph with $n$ points and $m$ edges, with edge weights and node weights. The path value is calculated as: the maximum node weight on the path multiplied by the maximum edge weight on the path. Question: What is the minimum path value between all pairs of points?

$n\leq500$, edge weights and node weights sum not exceeding $10^9$. (Need to use long long)

Solution

No story, I think Floyd is troublesome and would definitely fail, so I didn't write it. So:

Consider that Floyd is a process of gradually adding points. We add points in ascending order of node weight, so each time after adding, this point must be the maximum in the current path (excluding the two endpoints), and we don't need to consider the influence of other points in the path. If adding this point reduces the maximum edge weight, then try to update the answer (maximum edge weight multiplied by the maximum of the current node weight and the two endpoint node weights). Otherwise, do not update, because we enumerated node weights in ascending order.

#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;
}

The preprocessing part may need further study. I added unsigned when I later corrected the problem, and only passed after preprocessing to -1. There may be some strange things to note.

C Teleport Dad

Teleport me I didn't write this problem, it's a BFS/SPFA easy problem