当前位置: 首页 > news >正文

包子凑数【蓝桥杯】/完全背包

包子凑数

在这里插入图片描述
在这里插入图片描述
在这里插入图片描述
在这里插入图片描述

完全背包

完全背包问题和01背包的区别就是,完全背包问题每一个物品能取无限次。
思路:当n个数的最大公约数不为1,即不互质时,有无限多个凑不出来的,即n个数都可以表示成kn,k为常数且不为1。当n个数的最大公约数为1,到了某个数之后就全都可以凑出来。
根据本题的数据,可以直接遍历到10010就行

#include<iostream>
using namespace std;
//dp[i]表示i这个数可不可以被凑出来
int dp[10010];
//欧几里得算法求最大公约数
int gcd(int a,int b)
{return (b==0)?a:gcd(b,a%b);
}
int main()
{int n;cin>>n;int a[n],g;for(int i=0;i<n;i++) {cin>>a[i];if(i==0) g=a[i];else g=gcd(g,a[i]);}if(g!=1){cout<<"INF"<<endl;return 0;}dp[0]=1;//完全背包for(int i=0;i<n;i++){for(int j=a[i];j<10010;j++){dp[j]=max(dp[j],dp[j-a[i]]);}}int ans=0;for(int i=0;i<10010;i++){if(!dp[i]) ans++;}cout<<ans<<endl;return 0;
}

相关文章:

包子凑数【蓝桥杯】/完全背包

包子凑数 完全背包 完全背包问题和01背包的区别就是&#xff0c;完全背包问题每一个物品能取无限次。 思路&#xff1a;当n个数的最大公约数不为1&#xff0c;即不互质时&#xff0c;有无限多个凑不出来的&#xff0c;即n个数都可以表示成kn&#xff0c;k为常数且不为1。当n个…...

口语 4.6

drop the gun :逃避 radically 极大程度地 vastly cognition&#xff1a;认知能力 flaw缺陷 flawless&#xff1a;没有缺陷 interface&#xff1a;接口&#xff0c;交流处 retain&#xff1a;保留 down the rabbit hole&#xff1a;进入未知领域了 wrap your head aro…...

使用Docker 部署jenkins 实现自动化部署

使用Docker部署jenkins实现自动化部署ruoyi-vue docker jenkinsJava jenkinsfilevue jenkinsfileDockerfile 部署脚本Java Dockerfilenginx Dockerfilenginx-dev.conf 使用docker部署Jenkins&#xff0c;项目: https://gitee.com/y_project/RuoYi-Vue 作为部署项目示范 docker…...

golang语言系列:Web框架+路由 之 Gin

云原生学习路线导航页&#xff08;持续更新中&#xff09; 本文是golang语言学习系列&#xff0c;本篇对Gin框架的基本使用方法进行学习 1.Gin框架是什么 Gin 是一个 Go (Golang) 编写的轻量级 http web 框架&#xff0c;运行速度非常快&#xff0c;如果你是性能和高效的追求者…...

春招百题--堆

一、堆的定义 二、堆&#xff08;优先队列&#xff09; 堆通常用于实现优先队列&#xff08;priority_queue&#xff09;&#xff0c;大顶堆相当于元素按从大到小的顺序出队的优先队列。从使用角度来看&#xff0c;我们可以将“优先队列”和“堆”看作等价的数据结构。 堆的…...

全志A40i android7.1 移植wifi驱动的一般流程

一&#xff0c;问题分析 一般情况下移植一款模组&#xff0c;会涉及到驱动&#xff0c;firmware, hal层&#xff0c;方案端的适配。 下面以RTL8723ds为例详细列出移植的通用步骤。 二&#xff0c;移植步骤 1. 移植Wi-Fi驱动 从RTL原厂或者已经支持的其他把内核版本中获取驱动…...

Qt——Qt绘图之QPainter的使用总结(使用paintEvent实现旋转图片效果)

【系列专栏】:博主结合工作实践输出的,解决实际问题的专栏,朋友们看过来! 《项目案例分享》 《极客DIY开源分享》 《嵌入式通用开发实战》 《C++语言开发基础总结》 《从0到1学习嵌入式Linux开发》 《QT开发实战》 《Android开发实战》...

Day83:服务攻防-开发组件安全JacksonFastJson各版本XStreamCVE环境复现

