蓝桥杯官网题目:2.包子凑数

这篇具有很好参考价值的文章主要介绍了蓝桥杯官网题目:2.包子凑数。希望对大家有所帮助。如果存在错误或未考虑完全的地方,请大家不吝赐教,您也可以点击"举报违法"按钮提交疑问。

蓝桥杯官网题目:2.包子凑数,蓝桥杯,算法

链接:题目点这里

首先要知道一个数学定理裴蜀定理,还有完全背包的基本运用,这里只介绍前者

也可以看一下我的个人理解,我是第一次听说这个定理,理解可能有误差。

  • 假设gcd(a,b)=d,gcd是最大公约数的意思。即a,b的最大公约数是d
  • ax+by=m(x,y是任意整数,可正可负)
  • 对于所有的m,一定会被d整除,即m%d=0

可以尝试画出ax+by=z的三维立体图,很显然是一个空间平面。
蓝桥杯官网题目:2.包子凑数,蓝桥杯,算法

z是一个未知数,它的取值有无数个,如果在三维坐标系中看,那么是所有的z(z可以被gcd(a,b)整除)。
换句话说,ax+by表示的数的集合是{实数中所有的可以被gcd(a,b)整除的数}。

  • 以下考虑a,b互质

  • a,b如果是互质的,那么
    g c d ( a , b ) = 1 gcd(a,b)=1 gcdab=1

  • 那么ax+by可以构成所有的整数:

    {ax+by | x ∈ x\in xN, y ∈ y\in yN, a x + b y ∈ ax+by\in ax+byN}

  • 当x,y都是正整数的时候,包括0。ax+by不能表示的最小数是:
    ( a − 1 ) ∗ ( b − 1 ) − 1 (a-1)*(b-1)-1 (a1)(b1)1

  • 也就是说,ax+by可以表示大于(a-1)*(b-1)-1的所有正整数

回到题目
看懂了上面的数学基础应该这个题就比较清晰了。

那我就直接上代码了,不懂的评论区留言

#include<iostream>
#include<algorithm>
using namespace std;
const int N = 1e4+1;  //只需要比ax+by的最小值大1就可以了。
const int M = 110;
long long int dp[N];  //dp[i]=j表示取i种包子的方案数是j
//dp[i]=dp[i-a[1]]+dp[i-a[2]]+dp[i-a[3]]+....+dp[i-a[n]]; 
//即,取i种包子的方案数等于取[i-a[1]]包子的方案数+[i-a[2]]包子的方案数+...+[i-a[n]]包子的方案数
int a[M];
int sum = 0;

int gcd(int a, int b)  //辗转相除法
{
    if (a < b)swap(a, b);  //大的数是被除数
    int r = a % b;   //余数
    if (r == 0)return b;
    else
    {
        a = b;
        b = r;
    }
    return gcd(a, b);
}

int main()
{
    int n;
    cin >> n;
    int k;
    for (int i = 1; i <= n; i++)  //找最大公约数
    {
        cin >> a[i];
        if (i == 1)k = a[i];
        else
            k = gcd(k, a[i]);
    }

    if (k != 1)cout << "INF";   //如果最大公约数不是1,那么就会有无穷个数取不到。

    else  //说明最大公约数是1,那么ax+by的值是所有1的倍数,ax+by此时表示整数集(所有整数)
    {
        sort(a + 1, a + n + 1);
        dp[0] = 1;  //取0种包子的方案数是1,即不取,这个必须要有,是很重要的边界初始化
        for (int i = 1; i <= N; i++)  //枚举包子的个数
        {
            for (int j = 1; j <= n; j++)  //然后更新当前包子个数的方案数
            {
                if (i - a[j] < 0)
                    break;
                dp[i] += dp[i - a[j]];
            }
            if (dp[i] == 0)  //退出内嵌for循环判断i个包子的方案数是否是0,如果是,说明这个数不能被构成
                sum++;
        }
        cout << sum << endl;
    }
    return 0;
}

对裴蜀定理有兴趣的可以关注我这篇博客,我会从cf和leetcode等网站更新相关内容,将会以链接形式帖在本篇下面文章来源地址https://www.toymoban.com/news/detail-812352.html

到了这里,关于蓝桥杯官网题目:2.包子凑数的文章就介绍完了。如果您还想了解更多内容,请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章,希望大家以后多多支持TOY模板网!

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处: 如若内容造成侵权/违法违规/事实不符,请点击违法举报进行投诉反馈,一经查实,立即删除!

领支付宝红包 赞助服务器费用

