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

【dp + 裴蜀定理】P8646 [蓝桥杯 2017 省 AB] 包子凑数题解

news 来源：原创 2025/5/9 10:42:01

P8646 [蓝桥杯 2017 省 AB] 包子凑数题解

题目传送门

P8646 [蓝桥杯 2017 省 AB] 包子凑数

一、题目描述

小明发现包子铺有N种蒸笼，每种能放A_i个包子（无限供应）。问有多少个正整数X无法被这些蒸笼数量的组合表示出来。若无限多个则输出INF。

二、题目分析

这是一个典型的数论+动态规划问题。需要解决两个关键点：

判断无法表示的数字是否有无限多个
有限情况下统计具体无法表示的数字个数

三、问题思考

算法分析

本题需要结合数论中的裴蜀定理和动态规划来解决。

前置知识：裴蜀定理

对于任意整数a,b，存在整数x,y使得ax+by=gcd(a,b)。推广到多个数：

当所有数的gcd=1时，只有有限多个数无法表示
当gcd>1时，所有不被gcd整除的数都无法表示（无限多个）

四、动态规划思路

a. 状态表示

f[j]表示数字j能否被表示（true/false）

b. 初始化

f[0] = true（0个包子总是可以表示）

c. 状态转移

对于每个蒸笼数量a[i]，从a[i]开始更新：

if(f[j - a[i]]) f[j] = true;

d. 最终结果

统计所有f[j]==false的j的个数

五、代码实现

#include <bits/stdc++.h>
using namespace std;
const int N = 110, M = 1e4 + 10; // N是蒸笼种类上限，M是DP数组大小
int n;
int a[N];// 计算最大公约数
int gcd(int a, int b) {return b == 0 ? a : gcd(b, a % b);
}bool f[M]; // DP数组int main() {ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);cin >> n;for (int i = 1; i <= n; i ++) cin >> a[i];// 计算所有数的gcdint g = a[1];for (int i = 2; i <= n; i ++) {g = gcd(g, a[i]);}// 根据gcd判断是否有无限解if (g != 1) {cout << "INF";return 0;}// DP过程f[0] = true; // 初始化for (int i = 1; i <= n; i ++) { // 遍历每种蒸笼for (int j = a[i]; j < M; j ++) { // 更新DP数组if(f[j - a[i]]) f[j] = true;}}// 统计结果int res = 0;for (int i = 1; i < M; i ++)if (!f[i]) res ++;cout << res;return 0;
}

六、重点细节

DP数组大小M：需要足够大（1e4）以确保能覆盖所有可能的解
状态转移顺序：必须正向更新，避免重复计算
初始化：f[0]=true是正确计算的基础
gcd计算：必须先判断gcd，避免无效的DP计算

七、复杂度分析

时间复杂度：O(N*M)，其中N≤100，M=1e4
空间复杂度：O(M)

八、总结

本题巧妙结合了数论和动态规划：

使用裴蜀定理判断解的有限性
通过完全背包式的DP统计具体解
代码简洁高效，体现了算法设计的精妙

关键点在于理解数论原理并将其与动态规划相结合，这也是算法竞赛中常见的解题思路。

List item

【dp + 裴蜀定理】P8646 [蓝桥杯 2017 省 AB] 包子凑数题解

P8646 [蓝桥杯 2017 省 AB] 包子凑数题解题目传送门 P8646 [蓝桥杯 2017 省 AB] 包子凑数一、题目描述小明发现包子铺有N种蒸笼，每种能放A_i个包子（无限供应）。问有多少个正整数X无法被这些蒸笼数量的组合表示出来。若无限多个则输出…...

编程日记 2025/5/9 10:42:01

在HarmonyOS NEXT 开发中，如何指定一个号码，拉起系统拨号页面

大家好，我是 V 哥。《鸿蒙 HarmonyOS 开发之路卷1 ArkTS篇》已经出版上市了哈，有需要的朋友可以关注一下，卷2应用开发篇也马上要出版了，V 哥正在紧锣密鼓的写鸿蒙开发实战卷3的教材，卷3主要以项目实战为主&#xff0…...

编程日记 2025/5/9 10:23:38

网络华为HCIA+HCIP 策略路由，双点双向

目录路由策略，策略路由策略路由优势策略路由分类接口策略路由双点双向双点双向路由引入特点: 联系路由回灌和环路问题路由策略，策略路由路由策略:是对路由条目进行控制，通过控制路由条目影响报文的转发路径，即路…...

编程日记 2025/5/8 15:51:40

