蓝桥杯17年省赛原题佛系题解

禁止摸鱼!


T1 购物单

小明刚刚找到工作,老板人很好,只是老板夫人很爱购物。老板忙的时候经常让小明帮忙到商场代为购物。小明很厌烦,但又不好推辞。

这不,XX大促销又来了!老板夫人开出了长长的购物单,都是有打折优惠的。
小明也有个怪癖,不到万不得已,从不刷卡,直接现金搞定。
现在小明很心烦,请你帮他计算一下,需要从取款机上取多少现金,才能搞定这次购物。

取款机只能提供100元面额的纸币。小明想尽可能少取些现金,够用就行了。
你的任务是计算出,小明最少需要取多少现金。

以下是让人头疼的购物单,为了保护隐私,物品名称被隐藏了。



180.90 88折 10.25 65折
56.14 9折 104.65 9折
100.30 88折 297.15 半价
26.75 65折 130.62 半价
240.28 58折 270.62 8折
115.87 88折 247.34 95折
73.21 9折 101.00 半价
79.54 半价 278.44 7折
199.26 半价 12.97 9折
166.30 78折 125.50 58折
84.98 9折 113.35 68折
166.57 半价 42.56 9折
81.90 95折 131.78 8折
255.89 78折 109.17 9折
146.69 68折 139.33 65折
141.16 78折 154.74 8折
59.42 8折 85.44 68折
293.70 88折 261.79 65折
11.30 88折 268.27 58折
128.29 88折 251.03 8折
208.39 75折 128.88 75折
62.06 9折 225.87 75折
12.89 75折 34.28 75折
62.16 58折 129.12 半价
218.37 半价 289.69 8折

需要说明的是,88折指的是按标价的88%计算,而8折是按80%计算,余者类推。
特别地,半价是按50%计算。

请提交小明要从取款机上提取的金额,单位是元。
答案是一个整数,类似4300的样子,结尾必然是00,不要填写任何多余的内容。

根据所得数据计算出要花的钱,然后上取整百就可以了。

什么叫上取整百?比如说最后结果是114.514,就要取200,最后结果如果是1919.810,最后要取2000。

插播一句,我认为这题用Excel做比用C++做方便。。。

需要花费5136.86元,那么题目答案就是5200。

tips:数据可以先用word进行处理,把前面的星号都删掉,然后把xx折的折字都替换掉,半价替换成5,在word里面对这些数据插入表格,复制表格进excel,就可以啦(滑稽)

T2 等差素数列

2,3,5,7,11,13,….是素数序列。
类似:7,37,67,97,127,157 这样完全由素数组成的等差数列,叫等差素数数列。
上边的数列公差为30,长度为6。

2004年,格林与华人陶哲轩合作证明了:存在任意长度的素数等差数列。
这是数论领域一项惊人的成果!

有这一理论为基础,请你借助手中的计算机,满怀信心地搜索:

长度为10的等差素数列,其公差最小值是多少?

注意:需要提交的是一个整数,不要填写任何多余的内容和说明文字。

这可怎么搜呢?我寻思先打个几万的素数表,然后二分公差(从1到10000左右吧),根据二分到的公差去尝试构造素数表。如果构造不成功则需要加大公差….

什么花里胡哨的的玩意。。。直接暴力枚举。素数表该打还是要打,完事开一个双重循环,第一层枚举公差d,第二层枚举起始素数,然后去判断从第一位到第十位是不是都是素数,是的话就可以了。

为什么要第一层枚举公差d?因为这样可以保证公差最小。

这是一个提交答案题,爆枚挂机即可,时间复杂度倒是没有太高要求。

T3 承压计算

X星球的高科技实验室中整齐地堆放着某批珍贵金属原料。

每块金属原料的外形、尺寸完全一致,但重量不同。
金属材料被严格地堆放成金字塔形。

                         7
