本文主要是介绍第八届蓝桥杯——包子凑数,希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!
【问题描述】
小明几乎每天早晨都会在一家包子铺吃早餐。
他发现这家包子铺有 N 种蒸笼,其中第 i 种蒸笼恰好能放 Ai 个包子。
每种蒸笼都有非常多笼,可以认为是无限笼。
每当有顾客想买 X 个包子,卖包子的大叔就会迅速选出若干笼包子来,使得这若干笼中恰好一共有 X 个包子。
比如一共有 3 种蒸笼,分别能放 3、4 和 5 个包子。
当顾客想买 11 个包子时,大叔就会选 2 笼 3 个的再加 1 笼 5 个的(也可能选出 1 笼 3 个的再加 2 笼 4 个的)。
当然有时包子大叔无论如何也凑不出顾客想买的数量。
比如一共有 3 种蒸笼,分别能放 4、5 和 6 个包子。
而顾客想买 7 个包子时,大叔就凑不出来了。
小明想知道一共有多少种数目是包子大叔凑不出来的。
【输入格式】
第一行包含一个整数 N。
接下来 N 行,每行包含一个整数 Ai。
【输出格式】
输出一个整数代表答案。
如果凑不出的数目有无限多个,输出INF。
【输入样例1】
2
4
5
【输出样例】
6
【输入样例2】
2
4
6
【输出样例2】
INF
【数据范围】
1 ≤ N ≤ 100
1 ≤ Ai ≤ 100
解题思路:
【点击了解】关于不定方程的数学知识
题解
数论 & 完全背包:
#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>using namespace std;const int N = 10010;
int a[110];
bool f[110][N];int gcd(int a, int b)
{return b ? gcd(b, a % b): a; // 求最大公约数
}int main()
{int n;cin >> n;int d = 0;for (int i = 1; i <= n; i ++){cin >> a[i];d = gcd(d, a[i]);}if(d != 1) puts("INF"); // 最大公约数不是 1,凑不到的数一定无穷多else{f[0][0] = true; // 0 个包子肯定能凑到for (int i = 1; i <= n; i ++)for (int j = 0; j < N; j ++){f[i][j] = f[i - 1][j]; if(j >= a[i]) f[i][j] |= f[i][j - a[i]]; // 体积够大才能往里装}int ans = 0;for (int i = 0; i < N; i ++) if(!f[n][i]) ans ++;cout << ans << endl; }return 0;
}
空间优化
#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>using namespace std;const int N = 10010;
int a[110];
bool f[N];int gcd(int a, int b)
{return b ? gcd(b, a % b): a;
}int main()
{int n;cin >> n;int d = 0;for (int i = 1; i <= n; i ++){cin >> a[i];d = gcd(d, a[i]);}if(d != 1) puts("INF"); else{f[0] = true; for (int i = 1; i <= n; i ++)for (int j = a[i]; j < N; j ++){f[j] |= f[j - a[i]]; }int ans = 0;for (int i = 0; i < N; i ++) if(!f[i]) ans ++;cout << ans << endl; }return 0;
}
这篇关于第八届蓝桥杯——包子凑数的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!