解题思路:
有无限个解的条件是:
最大公约数不为1
如果不是1的话,说明是和某个数成倍数关系,所以可以得出组合的只能是那个数的倍数
有限个解的判断条件:
穷举法:
先把第一个蒸笼能放的位置列举出来,也就是第一个蒸笼能放包子的各种倍数
例如:2的话就是 2,4,6,8,10,12,14............
之后,再把下一个蒸笼能放的数列举出来,并且再和第一种的组合起来,
例如:第二个数是3的话,和3成倍数的:3,6,9,12,15,18......
再和第一种组合起来:2+3,4+3,6+3,8+3,10+3.........
5,7,9,11,13......
再和2,4,6,8,10,12,14.......组合起来就是:2,4,5,6,7,8,9,10,11,12,13,14.......
之后再以此类推
注意事项:
参考代码:
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 | #include <stdio.h> #define N 100000 int b[N]; //定义一个全局变量 int gcd( int num1, int num2) //求最大公约数 { return num2 == 0 ? num1 : gcd(num2, num1 % num2); } int fun( int a[] , int n) //判断解是不是有无穷个 { int t = a[0]; for ( int i = 1; i < n; i++) t = gcd(t, a[i]); if (t > 1) return 1; return 0; //若返回1,则说明有无穷个解 } void judge( int a[], int n) //判断有多少个解 { b[0] = 1; for ( int i = 1; i <= n; i++) for ( int j = a[i - 1]; j < N; j++) if (b[j - a[i - 1]] == 1) b[j] = 1; //j 比 j - a[i-1] 多了个 a[ i -1 ] } int result( int b[]) //如果是有穷解的话,判断有多少个结果 { int count = 0; for ( int i = 0; i < N; i++) if (b[i] != 1) count++; return count; } int main() { int n, i, a[101]; scanf ( "%d" , &n); for (i = 0; i < n; i++) scanf ( "%d" , &a[i]); if (fun(a, n)) printf ( "INF\n" ); else { judge(a, n); printf ( "%d" , result(b)); } return 0; } |
9.9 分
6 人评分
C语言网提供由在职研发工程师或ACM蓝桥杯竞赛优秀选手录制的视频教程,并配有习题和答疑,点击了解:
一点编程也不会写的:零基础C语言学练课程
解决困扰你多年的C语言疑难杂症特性的C语言进阶课程
从零到写出一个爬虫的Python编程课程
只会语法写不出代码?手把手带你写100个编程真题的编程百练课程
信息学奥赛或C++选手的 必学C++课程
蓝桥杯ACM、信息学奥赛的必学课程:算法竞赛课入门课程
手把手讲解近五年真题的蓝桥杯辅导课程
发表评论 取消回复