5 8
7 8 8
9 2 7 2
8 1 4 9 1
8 1 8 8 4 1
7 9 6 1 4 5 4
5 6 5 5 6 9 5 6
5 5 4 7 9 3 5 5 1
7 5 7 9 7 4 7 3 3 1
4 6 4 5 5 8 8 3 2 4 3
1 1 3 3 1 6 6 5 5 4 4 2
9 9 9 2 1 9 1 9 2 9 5 7 9
4 3 3 7 7 9 3 6 1 3 8 8 3 7
3 6 8 1 5 3 9 5 8 3 8 1 8 3 3
8 3 2 3 3 5 5 8 5 4 2 8 6 7 6 9
8 1 8 1 8 4 6 2 2 1 7 9 4 2 3 3 4
2 8 4 2 2 9 9 2 8 3 4 9 6 3 9 4 6 9
7 9 7 4 9 7 6 6 2 8 9 4 1 8 1 7 2 1 6
9 2 8 6 4 2 7 9 5 4 1 2 5 1 7 3 9 8 3 3
5 2 1 6 7 9 3 2 8 9 5 5 6 6 6 2 1 8 7 9 9
6 7 1 8 8 7 5 3 6 5 4 7 3 4 6 7 8 1 3 2 7 4
2 2 6 3 5 3 4 9 2 4 5 7 6 6 3 2 7 2 4 8 5 5 4
7 4 4 5 8 3 3 8 1 8 6 3 2 1 6 2 6 4 6 3 8 2 9 6
1 2 4 1 3 3 5 3 4 9 6 3 8 6 5 9 1 5 3 2 6 8 8 5 3
2 2 7 9 3 3 2 8 6 9 8 4 4 9 5 8 2 6 3 4 8 4 9 3 8 8

7 7 7 9 7 5 2 7 9 2 5 1 9 2 6 5 3 9 3 5 7 3 5 4 2 8 9
7 7 6 6 8 7 5 5 8 2 4 7 7 4 7 2 6 9 2 1 8 2 9 8 5 7 3 6
5 9 4 5 5 7 5 5 6 3 5 3 9 5 8 9 5 4 1 2 6 1 4 3 5 3 2 4 1
X X X X X X X X X X X X X X X X X X X X X X X X X X X X X X


其中的数字代表金属块的重量(计量单位较大)。
最下一层的X代表30台极高精度的电子秤。

假设每块原料的重量都十分精确地平均落在下方的两个金属块上,
最后,所有的金属块的重量都严格精确地平分落在最底层的电子秤上。
电子秤的计量单位很小,所以显示的数字很大。

工作人员发现,其中读数最小的电子秤的示数为:2086458231

请你推算出:读数最大的电子秤的示数为多少?

注意:需要提交的是一个整数,不要填写任何多余的内容。

待填坑

T4 方格分割

6x6的方格,沿着格子的边线剪开成两部分。
要求这两部分的形状完全相同。

如图:p1.png, p2.png, p3.png 就是可行的分割法。

试计算:
包括这3种分法在内,一共有多少种不同的分割方法。
注意:旋转对称的属于同一种分割法。

请提交该整数,不要填写任何多余的内容或说明文字。

待填坑

T5 取数位

求1个整数的第k位数字有很多种方法。
以下的方法就是一种。

// 求x用10进制表示时的数位长度

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
int len(int x){
if(x<10) return 1;
return len(x/10)+1;
}

// 取x的第k位数字
int f(int x, int k){
if(len(x)-k==0) return x%10;
return _; //填空
}

int main()
{
int x = 23574;
printf(“%d\n”, f(x,3));
return 0;
}

对于题目中的测试数据,应该打印5。

请仔细分析源码,并补充划线部分所缺少的代码。

注意:只提交缺失的代码,不要填写任何已有内容或说明性的文字。

这个题还是比较简单的。我们可以看出len函数用来求一个十进制数的位数,使用f函数去求第k位数。f函数给我们提供了一个特判,当len(x)与k相等,也就是数字位数与取的这一位数字相同时(换句话说,这时候取的是最后一位,因为题目中len(x)是5,k要和它相等的话也是5),直接return了x%10,它就是数字的最后一位。