探索Doris：日志分析的新宠，是否能取代老牌ES？

在大数据时代，日志存储与分析对于企业的运营和决策起着至关重要的作用。Elasticsearch（简称 ES）作为一款广泛应用的开源分布式搜索和分析引擎，长期以来在日志管理领域占据着举足轻重的地位。然而，随着技术的不断发展&a…...

编程日记 2025/5/9 10:39:18

常见电源模块设计

目录 1. 5V电源模块 2. 3.3V电源模块 3. 1.9V电源模块 4. 220V转12V电源模块 1. 5V电源模块参考电路电路说明： 这个电路采用的是稳压芯片78L05，我是用的12V的电源模块转成为5V,为后续的供电。 2. 3.3V电源模块参考电路： 电路说明…...

编程日记 2025/5/6 13:12:34

虚幻引擎控制角色跟随移动方向旋转的方法

在UE5中，要控制角色随移动方向旋转，可以使用蓝图和C两种方式来实现。使用蓝图 1、选中角色移动组件，勾选将旋转朝向运动。 2、选中当前角色类取消勾选使用控制器旋转的几个选项 3、这时，摄像机会跟着角色一起旋转。如果不希望…...

编程日记 2025/5/9 10:36:40

Oracle 23ai Vector Search 系列之3 集成嵌入生成模型（Embedding Model）到数据库示例，以及常见错误