目录 J2EE-组件Jackson-本地demo&CVE 代码执行 (CVE-2020-8840) 代码执行 (CVE-2020-35728&#xff09; J2EE-组件FastJson-本地demo&CVE FastJson < 1.2.24 FastJson < 1.2.47 FastJson < 1.2.80 (利用条件比较苛刻) J2EE-组件XStream-靶场&CVE …...

【QT+QGIS跨平台编译】056:【pdal_kazhdan+Qt跨平台编译】(一套代码、一套框架,跨平台编译)

点击查看专栏目录 文章目录 一、pdal_kazhdan介绍二、pdal下载三、文件分析四、pro文件五、编译实践一、pdal_kazhdan介绍 pdal_kazhdan 是 PDAL(Point Data Abstraction Library)相关的 Kazhdan 算法的实现。PDAL 是一个用于处理和分析点云数据的开源库,而 Kazhdan 算法通常…...

泰坦尼克号幸存者数据分析

泰坦尼克号幸存者数据分析 1、泰坦尼克号数据集2、数据集加载与概览3、泰坦尼克号幸存者数据分析4、哪些人可能成为幸存者&#xff1f; 1、泰坦尼克号数据集 泰坦尼克号的沉没是世界上最严重的海难事故之一&#xff0c;造成了大量的人员伤亡。这是一艘号称当时世界上最大的邮轮…...

Memcached 教程之 PHP 连接 Memcached 服务(十)

PHP 连接 Memcached 服务 在前面章节中我们已经介绍了如何安装 Memcached 服务&#xff0c;接下来我们为大家介绍 PHP 如何使用 Memcached 服务。 PHP Memcache 扩展安装 PHP Memcache 扩展包下载地址&#xff1a;PECL :: Package :: memcache&#xff0c;你可以下载最新稳定…...

【zlm】音视频流与音频流合并的设计

目录 设想一 设想二 方案三 关键技术 测试语句 测试脚本 参考文档 设想一 //开始录制_option.mp4_save_path custom_path;_option.mp4_max_second max_second;vector<Track::Ptr> mytracks getTracks();auto src MediaSource::find( DEFAULT_VHOST, "1&quo…...

typescript的工作流

先coding code.ts代码&#xff0c;由tsc编译code.ts生成code.js格式 npm install —save-dev lite-server 是用来安装轻量级的服务器&#xff0c;只是用来开发的一个服务器&#xff0c;真正到生产环境中时可能会使用类似于Apache的server或者汤姆猫一类的服务器&#xff0c;安…...

MATLAB下载与安装详细教程:从官方获取到成功启动

引言 MATLAB&#xff08;MATrix LABoratory&#xff09;作为一款全球知名的高级数值计算与数据分析平台&#xff0c;以其强大的矩阵运算能力、丰富的内置函数库以及直观易用的图形用户界面&#xff0c;深受科研人员、工程师和学生群体的青睐。无论是进行复杂的数学建模、信号处…...

【随笔】Git 高级篇 -- 分离 HEAD(十一)

&#x1f48c; 所属专栏&#xff1a;【Git】 &#x1f600; 作  者&#xff1a;我是夜阑的狗&#x1f436; &#x1f680; 个人简介&#xff1a;一个正在努力学技术的CV工程师&#xff0c;专注基础和实战分享 &#xff0c;欢迎咨询&#xff01; &#x1f496; 欢迎大…...

mac、windows 电脑安装使用多个版本的node

我们为啥要安装多个不同版本的node&#xff1f; 开发旧项目时&#xff0c;使用低版本Nodejs。开发新项目时&#xff0c;需使用高版本Node.js。可使用n同时安装多个版本Node.js&#xff0c;并切换到指定版本Node.js。 mac电脑安装 一、全局安装 npm install -g n 二、mac电脑…...

vue 浅解watch cli computed props ref vue slot axios nexttick devtools说明使用

Vue.js 是一个强大的前端框架&#xff0c;它提供了很多有用的功能和工具。你提到的这些特性&#xff08;watch、cli、computed、props、ref、slot、axios、nextTick、devtools&#xff09;在 Vue 中各自扮演着不同的角色。下面我会逐一解释这些特性如何在 Vue 中使用&#xff1…...

Unity自定义框架(1)-----------单例模式

前言&#xff1a; Unity作为一款强大的游戏开发引擎&#xff0c;其基础框架的设计对于项目的结构和性能有着重要的影响。其中&#xff0c;单例模式是一种常用的设计模式&#xff0c;用于确保一个类只有一个实例&#xff0c;并提供一个全局访问点。 什么是单例模式&#xff1f…...

04-自媒体文章-自动审核

自媒体文章-自动审核 1)自媒体文章自动审核流程 1 自媒体端发布文章后&#xff0c;开始审核文章 2 审核的主要是审核文章的内容&#xff08;文本内容和图片&#xff09; 3 借助第三方提供的接口审核文本 4 借助第三方提供的接口审核图片&#xff0c;由于图片存储到minIO中&…...

LeetCode-热题100:763. 划分字母区间