如果需要中间的某位,我们需要对数字先进行除法处理,然后再对10取模。其实就是把非特殊情况去转化成特殊情况。一般来说非特殊情况是k要比len(x)小的,可以求出差值,不难发现这个差值其实就是我们要除去的位数。比如k是3,我们需要的是x这里面“23574”里面的数字5,这里len(x)是5,k是3,二者差值为2,如果把“23574”后面的“74”去掉,对235进行%10处理,就是答案5了。

但通过代码分析,这里用直接除法的方法似乎不太可行,因为没有提供pow函数。正解是递归,可能有点难想。它的结构和上面的len函数其实很像。

答案是f(x/10,k)

T6 最大公共子串

最大公共子串长度问题就是:
求两个串的所有子串中能够匹配上的最大长度是多少。

比如:”abcdkkk” 和 “baabcdadabc”,
可以找到的最长的公共子串是”abcd”,所以最大公共子串长度为4。

下面的程序是采用矩阵法进行求解的,这对串的规模不大的情况还是比较有效的解法。

请分析该解法的思路,并补全划线部分缺失的代码。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
#include <stdio.h>
#include <string.h>

#define N 256
int f(const char s1, const char s2)
{
int a[N][N];
int len1 = strlen(s1);
int len2 = strlen(s2);
int i,j;

memset(a,0,sizeof(int)NN);
int max = 0;
for(i=1; i<=len1; i++){
for(j=1; j<=len2; j++){
if(s1[i-1]==s2[j-1]) {
a[i][j] = __; //填空
if(a[i][j] > max) max = a[i][j];
}
}
}

return max;
}

int main()
{
printf(“%d\n”, f(“abcdkkk”, “baabcdadabc”));
return 0;
}

注意:只提交缺少的代码,不要提交已有的代码和符号。也不要提交说明性文字。

这个题其实难度不小。虽然答案很简洁但是真的不太好想。通过前后代码联系倒是可以看出来a[i][j]可能是要进行叠加计算的,因为后面有和max比较的操作,不难想到a[i][j]应该是在统计答案。

我们尝试一下从循环寻找突破口。前面是从1到len1,len2的双重循环,然后是if判断了s1[i-1]和s2[j-1]。我们知道,C字符串(char*那种的)下标是从0开始,你不感觉这个从1循环很可疑吗?到了后面判断s1和s2后用的就是i-1和j-1了,似乎在循环上刻意的避免了下标成-1的情况。

这是不是可以说明,a[i][j]会有牵扯到前驱的可能?存在即合理,如果它不会牵扯到前面的下标,那之前的循环直接从0写到len-1不好吗?这样疑点就基本说得通了。

好,我们顺着找前驱的思路去想。对于这两个串,abcdkkk和baabcdadabc,按照这个算法,当i为1,j为2的时候会进入的if后面的空缺,此时会让a[i][j]记录一个值,根据之前的推理,它很可能是一个与前件有关系的递推式。而根据后面的代码判断,此时的a[i][j]已经算是答案了,我们看一下,现在的串是怎样的?第一个串只找到了a,第二个串是ba,如果数据量就这么大,循环也就此结束,那么答案显然就是1。这个时候,a[i][j]应该等于1,并且会顶掉max中原本的0作为答案。

我们继续往下走,第二个串就已经找到baa了,还是假设在这停顿,答案应该是2。继续走,中间有好多不合适的,然后又发现一个a,这时第二个串应该是baabcda了,那么这里答案会是3吗?显然不是。这里最终答案应该还是2,但是a[i][j]在这里还要进行一次记录,具体记录什么?现在还是看不出来。

