就像昵称(firstpage:代码搬运工)一样,本身也是一个菜鸟,只是吸收了别人的知识,化为己用,然后进行记录一下。同时也为广大的小白们,提供一份优质的答案。
题目描述
小明几乎每天早晨都会在一家包子铺吃早餐。他发现这家包子铺有 NN 种蒸笼,其中第 ii 种蒸笼恰好能放 A_iAi? 个包子。每种蒸笼都有非常多笼,可以认为是无限笼。
每当有顾客想买 XX 个包子,卖包子的大叔就会迅速选出若干笼包子来,使得这若干笼中恰好一共有 XX 个包子。比如一共有 3 种蒸笼,分别能放 3、4 和 5 个包子。当顾客想买 11 个包子时,大叔就会选 2 笼 3 个的再加 1 笼 5 个的(也可能选出 1 笼 3 个的再加 2 笼 4 个的)。
当然有时包子大叔无论如何也凑不出顾客想买的数量。比如一共有 3 种蒸笼,分别能放 4、5 和 6 个包子。而顾客想买 7 个包子时,大叔就凑不出来了。
小明想知道一共有多少种数目是包子大叔凑不出来的。
输入描述
第一行包含一个整数 NN (1 \leq N \leq 1001≤N≤100)。
以下 N 行每行包含一个整数 A_iAi? (1 \leq A_i \leq 1001≤Ai?≤100)。
输出描述
一个整数代表答案。如果凑不出的数目有无限多个,输出 INF。
输入输出样例
示例 1
输入
2
4
5
输出
6
样例说明凑不出的数目包括:1, 2, 3, 6, 7, 11。
示例 2
输入
2
4
6
输出
INF
样例说明所有奇数都凑不出来,所以有无限多个
运行限制
- 最大运行时间:1s
- 最大运行内存: 256M
#include
using namespace std;
int gcd(int m,int n){
if(n==0)return m;
return gcd(n,m%n);
}
int main(){
int n,a[101],i,g,j,ans=0;
bool f[10000];
f[0]=true;
cin>>n;
for(i=1;
i<=n;
++i){//核心代码(for循环)
cin>>a[i];
if(i==1)g=a[i];
else
g=gcd(g,a[i]);
//计算公约数
for(j=0;
j<10000;
++j){//对可以凑出的包子数进行标记
if(f[j])f[j+a[i]]=true;
}
}
if(g!=1){//若不互质,则为INF
cout<<"INF"<
审题初感受:
problem1:判断的最大范围是多少?
problem2:什么情况下会出现INF?
这两个问题也是解题的关键
思路:
要解这道题需要明白一个数学知识
两个或多个数互质(最大公约数等于1),则a1x1+a2x2=c有有限个解(a1,a2>0,c为常数),最大的判断范围为a1*a2-a1-a2。这里用两个数来举例子。
反之则为INF
最后,我有一个问题,如果读者有看见,希望可以尽己所能帮助笔者
当未对ans初始化时 int ans,测试用例结果为7;当进行初始化时int ans=0,测试用例结果为6。
这里笔者不是很明白,希望有大佬可以指点。
【2017年蓝桥杯省赛包子凑数】lastingandpostive
推荐阅读
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
- 蓝桥杯|2017年蓝桥杯省赛B组Java真题
- 蓝桥杯真题|2017年蓝桥杯C/C++ B组省赛题目汇总及部分题解
- 科创项目|计算机设计大赛国奖作品_1. 项目概要
- 蓝桥杯|蓝桥杯python(题目思路即解答(笔记,持续更新))
- 蓝桥杯|蓝桥杯 历届试题 剪格子Python实现(dfs 回溯)
- 蓝桥杯|第十届蓝桥杯省赛B组部分题解
- 蓝桥杯|2019第十届蓝桥杯省赛JAVA A组真题解析(带源码及解析)
- 算法|第十届蓝桥杯省赛B组题解记录
- 算法与数据结构|第十届蓝桥杯大赛软件类省赛Java研究生组-题解