文章目录 Oracle 23ai Vector Search 系列之3 集成嵌入生成模型（Embedding Model）到数据库示例，以及常见错误使用安装了Oracle 23ai 的虚拟机（Oracle Database 23ai Free VirtualBox Appliance）1.下载[Oracle VM Virtu…...

编程日记 2025/5/9 10:40:39

RISC-V debug专栏2 --- Debug Module(DM)

Debug Module（DM）的核心功能 DM 就像一个翻译官，负责把调试器的抽象指令（比如 “暂停处理器”）转换成硬件能听懂的具体操作。它必须实现以下基本功能： 必要功能（必须实现）&#xff…...

编程日记 2025/5/9 10:13:27

LLM 分词器Tokenizer 如何从 0 到 1 训练出来

写在前面大型语言模型（LLM）处理的是人类的自然语言，但计算机本质上只能理解数字。Tokenizer（分词器）就是架在自然语言和计算机数字表示之间的一座至关重要的桥梁。它负责将我们输入的文本字符串分解成模型能够理解的最小单元——Token，并将这些 Token 转换成对应的数字…...

编程日记 2025/5/9 10:35:09

蓝桥杯冲刺：一维前缀和

系列文章目录蓝桥杯系列：一维前缀和文章目录系列文章目录前言一、暴力的写法：二、一维前缀和的模板： 具体实现： 三、具体例题：求和 1.题目参考：2.以下是具体代码实现： 总结前言上次我介绍…...

编程日记 2025/5/9 9:54:09

光学关键尺寸量测设备市场报告：2024年全球市场销售额达到了14.75亿美元

一、引言光学关键尺寸量测设备作为半导体制造、精密加工等领域的核心工具，其重要性不言而喻。随着科技的飞速发展，这些设备在提升产品精度、缩短研发周期、降低生产成本等方面发挥着越来越关键的作用。本报告旨在深入分析光学关键尺寸量测设备的技术特…...

编程日记 2025/5/9 10:00:59

链表 160相交链表代码 class Solution { public:ListNode *getIntersectionNode(ListNode *headA, ListNode *headB) {ListNode* h1headA;ListNode* h2headB;while(h1&&h2){if(h1!h2){h1h1->next;h2h2->next;}else{return h1;}}if(h1nullptr){h1headB;}else{h…...

编程日记 2025/5/9 9:56:48

2025 年浙江危化品经营单位考试攻略分享

浙江的考试由省应急管理部门主导。理论考试突出危化品在电商、物流等新兴业态下的安全管理知识，这与浙江发达的电商产业紧密相关。对危险化学品的环境危害及防治知识考查细致。实际操作考核模拟杭州、宁波等地危化品仓储物流中心的作业情况。报名材料准备齐全后…...

编程日记 2025/5/9 9:41:19

python使用cookie、session、selenium实现网站登录（爬取信息）

一、使用cookie 这段代码演示了如何使用Python的urllib和http.cookiejar模块来实现网站的模拟登录，并在登录后访问需要认证的页面。 # 导入必要的库 import requests from urllib import request, parse# 1. 导入http.cookiejar模块中的CookieJar类，用…...

编程日记 2025/5/9 10:40:39

STM32开发板上生成PWM正弦波

在STM32开发板上生成正弦波通常需要结合定时器（TIM）、数模转换器（DAC）或脉宽调制（PWM）以及时钟系统的配置。以下是分步指南： 方法1：使用DAC 定时器（推荐） 步…...

编程日记 2025/5/9 10:20:29

Spring Boot 实现文件秒传功能

前言在开发Web应用时，文件上传是一个常见需求。然而，当用户需要上传大文件或相同文件多次时，会造成带宽浪费和服务器存储冗余。此时可以使用文件秒传技术通过识别重复文件，实现瞬间完成上传的效果，大大提升了用户体验…...

编程日记 2025/5/8 7:50:17

【Vue2】数据绑定_MVVM模型_数据代理_事件处理

目录一、数据绑定 1. Vue中有2种数据绑定的方式： 2. 响应式原理 el 与 data 的两种写法二、 MVVM模型三、数据代理 1.回顾Object defineproperty方法 2. 何为数据代理 3.Vue中的数据代理四、事件处理 1.事件的基本使用： 2. Vue中的事…...

编程日记 2025/5/9 9:49:57

Python数据类型-dict

Python数据类型-dict 字典是Python中一种非常强大且常用的数据类型，它使用键-值对(key-value)的形式存储数据。 1. 字典的基本特性无序集合：字典中的元素没有顺序概念可变(mutable)：可以动态添加、修改和删除元素键必须唯一且不可变&…...

编程日记 2025/5/9 9:45:39

win10之mysql server 8.0.41安装

一 mysql server 下载官网下载地址页面 https://dev.mysql.com/downloads/mysql/二免装版使用步骤 1 解压下载完成后,解压文件夹,如下所示: 2 执行安装命令 D:\soft\mysql\mysql-8.0.41-winx64\mysql-8.0.41-winx64\bin>mysqld --install Service successfully in…...

编程日记 2025/5/9 10:14:47

解决Oracle PL/SQL中“表或视图不存在“错误的完整指南

解决Oracle PL/SQL中"表或视图不存在"错误的完整指南前言问题概述根本原因分析一、编译时与运行时验证差异二、权限问题三、 Schema命名问题实际案例演示案例1：动态分表查询案例2：权限不足的场景实用排查步骤排查流程图最佳实践建议解决方…...

编程日记 2025/5/9 9:55:19

从实用的角度聊聊Linux下文本编辑器VIM

本文从实用的角度聊聊Vim的常用命令。何为实用？我举个不实用的例子大家就明白了，用vim写代码。;) “vim是从 vi 发展出来的一个文本编辑器。代码补全、编译及错误跳转等方便编程的功能特别丰富，在程序员中被广泛使用，和Emacs并列成…...

编程日记 2025/5/8 11:17:08

MySQL的进阶语法8（SQL优化——insert、主键、order by、group by、limit、count和update）

目录一、插入数据 1.1 insert 1.2 大批量插入数据二、主键优化 2.1 数据组织方式 2.2 页分裂 2.2.1 主键顺序插入效果 2.2.2 主键乱序插入效果 2.3 页合并 2.4 索引设计原则三、order by优化 3.1 执行以下两条语句（无索引） 3.2 创建索引…...

编程日记 2025/5/9 10:37:59

STM32F103C8T6单片机硬核原理篇：讨论GPIO的基本原理篇章1——只讨论我们的GPIO简单输入和输出

目录前言输出时的GPIO控制部分标准库是如何操作寄存器完成GPIO驱动的初始化的？ 问题1：如何掌握GPIO的编程细节——跟寄存器如何打交道问题2：哪些寄存器，去哪里找呢？ 问题三，寄存器的含义&#xff…...

编程日记 2025/5/9 10:25:01

FreeRTOS源码下载分享

FreeRTOS源码下载分享官网下载太慢了，分享下FreeRTOSv202411 FreeRTOSv202411.00.zip 链接: https://pan.baidu.com/s/1P4sVS5WroYEl0WTlPD7GXg 提取码: g6aq...

编程日记 2025/5/9 10:33:50

PyArrow 核心技术与应用：高效数据处理与跨生态集成实践

Apache Arrow 作为列式内存数据格式的行业标准，其 Python 接口 PyArrow 正在重塑数据科学生态。本文深入解析 PyArrow 的核心计算能力，涵盖统计函数、分组聚合、窗口操作及跨库集成，通过完整代码示例演示如何利用其高性能特性优化数据处理流程…...

编程日记 2025/5/9 9:24:08

机试题——PCB印刷电路板布线

题目描述在 PCB 印刷电路板设计中，器件之间的连线需要避免线路的阻抗值增大，而且器件之间还可能存在其他干扰源。为了简化问题，我们将电路板简化为一个 ( M * N ) 的矩阵，每个位置（单元格）的值表示其源干…...

编程日记 2025/5/9 10:11:47

数据化管理（一）---什么是数据化管理

目录一、什么是数据化管理1.1 “聪明”的销售人员1.2 数据化管理的概念1.3 数据化管理的意义1.4 数据化管理的四个层次1.4.1 业务指导管理1.4.2 营运指导管理1.4.3 经营策略管理1.4.4 战略规划管理 1.5 数据化管理流程图1.5.1 分析需求1.5.2 收集数据1.5.3 整理数据1.5.4 分析…...

编程日记 2025/5/9 10:09:10

Android 10.0 通过广播控制systemui状态栏动态显示和隐藏功能实现

1.前言在10.0的系统rom定制化开发中，在某些特定的产品开发中，需要通过接口来控制系统状态栏的显示和隐藏， 所以就需要了解systemui状态栏的显示构造过程，然后通过相关接口来显示和隐藏状态栏，接下来就来实现相关的功…...

编程日记 2025/4/3 6:50:24

Linux服务器安装MinerU

安装MinerU 为了确保项目的稳定性和可靠性，我们在开发过程中仅对特定的软硬件环境进行优化和测试。这样当用户在推荐的系统配置上部署和运行项目时，能够获得最佳的性能表现和最少的兼容性问题。这里我们以基础的 [[Linux服务器部署PaddleX实战教程]] 使…...

编程日记 2025/5/8 15:32:36

深挖 DeepSeek 隐藏玩法·智能炼金术2.0版本

前引：屏幕前的你还在AI智能搜索框这样搜索吗？“这道题怎么写”“苹果为什么红”“怎么不被发现翘课” ，。看到此篇文章的小伙伴们！请准备好你的思维魔杖，开启【霍格沃茨模式】，看我如何更新秘密的【知识炼金…...

编程日记 2025/5/9 9:31:31

Vite 内联 CSS 和 JS 的解决方案

使用 vite-plugin-singlefile（推荐） 这个插件专门用于将整个 Vite 应用打包成单个 HTML 文件，内联所有 JS 和 CSS。安装 pnpm i vite-plugin-singlefile -D配置 vite.config.js import { defineConfig } from vite import { viteSingleF…...

编程日记 2025/5/9 7:02:04

致敬生物信息学先驱：玛格丽特·戴霍夫（Margaret Dayhoff，1925-1983）

李升伟编译社论发布于：2025年3月11日《自然-计算科学》第五卷第187页（2025年） 在玛格丽特戴霍夫（Margaret Dayhoff，1925-1983）百年诞辰之际，我们聚焦这位先驱在生物信息学领域留下的不朽…...

编程日记 2025/5/9 8:05:04

Knife4j文档请求异常空指针

打开swagger文档报空指针异常 java.lang.NullPointerException: nullat springfox.documentation.oas.mappers.SchemaMapper.model(SchemaMapper.java:97)at springfox.documentation.oas.mappers.SchemaMapper.mapModel(SchemaMapper.java:85)at springfox.documentation.oas…...

编程日记 2025/5/5 22:06:10

笔记2——网络参考模型

一、OSI参考模型： 应用层： 报文给应用程序提供接口表示层： 进行数据格式的转换会话层： 在通讯双方之间建立、管理和终止会话传输层： 数据段；建立、维护、取消一次端到端的数据传输过程；控制…...

编程日记 2025/5/7 13:19:52

Spring AOP + Redis缓存设计实战：基于注解的优雅三防方案（击穿/穿透/雪崩）

文章目录摘要正文一、缓存设计的痛点与破局二、核心代码拆解：四层防御设计1. 注解驱动（ZywCacheable）2. 缓存击穿防护：双重检查锁3. 缓存穿透防护：空值标记4. 缓存雪崩防护：TTL随机算法三、生产环境最佳…...

编程日记 2025/5/6 13:30:43

洛谷题单3-P5720 【深基4.例4】一尺之棰-python-流程图重构

题目描述《庄子》中说到，“一尺之棰，日取其半，万世不竭”。第一天有一根长度为 a a a 的木棍，从第二天开始，每天都要将这根木棍锯掉一半（每次除 2 2 2，向下取整）。第几天的时候木…...

编程日记 2025/5/7 17:33:25

jdk21新特性详解使用总结

jdk21新特性详解总结 1.StringBuilder和StringBuffer新增了一个repeat方法 /*** Java 21的StringBuilder和StringBuffer新增了一个repeat方法*/public static void repeatStr(){var sbnew StringBuilder().repeat("*",10);System.out.println(sb);}运行结果如下&…...

编程日记 2025/5/7 5:22:13

解码 collections.Counter - 频率统计的利器

文章目录前言一、什么是 collections.Counter？二、基本用法：从创建到访问2.1 创建 Counter 对象2.2 访问计数三、核心功能：更新与排序3.1 更新计数3.2 获取常见元素四、高级用法：数学运算与转换4.1 数学运算4.2 类型转换五、实际应用：Counter 的威力5.1 词频统计5.2 在…...

编程日记 2025/4/26 22:14:42

Mysql基础笔记

# 1.SQL数据类型可以去这篇文章看看： 最全 SQL 字段类型（4种）、属性（6种）总结:https://blog.csdn.net/weixin_45654582/article/details/119157403 ### 一.整数类型 ### 二.小数类型(2种) 1、浮点型：…...

编程日记 2025/5/3 19:40:55

HttpClient-03.入门案例-发送POST方式请求

一.发送POST方式请求编写代码： 1.创建一个HttpClient对象 2.创建一个HttpGet请求 3.发送http的get请求并获得响应对象 4.通过发送GET请求获取的CloseableHttpResponse响应对象来获取状态码以及响应数据 package com.sky.test;import com.alibaba.fastjson.JS…...

编程日记 2025/4/30 19:34:50

Oracle数据库数据编程SQL＜3.6 PL/SQL 包(Package)＞

包是Oracle数据库中一种重要的PL/SQL程序结构，它将逻辑相关的变量、常量、游标、异常、过程和函数组织在一起，提供了更好的封装性和模块化。在大型项目中，可能有很多模块，而每一个模块又有自己的存过、函数等。而这些存过、函数默…...

编程日记 2025/5/5 8:06:42

每日一题---买卖股票的最好时机(一)、(二)

目录买卖股票的最好时机(一) 一、题目链接：买卖股票的最好时机(一)_牛客题霸_牛客网二、解题思路三、代码实现买卖股票的最好时机（二） 一、题目链接：买卖股票的最好时机(二)_牛客题霸_牛客网编辑二、解题思路 …...

编程日记 2025/5/6 21:26:11

XSS漏洞的分类解释和演示实验

XSS漏洞：跨站脚本攻击(cross site scripting)，为了不和CSS混淆而改名。攻击者网web插入恶意script代码，当用户浏览页面时，嵌入的代码会被执行。危害：盗取各类用户，强制发送电子邮件，网站挂马等…...

编程日记 2025/5/8 21:06:43

【Pandas】pandas DataFrame info

Pandas2.2 DataFrame Attributes and underlying data 方法描述DataFrame.index用于获取 DataFrame 的行索引DataFrame.columns用于获取 DataFrame 的列标签DataFrame.dtypes用于获取 DataFrame 中每一列的数据类型DataFrame.info([verbose, buf, max_cols, …])用于提供 Dat…...

编程日记 2025/5/8 5:01:56

JP1 Systemwalker 和 unirita的A-AUTO制品对比

以下是 JP1 SystemWalker（日立） 与 Unirita A-AUTO 的对比分析。两者均为日本企业开发的IT运维自动化工具，但在功能定位、技术架构和适用场景上存在显著差异： 1. 产品背景与市场定位维度JP1 SystemWalkerUnirita A-AUTO开发商日…...

编程日记 2025/4/30 20:41:06

探索鸿蒙操作系统：迎接万物互联新时代

# 探索鸿蒙操作系统：迎接万物互联新时代在科技飞速发展的当下，万物互联的时代浪潮正席卷而来。在这个全新的时代背景下，移动应用开发领域面临着前所未有的挑战，同时也迎来了诸多机遇。而鸿蒙操作系统（HarmonyOS&…...

编程日记 2025/5/1 17:10:30

NOIP2010提高组.引水入城

*前置题目 901. 滑雪 #include <iostream> #include <algorithm> #include <cstring>using namespace std;const int N 310, INF 0x3f3f3f3f; const int dx[4] {0, -1, 0, 1}, dy[4] {1, 0, -1, 0};int n, m, h[N][N]; int f[N][N]; int ans;int dfs(i…...

编程日记 2025/5/5 9:06:05