试想一下,如果第二个串是baaaaaaa,遍历的时候是怎样?每次找到一个a,答案就会增加,但如果是baaabaaa,在找到第四个a的时候答案不会增加了,因为此时有b阻挡,它不能被计入到之前的答案中。那么对于第四个a,可以发现,阻挡它的b正好是前件!并且这个阻挡的b还可以推广到很长很长一大段,以刚才的baabcda为例,在找到第三个a的时候,a[i][j]需要改变,但是max是不会变的,原因就是有前件的阻挡导致它们无法在同一个子串中。

遍历完成,根据a字母,我们处理了一些a数组的问题,但此时答案仍不明确。我们继续模拟,下一个字母是b,在第二个串中一上来就能找到一个b,如果此时停顿,答案是1。然后我们找到baab,找到第二个b后,假设此时停顿,答案是多少?

根据思维定势,这里可能会说1。但是如果把状态画一下,第一个串已经扫到了b,那这么看就是b在baab里面的最大子串,这固然是1啊,哪里不对呢。我觉得,我们可能忘掉了a对a数组所做的贡献。如果第一个串按ab算,对于第二个串的baab,答案应该是2而不是1。后续模拟发现答案不会增长。

然后第一个串找到了c,模拟发现答案变成了3,在baabc处发现了abc子串。思考一下,在ab子串那里,我们记录的答案是2,也就是说这里的a[i][j]应该等于2才对。到了baabc那里a[i][j]就应该变成了3。再找d的话a[i][j]在第一次找到abcd子串的时候就会更新成4。在这个数据里面,4就是最终答案了。

根据之前对前件的怀疑,我觉得可以猜一个大体的答案:

a[i][j] = 前件 + 1

前件只算是个怀疑,+1是怎么来的?每次一层循环只+1,也就是说第一个串在循环时长度只会比上一个串多1,那么最后的公共子串答案要算的话也是最多只能是在前件答案的基础上+1。

说了这么多,a[i][j]的含义可能已经比较明确了。可以说,a[i][j]表示字符串s1的前i位置和s2的前j位置的最大公共子串的长度。通过每次更新第一个串的长度去更新后续的a[i][j],同时更新答案。那么最后两层循环全部完成后,就能算出答案。

那么具体的前件到底是什么?想一想,对于a[i][j],结合刚才的分析,它的上一个状态是什么?

woc我分析不下去了……前件是a[i-1][j-1]…

T7 日期问题

小明正在整理一批历史文献。这些历史文献中出现了很多日期。小明知道这些日期都在1960年1月1日至2059年12月31日。令小明头疼的是,这些日期采用的格式非常不统一,有采用年/月/日的,有采用月/日/年的,还有采用日/月/年的。更加麻烦的是,年份也都省略了前两位,使得文献上的一个日期,存在很多可能的日期与其对应。

比如02/03/04,可能是2002年03月04日、2004年02月03日或2004年03月02日。

给出一个文献上的日期,你能帮助小明判断有哪些可能的日期对其对应吗?

输入

一个日期,格式是”AA/BB/CC”。 (0 <= A, B, C <= 9)

输出

输出若干个不相同的日期,每个日期一行,格式是”yyyy-MM-dd”。多个日期按从早到晚排列。

样例输入

02/03/04

样例输出

2002-03-04
2004-02-03
2004-03-02

资源约定:
峰值内存消耗(含虚拟机) < 256M
CPU消耗 < 1000ms

这个不算难,就是有点麻烦。记录下yy,mm,dd,然后根据年月日,月日年,日月年大小排个序,输出一下就好。

如果再谈一下细节的话,那就是去判断闰年的2月,如果非闰年还有2月29号应该是不行的。

T8 包子凑数

小明几乎每天早晨都会在一家包子铺吃早餐。他发现这家包子铺有N种蒸笼,其中第i种蒸笼恰好能放Ai个包子。每种蒸笼都有非常多笼,可以认为是无限笼。

