SSL-OI夏日合宿 2020.08.18

摘要： 在SSL-OI夏日合宿中，参与者们面对了三道题目。T1是关于分火腿的问题，要求将火腿切成大小相等的份数，求最小切几刀，解法是输出$m-(n,m)$，其中$(n,m)$表示$n$和$m$的最大公约数。T2是关于工资分配的问题，要求将数组分成最多$m$块，求各块和的最大值最小，解法是二分答案并贪心遍历数组。T3是关于选择$k$个数使其$gcd$最大的问题，解法是记录每个值出现的次数，然后从大到小枚举答案，统计倍数出现次数的和，若大于等于$k$则为答案。整体而言，题目难度适中，参与者们在中午前就完成了所有题目的修改。下午计划修改昨天的题目，并关注NOI网络同步赛的情况。

今天大佬们都去打NOI网络同步赛了, 就我一个没报名QwQ.

于是就只有一个组别, 好像题还挺简单.(不是

然后就被初一爆踩了 /doge

T1 分火腿

题意

给出$n$根火腿, 要求切成大小相等的$m$份. 求最小切几刀.

故事

显然这是一道给小学生写的水题. 对于每$(n,m)$根火腿, 我们都可以少切一刀. 于是直接输出$(m-1)-((n,m)-1)$即$m-(n,m)$就好.

#include <stdio.h>

int T;

int gcd(int a, int b) { return (b == 0) ? (a) : gcd(b, a % b); }

signed main() {
    freopen("A.in", "r", stdin);

    scanf("%d", &T);

    for (int i, n, m; T-- > 0;)
        scanf("%d%d", &n, &m), printf("%d\n", m - gcd(n, m));

    return 0;
}

实际上这也是正解.

T2 工资

题意

给出一个数组$arr$, 最多划分成$m$块. 对划分出的每一块求和, 求最大值最小.

故事

T2就开始不会了QwQ.

求最大值最小的问题一般就二分答案吧? 那么我们对于二分出的最大值$lim$, 贪心地遍历$arr$, 一旦求和超过$lim$就另起一段. 总觉得贪心哪里不对, 但又不会证, 也想不出更好的方法.

#define MXN (100020)

#include <stdio.h>

#include <algorithm>

int n, m;
long long a[MXN];

int check(int lim) {
    int res = 0, cnt = 0;
    for (int i = 0; i < n; ++i)
        if ((cnt += a[i]) > lim)
            cnt = a[i], ++res;
        else if (cnt == lim)
            cnt = 0, ++res;
    return res + (cnt > 0);
}

long long l, r = MXN * MXN, md;

signed main() {
    freopen("B.in", "r", stdin);
    scanf("%d%d", &n, &m);
    for (int i = 0; i < n; ++i)
        scanf("%lld", &a[i]), l = std::max(l, a[i]);

    while (l < r) {
        if (check(md = (l + r) / 2) <= m)
            r = md;
        else
            l = md + 1;
    }

    printf("%d", r);

    return 0;
}

结果WA90? 奇奇怪怪. 稍微改了一贪心函数就过了.

待会研究一下贪心为啥正确.

T3 欠扁的CD

题意

给出$n$个数, 从中选$k$个, 使他们的$gcd$最大.

故事

T3就已经完全不会了, 感觉题目读得有点奇怪? 于是乎没有故事...

正解

好像果然是读题的问题, 如果多读几遍说不定就读懂了. 不出意外地, 这题也是大水题.

我们开一个$500000$的数组, 记录每个值出现的次数. 再从大到小枚举答案$ans$, 然后统计它的所有倍数出现次数的和, 若大于等于$k$即为答案. 是的, 正解非常暴力.

复杂度为 $O(\sum_{i=1}^{N}\frac{i}{N})$ 大概就是 $O(N\log{N})$. (我也不知道为啥)

#define MXN (500020)

#include <stdio.h>

#include <algorithm>

int n, k, top;
int cnt[MXN];
long long ans;

signed main() {
    freopen("C.in", "r", stdin);

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

    for (int i = 0, x; i < n; ++i)
        scanf("%d", &x), ++cnt[x], top = std::max(top, x);

    for (int i = top, j, res; i > 0; --i) {
        for (j = i, res = 0; j <= top; j += i)
            res += cnt[j];
        if (res >= k) {
            ans = i;
            break;
        }
    }

    printf("%lld", ans * k);

    return 0;
}

中午就把题全改完了, 今天的题确实简单.

下午把昨天的题改一改吧.

然后看一看今天他们打的NOI?