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

思路

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

首先计算出所有汤圆规格的最大公约数

pd

，若

pd

等于 1，则说明所有规格数互质。知道这个条件可以干什么呢？举个例子，若输入是

CPP

2
2 4

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

CPP

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

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

AC Code

CPP

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

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

文章操作

思路

AC Code

相关推荐

评论

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