-
2022-01-14 16:33:47
【问题描述】 数学老师给小明出了一道等差数列求和的题目。但是粗心的小明忘记了一 部分的数列,只记得其中 N 个整数。 现在给出这 N 个整数,小明想知道包含这 N 个整数的最短的等差数列有 几项?
【输入格式】 输入的第一行包含一个整数 N。 第二行包含 N 个整数 A1, A2, · · · , AN。(注意 A1 ∼ AN 并不一定是按等差数 列中的顺序给出)
【输出格式】 输出一个整数表示答案。
【样例输入】
5
2 6 4 10 20
【样例输出】 10
【样例说明】 包含 2、6、4、10、20 的最短的等差数列是 2、4、6、8、10、12、14、16、 18、20。
【评测用例规模与约定】 对于所有评测用例,2 ≤ N ≤ 100000,0 ≤ Ai ≤ 109。
先上代码:
nums = input() target_nums = list(map(int,input().split(' '))) target_nums = list(sorted(target_nums)) list1 = [] for i in range(int(nums)-1): a = target_nums[i+1] - target_nums[i] list1.append(a) the_min = min(list1) if the_min == 0: print(nums) else: while True: for i in range(1,int(nums)): if (target_nums[i] - target_nums[0]) % the_min == 0: pass else: break else: break the_min = the_min - 1 c = target_nums[-1] - target_nums[0] print(int(c/the_min) + 1)
这个题的题意并不难理解,我们首先搞定输入的问题。
1,先输入要输入数的个数,用一个input()接收到nums中。
2,下边接收数,可以看出数是由空格隔开的,用map函数把input割开后的数变为int类型储存在表格中。
下面便是非常有必要的一个行动,就是把杂乱无章的数变为有序数组这里用了sorted()函数(当然用.sort()方法也可以)
最关键的一步:找最大公差值
怎样找呢?我们不难看出,这一堆数的最大公差一定小于等于大数减小数差值的最大值而且大于等于1特殊情况就是公差为0其为常数列,所以思路就有了。
我们先找到最大公差值最大的情况,对于测试用例来说这个数是2,这个题比较巧最大公差值就是2,但是对于一般情况下,如果2不是最大公差值(对一些数不成立)就要逐步缩小这个最大公差值直到找到一个合适的公差值。
另外一个关键点:如何确定一个数是不是这些数可能的公差?
那我们就拿其中最小的数,对于排序后的数列来说就是第0号位置上的值,让非0号位上的值去减去这个值利用取余符号%判断结果是不是0就知道了
更多相关内容 -
2018省赛第九届蓝桥杯真题C语言B组
2018-04-01 16:49:542018省赛第九届蓝桥杯真题C语言B组;2018省赛第九届蓝桥杯真题C语言B组;2018省赛第九届蓝桥杯真题C语言B组;2018省赛第九届蓝桥杯真题C语言B组;2018省赛第九届蓝桥杯真题C语言B组;2018省赛第九届蓝桥杯真题C语言B... -
2018年4月1日省赛第九届蓝桥杯真题C语言(B组)
2018-04-01 18:18:452018年4月1日年省赛第九届蓝桥杯真题Java(C组),新鲜出炉。 -
蓝桥杯C语言历年真题及相关资料
2019-03-02 11:29:10蓝桥杯C语言历年真题及相关资料,资料比较全面,还有相关的蓝桥杯资料,对准备蓝桥杯非常有帮助,加油! -
蓝桥杯c语言赛项历年真题
2019-03-27 23:55:59为推动软件开发技术的发展,促进软件专业技术人才培养,向软件行业输送具有创新能力和实践能力的高端人才,提升高校毕业生的就业竞争力,全面推动行业发展及人才培养进程,工业和信息化部人才交流中心特举办“全国... -
2018省赛第九届蓝桥杯真题C语言B第四题题解 测试次数
2018-04-02 15:03:542018第九届蓝桥杯C++省赛B组[最新题解汇总] 标题:测试次数 x星球的居民脾气不太好,但好在他们生气的时候唯一的异常举动是:摔手机。 各大厂商也就纷纷推出各种耐摔型手机。x星球的质监局规定了手机必须经过...标题:测试次数
x星球的居民脾气不太好,但好在他们生气的时候唯一的异常举动是:摔手机。
各大厂商也就纷纷推出各种耐摔型手机。x星球的质监局规定了手机必须经过耐摔测试,并且评定出一个耐摔指数来,之后才允许上市流通。
x星球有很多高耸入云的高塔,刚好可以用来做耐摔测试。塔的每一层高度都是一样的,与地球上稍有不同的是,他们的第一层不是地面,而是相当于我们的2楼。
如果手机从第7层扔下去没摔坏,但第8层摔坏了,则手机耐摔指数=7。
特别地,如果手机从第1层扔下去就坏了,则耐摔指数=0。
如果到了塔的最高层第n层扔没摔坏,则耐摔指数=n
为了减少测试次数,从每个厂家抽样3部手机参加测试。
某次测试的塔高为1000层,如果我们总是采用最佳策略,在最坏的运气下最多需要测试多少次才能确定手机的耐摔指数呢?
请填写这个最多测试次数。
注意:需要填写的是一个整数,不要填写任何多余内容。
思路:
100层楼扔两个鸡蛋的问题
两个软硬程度一样但未知的鸡蛋,它们有可能都在一楼就摔碎,也可能从一百层楼摔下来没事。
有座100层的建筑,要你用这两个鸡蛋确定哪一层是鸡蛋可以安全落下的最高位置。可以摔碎两个鸡蛋。
最少需要几次测试,才能得到摔碎鸡蛋的楼层?方案如何?
=================================================
对于这个问题,如果从编程角度而言,最简单的思路是用动态规划的思想来解决,不过本文不将其从编程角度分析,而是从数学角度对问题进行论述。
================================================
对这个问题,原始问题——【100层楼,最少需要几次测试,才能得到摔碎鸡蛋的楼层】,直接考虑不容易考虑,但是,如果将这个问题进行一种等价的转换,这个问题将会变得非常容易解答。个人认为,这个转换是解决这个问题的核心,这个转换是:
转换问题——【两个鸡蛋,进行k次测试,最多可以测试几层楼】
如果大家能想到将“原始问题”变为“转换问题”,这个问题个人认为已经解决一半了,转换后,这个问题豁然开朗,思路全开。
现在我们以“转换问题”为模板进行考虑,有两个鸡蛋,第一个鸡蛋如果破碎,第二个鸡蛋就必须只能一层一层的测试了,而且,我们要求进行k次测试就将摔碎鸡蛋的楼层必须找到.
=====================================================
考虑第一次测试。第一次测试的时候,第一个鸡蛋不能放置的楼层太高了,否则,如果第一个鸡蛋破碎,第二个鸡蛋可能不能在k次测试后得到结果。但是也不能放置的矮了,因为如果放置的矮了,第一个鸡蛋破碎了还好说,如果没破,我们浪费了一次测试机会,也不能说是完全浪费了,不过至少是让效用没有最大化。所以,第一次测试的时候必须让第一个鸡蛋放置的不高不矮。
不高不矮是多高?高到如果第一个鸡蛋破碎后第二个鸡蛋刚好能完成k次测试得到结果这个目标。由此可知,第一次测试所在的楼层高度为k,如果第一次测试第一枚鸡蛋破碎,则剩下k-1层楼,一层一层的试,k次一定能完成目标。
如果第一次测试,第一枚鸡蛋没有破碎,则我们现在只有k-1次测试机会了,而且直到了k楼及其以下都是安全的了。我们消耗了一次测试机会,但是一次就测试了k层楼。
然后只有k-1次机会了,第二次测试,我们可以在k层的基础上再增加k-1层了,注意,这个时候由于我们只有k-1次机会,所以这次只能再增加k-1层,以保证测试的时候第一枚鸡蛋破碎的情况下仍然能完成任务。
于是,重复上述过程,直到最后一次机会,我们总共测试的楼层数为:
然后,再回到“原始问题”,100层楼,如果需要k次测试才能测试完成,则必须有
则可以得到,k≥14
也就是需要14次测试才能得到结果,而且这个过程也将测试方案一并得出来,就是第一次在14楼测试,如果第一枚蛋碎,则剩余13次机会,13层未知楼层,恰好,第二次在14+13=27楼测试,如此。
如果不是100层,而是N层,需要的测试次数为k,则有
=========================================================
然后,这个问题这个时候还可以扩展了,如果我们有三个鸡蛋,有k次机会,我们最大可以测试多少层楼?
思路同前面一样,第一次测试,不能太高也能太矮,必须恰到好处,也就是第一枚鸡蛋如果破碎,剩余k-1次机会能将剩余楼层给测试完。
由上面结论,k-1次机会最多可以测试k(k-1)/2层楼,所以第一次在k(k-1)/2+1层楼,第一次如果第一枚鸡蛋不碎,第二次在此基础上增加(k-1)(k-2)/2+1层楼,于是,三个鸡蛋k次机会总共测试楼层数为
至于四个鸡蛋,五个鸡蛋,以至于M个鸡蛋,可以以此类推,方法同上。此处原理讲通,就不推导了
答案:19
-
2018年蓝桥杯 C语言B组试题
2018-04-02 16:58:272018-04-01 2018年蓝桥杯个人赛-省赛 C语言B组全部试题(1-10) -
2017年蓝桥杯省赛C语言B组真题
2017-04-08 16:04:412017年蓝桥杯省赛C语言B组真题 -
第九届蓝桥杯真题C/C++(C组)
2018-04-01 14:42:59这是2018年省赛第九届蓝桥杯真题C/C++(C组),新鲜出炉。。 -
蓝桥杯C语言历年真题与答案.zip
2013-09-20 11:47:05蓝桥杯C语言 真题与答案 可以练习C语言的算法 和思想 -
蓝桥杯试题C语言答案..doc
2021-05-19 17:23:40蓝桥杯试题C语言答案.1、A、B、C、D、E五名学生有可能参加计算机竞赛,根据下列条件判断哪些人参加了竞赛:(1)A参加时,B也参加;(2)B和C只有一个人参加;(3)C和D或者都参加,或者都不参加;(4)D和...蓝桥杯试题C语言答案.
1、A、B、C、D、E五名学生有可能参加计算机竞赛,根据下列条件判断哪些
人参加了竞赛:
(1)A参加时,B也参加;
(2)B和C只有一个人参加;
(3)C和D或者都参加,或者都不参加;
(4)D和E中至少有一个人参加;
(5)如果E参加,那么A和D也都参加。
00110 c、d
#include
int main()
{
int a,b,c,d,e; /*0表示不参加, 1表示参加.*/
for(a=0;a<2;a++)
for(b=0;b<2;b++)
for(c=0;c<2;c++)
for(d=0;d<2;d++)
for(e=0;e<2;e++)
{
if(a&&!b) continue;
if(b&&c||!b&&!c) continue;
if(c&&!d||!c&&d) continue;
if(!d&&!e) continue;
if(e&&(!a||!d))continue;
printf("%d%d%d%d%d",a,b,c,d,e);
}
return 0;
}
2、某侦察队接到一项紧急任务,要求在A、B、C、D、E、F六个队员中尽可能多地挑若干人,但有以下限制条件:
1)A和B两人中至少去一人;
2)A和D不能一起去;
3)A、E和F三人中要派两人去;
4)B和C都去或都不去;
5)C和D两人中去一个;
6)若D不去,则E也不去。
试编写一个程序,输出问应当让哪几个人去?
#include
int main()
{
int a,b,c,d,e,f;
for(a=1;a>=0;a--)
for(b=1;b>=0;b--)/*1:去 0:不去*/
for(c=1;c>=0;c--)
for(d=1;d>=0;d--)
for(e=1;e>=0;e--)
for(f=1;f>=0;f--)
{
if(a+b>=1&&a+d!=2&&a+e+f==2&&b==c&&c+d==1&&(d+e==0||d==1))
printf("a=%d,b=%d,c=%d,d=%d,e=%d,f=%d",a,b,c,d,e,f);
}
return 0;
}
3、警察局抓住了A、B、C、D四名盗窃嫌疑犯,其中只有一人是小偷。在审问时,A说:“我不是小偷”;
B说:“C是小偷”;C说:“小偷肯定是D”;D说:“C在冤枉好人”。
现在已经知道这四人中有三人说的是真话,一人说的是假话。请问到底谁是小偷?
提示:设4个变量a,b,c,d,为0时表示不是小偷,为1时表示是小偷,用四重循环穷举a,b,c,d可能的取值的组合,
对每一种组合判断其是否符合题目中给出的约束。最后结论:C是小偷。
#include
int main()
{
int a,b,c,d;
for(a=1;a>=0;a--)
for(b=1;b>=0;b--)/*1:是小偷 0:不是小偷*/
for(c=1;c>=0;c--)
for(d=1;d>=0;d--)
{
if((a==0)+(c==1)+(d==1)+(d==0)==3&&a+b+c+d==1)/*4人的说法中有3个真的,且只有一个小偷*/
printf("%d %d %d %d",a,d,c,d);
}
return 0;
}
有限五位数
个位数为6且能被3整除的五位数有多少个?
#include
int main()
{
long int i;
int sum=0;
for(i=1000;i<=9999;i++)
{
if((i*10+6)%3==0)
{
sum++;
}
}
printf("%d",sum);
return 0;
}
5、标题:错误票据
某涉密单位下发了某种票据,并要在年终全部收回。
每张票据有唯一的ID号。全年所有票据的ID号是连续的,但ID的开始数码是随机选定的。
因为工作人员疏忽,在录入ID号的时候发生了一处错误,造成了某个ID断号,另外一个ID重号。
你的任务是通过编程,找出断号的ID和重号的ID。 假设断号不可能发生在最大和最小号。
要求程序首先输入一个整数N(N<100)表示后面数据行数。 接着读入N行数据。
-
蓝桥杯真题 C语言 高斯日记
2020-03-01 15:20:27题目 题目标题:高斯日记 大数学家高斯有个好习惯:无论如何都要记日记。 他的日记有个与众不同的地方,他从不注明年月日,而是用一个整数代替,比如: 4210 后来人们知道,那个整数就是日期,它表示那一天是高斯出生后...题目
题目标题:高斯日记
大数学家高斯有个好习惯:无论如何都要记日记。
他的日记有个与众不同的地方,他从不注明年月日,而是用一个整数代替,比如: 4210
后来人们知道,那个整数就是日期,它表示那一天是高斯出生后的第几天。这或许也是个好习惯,它时时刻刻提醒着主人:日子又过去一天,还有多少时光可以用于浪费呢?
高斯出生于: 1777年4月30日。
在高斯发现的一个重要定理的日记上标注着: 5343, 因此可算出那天是: 1791年12月15日。
高斯获得博士学位的那天日记上标着: 8113
请你算出高斯获得博士学位的年月日。
提交答案的格式是: yyyy-mm-dd,例如: 1980-03-21
请严格按照格式,通过浏览器提交答案。
注意:只提交这个日期,不要写其它附加内容,比如:说明性的文字。注意点
出生日算第一天,所以5343天循环是写为5342,8113写为8112
加Continue是为了提高效率。#include<stdio.h> bool isrunyear(int y){ return (y%4 == 0 && y%100 != 0 ) || (y%400==0); } int main(){ //出生日期 int y=1777; int m=4; int d=30; //模拟翻日历 for(int i=0;i<8112;i++){ d++; //年的最后一天 if(m==12 && d==32){ y++; m=1; d=1; continue; } if((m==1 || m==3 || m==5 ||m==7||m==8||m==10)&& d==32){ //判断1357810月的最后一天 31天的 m++; d=1; continue; } if((m==4 || m==6 || m==9 ||m==11)&& d==31){ //判断4 6 9 11月份的最后一天 30天的 m++; d=1; continue; } if(m==2&& isrunyear(y) && d==30 ){ //判断闰年2月 m++; d=1; continue; } if(m==2&& !isrunyear(y) && d==29 ){ m++; d=1; continue; } } printf("%d-%d-%d",y,m,d) ; return 0; }
-
蓝桥杯真题系列:19年C语言B组试题 年号字串
2022-01-11 14:14:08先上原题: 【问题描述】 小明用字母 A 对应数字 1,B 对应 2,以此类推,用 Z 对应 26。对于 27 以上的数字,小明用两位或更长位的字符串来对应,例如 AA 对应 27,AB 对 应 28,AZ 对应 52,LQ 对应 329。... -
2018省赛第九届蓝桥杯真题C语言B第三题题解 乘积尾零
2021-05-19 15:28:10标题:乘积尾零如下的10行数据,每行有10个整数,请你求出它们的乘积的末尾有多少个零?5650 4542 3554 473 946 4114 3871 9073 90 43292758 7949 6113 5659 5245 7432 3051 4434 6704 35949937 1173 6866 3397 4759... -
2018省赛第九届蓝桥杯真题C语言B组第十题题解 乘积最大
2021-05-19 13:39:53标题:乘积最大给定N个整数A1, A2, ... AN。请你从中选出K个数,使其乘积最大。请你求出最大的乘积,由于乘积可能超出整型范围,你只需输出乘积除以1000000009的余数。注意,如果X<0, 我们定义X除以1000000009的... -
2018省赛第九届蓝桥杯真题C语言B组第五题题解 快速排序
2018-04-02 15:07:252018第九届蓝桥杯C++省赛B组[最新题解汇总]标题:快速排序。 以下代码可以从数组a[]中找出第k小的元素。它使用了类似快速排序中的分治算法,期望时间复杂度是O(N)的。请仔细阅读分析源码,填写划线部分缺失的内容。... -
2018省赛第九届蓝桥杯真题C语言B组第六题题解 递增三元组
2021-05-22 13:22:46标题:递增三元组给定三个整数数组A = [A1, A2, ... AN],B = [B1, B2, ... BN],C = [C1, C2, ...... 1 <= i, j, k <= N2.... Bj < Ck【输入格式】第一行包含一个整数N。第二行包含N个整数A1, A2, ...... -
蓝桥杯真题系列:第十一届蓝桥杯C语言B组集锦
2022-01-24 11:28:38第一题:门牌制作 解答:作为填空题第一题,难度比较低,暴力查2即可。 cnt = 0 for i in range(1,2021): for j in str(i): if j == '2': cnt = cnt + 1 ...题解:这个题我想到的办法就是暴力解决,生成1到2020的... -
【蓝桥杯真题】2021年蓝桥杯省赛B组题目解析+代码(C/C++)
2021-12-18 14:15:082021年蓝桥杯省赛B组题目解析,附C/C++代码 -
2018 蓝桥杯 省赛 B组 原题 C语言B组 第3题 第九届蓝桥杯真题 +答案+解析
2021-05-19 11:44:00标题:乘积尾零如下的10行数据,每行有10个整数,请你求出它们的乘积的末尾有多少个零?5650 4542 3554 473 946 4114 3871 9073 90 43292758 7949 6113 5659 5245 7432 3051 4434 6704 35949937 1173 6866 3397 4759... -
第十一届蓝桥杯C语言B组.zip
2021-03-16 00:42:21第十一届蓝桥杯C语言B组.zip -
2018省赛第九届蓝桥杯真题C语言B组第八题题解 日志统计
2018-04-01 19:46:342018第九届蓝桥杯C++省赛B组[最新题解汇总]标题:日志统计小明维护着一个程序员论坛。现在他收集了一份"点赞"日志,日志共有N行。其中每一行的格式是:ts id 表示在ts时刻编号id的帖子收到一个"赞&... -
蓝桥杯试题C语言答案.doc
2021-05-19 18:15:28.Word 文档1、A、B、C、D、E五名学生有可能参加计算机竞赛,根据下列条件判断哪些人参加了竞赛:(1)A参加时,B也参加;(2)B和C只有一个人参加;(3)C和D或者都参加,或者都不参加;... -
2020年7月B组C++蓝桥杯真题试水
2021-05-21 10:43:01哇!刚刚突然发现我的那篇扩展欧几里得达到了500+的阅读量,开森森~ 看起来努力就是有回报的嘛!用心写的文章和不用心写的文章相信广大程序员萌都一眼看得出来撒~快乐!你们的关注和点赞是我最大的动力嗷!... -
2018蓝桥杯C语言b组国赛真题
2018-05-29 09:42:031.... x星球的钞票的面额只有:100元,5元,2元,1元,共4种。...他找到了参加蓝桥杯的你来帮他计算这个答案。 由于这个答案可能很大,你只需要回答这个答案对1000000007(十亿零七)取模后的结果。 注意:地基... -
内含答案的 -- 2013蓝桥杯C语言本科组B.doc
2021-05-22 15:23:362013蓝桥杯C语言本科组B1、题目标题: 高斯日记(满分4分)大数学家高斯有个好习惯:无论如何都要记日记。他的日记有个与众不同的地方,他从不注明年月日,而是用一个整数代替,比如:4210后来人们知道,那个整数就是... -
第十届蓝桥杯真题编程题1-7解析(高级组).pdf
2021-05-23 09:35:09scratch 少儿编程第十届蓝桥杯真题 7大家好 ~今天我们来讲解 scratch 蓝桥杯第十届编程大题的第七道题。同样,这道题也是非常有难度的一道题。一起来看一下吧解析:女孩的程序1、在进行编程之前,我们需要把女孩的... -
2018省赛第九届蓝桥杯真题C语言B组详解第一题
2018-04-01 19:10:032018第九届蓝桥杯C++省赛B组[最新题解汇总]标题:第几天2000年的1月1日,是那一年的第1天。那么,2000年的5月4日,是那一年的第几天?注意:需要提交的是一个整数,不要填写任何多余内容。思路:签到手算即可.答案:... -
2018省赛第九届蓝桥杯真题C语言B组第九题题解 全球变暖
2018-04-01 20:12:392018第九届蓝桥杯C++省赛B组[最新题解汇总]标题:全球变暖你有一张某海域NxN像素的照片,"."表示海洋、"#"表示陆地,如下所示:........##.....##........##...####....###........其中"...