相关文章

  • 蓝桥杯官网填空题(距离和)

    题目描述 本题为填空题,只需要算出结果后,在代码中使用输出语句将所填结果输出即可。 两个字母之间的距离定义为它们在字母表中位置的距离。例如 A 和 C 的距离为 2,L 和 Q 的距离为 5。 对于一个字符串,我们称字符串中两两字符之间的距离之和为字符串的内部

    2024年02月09日
    浏览(47)
  • 蓝桥杯官网练习题(旋转)

    题目描述 图片旋转是对图片最简单的处理方式之一,在本题中,你需要对图片顺时针旋转 90 度。 我们用一个 n×m 的二维数组来表示一个图片,例如下面给出一个 3×4 的 图片的例子: 1 3 5 7 9 8 7 6 3 5 9 7 这个图片顺时针旋转 90 度后的图片如下: 3 9 1 5 8 3 9 7 5 7 6 7 给定初始图

    2024年02月09日
    浏览(41)
  • 蓝桥杯官网填空题(数位和)

    题目描述 本题为填空题,只需要算出结果后,在代码中使用输出语句将所填结果输出即可。 数学家高斯很小的时候就天分过人。一次老师指定的算数题目是:1+2+...+100。 高斯立即做出答案:5050! 这次你的任务是类似的。但并非是把一个个的数字加起来,而是对该数字的每一

    2024年02月09日
    浏览(52)
  • 蓝桥杯官网填空题(方格计数)

    题目描述 本题为填空题,只需要算出结果后,在代码中使用输出语句将所填结果输出即可。 如下图所示,在二维平面上有无数个  1×1 的小方格。 我们以某个小方格的一个顶点为圆心画一个半径为  50000 的圆。 你能计算出这个圆里有多少个完整的小方格吗? 运行限制 最大

    2024年02月05日
    浏览(52)
  • 蓝桥杯官网填空题(生成树)

    问题描述 下面是一个 8 个结点的无向图的邻接矩阵表示,其中第 i 行第 j 列表示结点 i 到结点 j 的边长度。当 长度为 0 时表示不存在边。 请问,这个图的最小生成树大小的多少? 答案提交 这是一道结果填空的题,你只需要算出结果后提交即可。本题的结果为一个整数

    2024年02月09日
    浏览(39)
  • 包子凑数【动态规划;数学】

    小明几乎每天早晨都会在一家包子铺吃早餐。他发现这家包子铺有 N 种蒸笼,其中第 i 种蒸笼恰好能放 A i个包子。每种蒸笼都有非常多笼,可以认为是无限笼。 每当有顾客想买 X 个包子,卖包子的大叔就会迅速选出若干笼包子来,使得这若干笼中恰好一共有 X 个包子。比如

    2024年02月08日
    浏览(31)
  • 蓝桥杯官网练习题(移动距离)

    题目描述 X 星球居民小区的楼房全是一样的,并且按矩阵样式排列。其楼房的编号为 1,2,3,··· 当排满一行时,从下一行相邻的楼往反方向排号。 比如:当小区排号宽度为 6 时,开始情形如下: 1    2     3    4   5   6 12  11  10  9    8   7 13  14  15  ··· 我们的问题是

    2024年02月05日
    浏览(69)
  • 蓝桥杯官网填空题(骰子迷题)

    题目描述 本题为填空题,只需要算出结果后,在代码中使用输出语句将所填结果输出即可。 小明参加了少年宫的一项趣味活动:每个小朋友发给一个空白的骰子(它的  6 个面是空白的,没有数字),要小朋友自己设计每个面写哪个数字。但有如下要求: 每个面只能填写 

    2024年01月23日
    浏览(56)
  • 蓝桥杯官网填空题(海盗与金币)

    题目描述 本题为填空题,只需要算出结果后,在代码中使用输出语句将所填结果输出即可。 12名海盗在一个小岛上发现了大量的金币,后统计一共有将近5万枚。 登上小岛是在夜里,天气又不好。由于各种原因,有的海盗偷拿了很多,有的拿了很少。 后来为了“均贫富”,头

    2024年01月22日
    浏览(53)
  • 蓝桥杯官网填空题(黄金连分数)

    题目描述 本题为填空题,只需要算出结果后,在代码中使用输出语句将所填结果输出即可。 黄金分割数  0.61803... 是个无理数,这个常数十分重要,在许多工程问题中会出现。有时需要把这个数字求得很精确。 对于某些精密工程,常数的精度很重要。也许你听说过哈勃太空

    2024年02月05日
    浏览(85)

觉得文章有用就打赏一下文章作者

支付宝扫一扫打赏

博客赞助

微信扫一扫打赏

请作者喝杯咖啡吧~博客赞助

支付宝扫一扫领取红包,优惠每天领

二维码1

领取红包

二维码2

领红包