题解：B4290 [蓝桥杯青少年组省赛 2022] 组合

· · 题解

思路

这题暴力过不了，因此蒟蒻问了一下 DeepSeek 思路（但并没有复制粘贴）。

首先计算出所有汤圆规格的最大公约数 pd，若 pd 等于 1，则说明所有规格数互质。知道这个条件可以干什么呢？举个例子，若输入是

2
2 4

2 和 4 它们并不互质，它们的最大公约数是 2，则只要不是 2 的倍数，如 5、7、11 都不行，这样的数有无数个，所以只要不互质，输出 -1 即可。

int pd = num[0];
rep(i, 1, n) {
    pd = gcd(pd, num[i]);
}
if (pd != 1) {
    cout << -1;
    return 0;
}

在遍历过程中，初始的判断数组首项设为真，表示 0 个汤圆是可被组合的。当连续可以组合的汤圆数量达到最小规格便可以停止遍历。

AC Code

#include <bits/stdc++.h>
#define rep(i,a,b) for(int i=a;i<b;i++)
#define upto(i,a,b) for(int i=a;i<=b;i++)
const int N = 1e6 + 10;//上限
typedef long long ll;
using namespace std;
int num[30], n;
int cnt = 0, tmp = 0, maxcnt = 0;
bool check[N];

int gcd(int a, int b) {//辗转相除法求最大公约数
    if (b == 0) {
        return a;
    } else {
        return gcd(b, a % b);
    }
}

void input() {
    cin >> n;
    rep(i, 0, n) {
        cin >> num[i];
    }
    sort(num, num + n);
}

int main() {
    input();
    int pd = num[0];
    rep(i, 1, n) {
        pd = gcd(pd, num[i]);
    }
    if (pd != 1) {
        cout << -1;
        return 0;
    }
    memset(check, false, sizeof check);//初始化
    check[0] = true;
    rep(i, 1, N) {
        rep(j, 0, n) {
            if (num[j] > i)
                break;
            if (check[i - num[j]]) {
                check[i] = true;
                break;
            }
        }
        if (check[i]) {
            tmp++;
            if (tmp >= num[0]) {
                maxcnt = i - num[0];
                break;
            }
        } else {
            cnt++;
            tmp = 0;
        }
    }
    cout << cnt;
    return 0;
}