题目描述 给你一个字符串 s 。我们要把这个字符串划分为尽可能多的片段&#xff0c;同一字母最多出现在一个片段中。 注意&#xff0c;划分结果需要满足&#xff1a;将所有划分结果按顺序连接&#xff0c;得到的字符串仍然是 s 。 返回一个表示每个字符串片段的长度的列表。…...

C++_核心编程_多态案例二-制作饮品

#include <iostream> #include <string> using namespace std;/*制作饮品的大致流程为&#xff1a;煮水 - 冲泡 - 倒入杯中 - 加入辅料 利用多态技术实现本案例&#xff0c;提供抽象制作饮品基类&#xff0c;提供子类制作咖啡和茶叶*//*基类*/ class AbstractDr…...

解决本地部署 SmolVLM2 大语言模型运行 flash-attn 报错

出现的问题 安装 flash-attn 会一直卡在 build 那一步或者运行报错 解决办法 是因为你安装的 flash-attn 版本没有对应上&#xff0c;所以报错&#xff0c;到 https://github.com/Dao-AILab/flash-attention/releases 下载对应版本&#xff0c;cu、torch、cp 的版本一定要对…...

Matlab | matlab常用命令总结

常用命令 一、 基础操作与环境二、 矩阵与数组操作(核心)三、 绘图与可视化四、 编程与控制流五、 符号计算 (Symbolic Math Toolbox)六、 文件与数据 I/O七、 常用函数类别重要提示这是一份 MATLAB 常用命令和功能的总结,涵盖了基础操作、矩阵运算、绘图、编程和文件处理等…...

Unit 1 深度强化学习简介

Deep RL Course ——Unit 1 Introduction 从理论和实践层面深入学习深度强化学习。学会使用知名的深度强化学习库&#xff0c;例如 Stable Baselines3、RL Baselines3 Zoo、Sample Factory 和 CleanRL。在独特的环境中训练智能体&#xff0c;比如 SnowballFight、Huggy the Do…...

是否存在路径(FIFOBB算法)

题目描述 一个具有 n 个顶点e条边的无向图&#xff0c;该图顶点的编号依次为0到n-1且不存在顶点与自身相连的边。请使用FIFOBB算法编写程序&#xff0c;确定是否存在从顶点 source到顶点 destination的路径。 输入 第一行两个整数&#xff0c;分别表示n 和 e 的值&#xff08;1…...

微软PowerBI考试 PL300-在 Power BI 中清理、转换和加载数据

微软PowerBI考试 PL300-在 Power BI 中清理、转换和加载数据 Power Query 具有大量专门帮助您清理和准备数据以供分析的功能。 您将了解如何简化复杂模型、更改数据类型、重命名对象和透视数据。 您还将了解如何分析列&#xff0c;以便知晓哪些列包含有价值的数据&#xff0c;…...

嵌入式学习笔记DAY33(网络编程——TCP)

一、网络架构 C/S &#xff08;client/server 客户端/服务器&#xff09;&#xff1a;由客户端和服务器端两个部分组成。客户端通常是用户使用的应用程序&#xff0c;负责提供用户界面和交互逻辑 &#xff0c;接收用户输入&#xff0c;向服务器发送请求&#xff0c;并展示服务…...

安宝特案例丨Vuzix AR智能眼镜集成专业软件,助力卢森堡医院药房转型,赢得辉瑞创新奖

在Vuzix M400 AR智能眼镜的助力下&#xff0c;卢森堡罗伯特舒曼医院&#xff08;the Robert Schuman Hospitals, HRS&#xff09;凭借在无菌制剂生产流程中引入增强现实技术&#xff08;AR&#xff09;创新项目&#xff0c;荣获了2024年6月7日由卢森堡医院药剂师协会&#xff0…...

算法:模拟

1.替换所有的问号 1576. 替换所有的问号 - 力扣&#xff08;LeetCode&#xff09; ​遍历字符串​&#xff1a;通过外层循环逐一检查每个字符。​遇到 ? 时处理​&#xff1a; 内层循环遍历小写字母&#xff08;a 到 z&#xff09;。对每个字母检查是否满足&#xff1a; ​与…...

[免费]微信小程序问卷调查系统(SpringBoot后端+Vue管理端)【论文+源码+SQL脚本】

大家好&#xff0c;我是java1234_小锋老师&#xff0c;看到一个不错的微信小程序问卷调查系统(SpringBoot后端Vue管理端)【论文源码SQL脚本】&#xff0c;分享下哈。 项目视频演示 【免费】微信小程序问卷调查系统(SpringBoot后端Vue管理端) Java毕业设计_哔哩哔哩_bilibili 项…...