第八届蓝桥杯——包子凑数

2024-02-02 08:59
文章标签 蓝桥 第八届 包子 凑数

本文主要是介绍第八届蓝桥杯——包子凑数,希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!

【问题描述】

小明几乎每天早晨都会在一家包子铺吃早餐。

他发现这家包子铺有 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;
}

这篇关于第八届蓝桥杯——包子凑数的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!



http://www.chinasem.cn/article/670182

相关文章

C语言蓝桥杯

一、语言基础 竞赛常用库函数 最值查询 min_element和max_element在vector(迭代器的使用) nth_element函数的使用 例题lanqiao OJ 497成绩分析 第一种用min_element和max_element函数的写法 第二种用min和max的写法 二分查找 二分查找只能对数组操作 binary_s

找不同-第15届蓝桥省赛Scratch初级组真题第4题

[导读]:超平老师的《Scratch蓝桥杯真题解析100讲》已经全部完成,后续会不定期解读蓝桥杯真题,这是Scratch蓝桥杯真题解析第183讲。 如果想持续关注Scratch蓝桥真题解读,可以点击《Scratch蓝桥杯历年真题》并订阅合集,查阅教程更方便。 第15届蓝桥杯省赛已于2024年8月24日落下帷幕,编程题一共有5题,分别如下: 猪八戒落地 游乐场 画西瓜 找不同 消

【蓝桥杯嵌入式(一)程序框架和调度器】

蓝桥杯嵌入式(一)程序框架和调度器 序、代码命名规则零、STM32和8051⼀、软件及环境安装⼆、⼯程框架搭建1.时钟配置2、SYS配置3、⼯程配置4、NVIC配置5.、Keil配置 三、系统初始化四、任务调度器 链接: 视频出处 序、代码命名规则 以下是一些常见的举例 零、STM32和8051 链接: 8位和32位单片机最本质区别 ⼀、软件及环境安装

【蓝桥杯嵌入式(二)Led、Key、Lcd】

蓝桥杯嵌入式(二)Led、Key、Lcd 五、Led模块1.原理图配置2. 知识点3.底层代码 六、Key模块1.原理图配置2.知识点3.底层代码底层代码(四⾏代码版本)底层代码(状态机版本) 七、LCD模块1.原理图配置2.知识点底层代码 五、Led模块 1.原理图配置 2. 知识点 链接: 上拉电阻的通俗解释 链接: 单⽚机怎么输出⾼电平!推挽输出和开

蓝桥杯:整数删除

// 蓝桥杯整数删除.cpp : Defines the entry point for the console application.//#include "stdafx.h"#include<stdio.h>#define MAX 100void findmin(int a[],int n,int& pos){int min=a[0];pos=0;//pos=0我开始忘了,特别注意

第十五届蓝桥杯图形化省赛题目及解析

第十五届蓝桥杯图形化省赛题目及解析 一. 单选题 1. 运行以下程序,角色会说( )? A、29     B、31     C、33     D、35 正确答案:C 答案解析: 重复执行直到m>n不成立,即重复执行直到m<=n。所有当m小于或者 等于n时,循环结束。循环过程中变量m与变量n的变化如下表: 通过上述表格可知,循环到第五次循环结束。m的值为14,n的值为19

第八届蓝桥杯 最大公共子串(动态规划)

标题:最大公共子串 最大公共子串长度问题就是: 求两个串的所有子串中能够匹配上的最大长度是多少。 比如:"abcdkkk" 和 "baabcdadabc", 可以找到的最长的公共子串是"abcd",所以最大公共子串长度为4。 下面的程序是采用矩阵法进行求解的,这对串的规模不大的情况还是比较有效的解法。 请分析该解法的思路,并补全划线部分缺失的代码。 #include <stdio.h

蓝桥杯第八届 方格分割(dfs)

标题:方格分割6x6的方格,沿着格子的边线剪开成两部分。要求这两部分的形状完全相同。如图:p1.png, p2.png, p3.png 就是可行的分割法。试计算:包括这3种分法在内,一共有多少种不同的分割方法。注意:旋转对称的属于同一种分割法。请提交该整数,不要填写任何多余的内容或说明文字。   观察可得他是一个中心对称图形,我们只需要搜索它的对称线即可。我们可以把对称线抽象为从(

蓝桥杯备赛day02:递推

斐波那契数列 #include <bits/stdc++.h>using namespace std;int main(){int n;cin>>n;int dp[n+1];dp[1]=1;dp[2]=1;for(int i = 3;i <= n;i++) dp[i] = dp[i-1]+dp[i-2];cout<<dp[n];return 0;} n = int(input())

第八届湘潭大学程序设计比赛A题

A Love Letter Accepted : 33 Submit : 66Time Limit : 1000 MS Memory Limit : 65536 KB  题目描述   CodeMonkey终于下定决心用情书的方式向心爱的女神表白,当他历经几天几夜写完之后才知道女神有很多不喜欢的词,所以他不得不有把这些词删掉。例如:原文是:ILOVEYOU,女神不喜欢的词是‘LV’