每当有顾客想买X个包子,卖包子的大叔就会迅速选出若干笼包子来,使得这若干笼中恰好一共有X个包子。比如一共有3种蒸笼,分别能放3、4和5个包子。当顾客想买11个包子时,大叔就会选2笼3个的再加1笼5个的(也可能选出1笼3个的再加2笼4个的)。

当然有时包子大叔无论如何也凑不出顾客想买的数量。比如一共有3种蒸笼,分别能放4、5和6个包子。而顾客想买7个包子时,大叔就凑不出来了。

小明想知道一共有多少种数目是包子大叔凑不出来的。

输入

第一行包含一个整数N。(1 <= N <= 100)
以下N行每行包含一个整数Ai。(1 <= Ai <= 100)

输出

一个整数代表答案。如果凑不出的数目有无限多个,输出INF。

例如,
输入:
2
4
5

程序应该输出:
6

再例如,
输入:
2
4
6

程序应该输出:
INF

样例解释:
对于样例1,凑不出的数目包括:1, 2, 3, 6, 7, 11。
对于样例2,所有奇数都凑不出来,所以有无限多个。

资源约定:
峰值内存消耗(含虚拟机) < 256M
CPU消耗 < 1000ms

T9 分巧克力

儿童节那天有K位小朋友到小明家做客。小明拿出了珍藏的巧克力招待小朋友们。
小明一共有N块巧克力,其中第i块是Hi x Wi的方格组成的长方形。

为了公平起见,小明需要从这 N 块巧克力中切出K块巧克力分给小朋友们。切出的巧克力需要满足:1. 形状是正方形,边长是整数  2. 大小相同  

例如一块6x5的巧克力可以切出6块2x2的巧克力或者2块3x3的巧克力。

当然小朋友们都希望得到的巧克力尽可能大,你能帮小Hi计算出最大的边长是多少么?

输入
第一行包含两个整数N和K。(1 <= N, K <= 100000)
以下N行每行包含两个整数Hi和Wi。(1 <= Hi, Wi <= 100000)
输入保证每位小朋友至少能获得一块1x1的巧克力。

输出
输出切出的正方形巧克力最大可能的边长。

样例输入:
2 10
6 5
5 6

样例输出:
2

资源约定:
峰值内存消耗(含虚拟机) < 256M
CPU消耗 < 1000ms

我总感觉可以二分答案啊。边长下限是1,上限是最大那块巧克力的较小边(这个。。。不唯一),然后二分答案后模拟构造分的巧克力,看看能不能够,如果能够就二分右边,不够就二分左边。

T10 k倍区间

给定一个长度为N的数列,A1, A2, … AN,如果其中一段连续的子序列Ai, Ai+1, … Aj(i <= j)之和是K的倍数,我们就称这个区间[i, j]是K倍区间。

你能求出数列中总共有多少个K倍区间吗?

输入

第一行包含两个整数N和K。(1 <= N, K <= 100000)
以下N行每行包含一个整数Ai。(1 <= Ai <= 100000)

输出

输出一个整数,代表K倍区间的数目。

例如,
输入:
5 2
1
2
3
4
5

程序应该输出:
6

资源约定:
峰值内存消耗(含虚拟机) < 256M
CPU消耗 < 2000ms

初读。。嗯前缀和?。。看看数据量。。woc树状数组?然后看看单点限制。。两秒?!

不知道n2算法能不能两秒跑十万呢(手动滑稽

解决算法复杂度后,这题就没有难度了。


-------------本文结束,感谢您的阅读转载请注明原作者及出处-------------


本文标题:蓝桥杯17年省赛原题佛系题解

文章作者:Shawn Zhou

发布时间:2019年03月17日 - 08:03

最后更新:2019年03月18日 - 18:03

原始链接:http://shawnzhou.xyz/2019/03/17/19-03-17-01/

许可协议: 署名-非商业性使用-禁止演绎 4.0 国际 转载请保留原文链接及作者。

知识无价,码字不易。对您有用,敬请打赏。金额随意,感谢关心。
0%