锐客网

  1. 首页 > it技术 > >

蓝桥杯|2018年第九届C/C++ A组蓝桥杯省赛真题部分题解（C语言/C++）

c语言哈希表动态规划蓝桥杯算法#


目录

  • 哪天返回
  • 猴子分香蕉
  • 第几个幸运数
  • 书号验证
  • 次数差
  • 耐摔指数
  • 较小分数

哪天返回 题目描述 小明被不明势力劫持。后莫名其妙被扔到x星站再无问津。小明得知每天都有飞船飞往地球，但需要108元的船票，而他却身无分文。 他决定在x星战打工。好心的老板答应包食宿，第1天给他1元钱。 并且，以后的每一天都比前一天多2元钱，直到他有足够的钱买票。 请计算一下，小明在第几天就能凑够108元，返回地球。
要求提交的是一个整数，表示第几天。请不要提交任何多余的内容。
题目分析
一个简单的循环即可。
题目代码
————————————————
#include int main() { int sum = 0; int i = 1; int day = 1; while(sum<108) { day++; sum = sum+i+2*(day-1); } printf("%d",day); return 0; }

猴子分香蕉 题目描述 5只猴子是好朋友，在海边的椰子树上睡着了。这期间，有商船把一大堆香蕉忘记在沙滩上离去。 第1只猴子醒来，把香蕉均分成5堆，还剩下1个，就吃掉并把自己的一份藏起来继续睡觉。 第2只猴子醒来，重新把香蕉均分成5堆，还剩下2个，就吃掉并把自己的一份藏起来继续睡觉。 第3只猴子醒来，重新把香蕉均分成5堆，还剩下3个，就吃掉并把自己的一份藏起来继续睡觉。 第4只猴子醒来，重新把香蕉均分成5堆，还剩下4个，就吃掉并把自己的一份藏起来继续睡觉。 第5只猴子醒来，重新把香蕉均分成5堆，哈哈，正好不剩！
请计算一开始最少有多少个香蕉。
需要提交的是一个整数，不要填写任何多余的内容。
题目分析
本题主要在于多次使用if进行条件的限制即可，接着从1开始枚举数字直到符合题意，即符合多次的if条件即可输出。
题目代码
————————————————
#include int main() { int i = 1; while(i>=1) { if((i-1)%5==0&&i!=1) { int temp1 = i-1-(i-1)/5; if((temp1-2)%5==0&&temp1!=2) { int temp2 = temp1-2-(temp1-1)/5; if((temp2-3)%5==0&&temp2!=3) { int temp3 = temp2-3-(temp2-1)/5; if((temp3-4)%5==0&&temp3!=4) { int temp4 = temp3-4-(temp3-1)/5; if(temp4%5==0&&temp4!=0) { printf("%d",i); break; } } } } } i++; } return 0; }

第几个幸运数 题目描述 到x星球旅行的游客都被发给一个整数，作为游客编号。 x星的国王有个怪癖，他只喜欢数字3,5和7。 国王规定，游客的编号如果只含有因子：3,5,7,就可以获得一份奖品。
我们来看前10个幸运数字是： 3 5 7 9 15 21 25 27 35 45 因而第11个幸运数字是：49
小明领到了一个幸运数字 59084709587505，他去领奖的时候，人家要求他准确地说出这是第几个幸运数字，否则领不到奖品。
请你帮小明计算一下，59084709587505是第几个幸运数字。
需要提交的是一个整数，请不要填写任何多余内容。
题目分析
这与力扣的一题非常相似，具体思路可以参考我的博客力扣——丑数II。
具体思路就是从反面出发，我们不需要一个一个枚举从1到题中所给数字的所有满足条件的数，我们只需要找到题目所要求的那些符合条件的数即可。
因此我们不需要使用枚举+条件选择来进行模拟，我们可以直接“找”出对应数字，从1开始找直到找到对应数字即可。
因此使用动态规划的思路即可。
题目代码
————————————————
#include//这里我模拟的是幸运数在10000以内的情况下的通用程序，此题所给幸运数过大，将int改为long long即可 int least(int a,int b,int c) { int temp = a

以下是我从别人博客看到的***使用C++***的另一种方式
#include using namespace std; const int a[] = {3,5,7}; const long long maxn = 49; priority_queue,greater >p; sets; int res; int main(){ long long n,m; for(int i = 0; i < 3; i++)p.push(a[i]); while((n = p.top())<=maxn){ p.pop(); res++; for(int i = 0; i < 3; i++){ m = n*a[i]; if(!s.count(m)){ s.insert(m); p.push(m); } } } cout << res; return 0; }

书号验证 【蓝桥杯|2018年第九届C/C++ A组蓝桥杯省赛真题部分题解（C语言/C++）】题目描述 2004年起，国际ISBN中心出版了《13位国际标准书号指南》。 原有10位书号前加978作为商品分类标识；校验规则也改变。 校验位的加权算法与10位ISBN的算法不同，具体算法是： 用1分别乘ISBN的前12位中的奇数位（从左边开始数起），用3乘以偶数位，乘积之和以10为模，10与模值的差值再对10取模（即取个位的数字）即可得到校验位的值，其值范围应该为0~9。
下面的程序实现了该算法，请仔细阅读源码，填写缺失的部分。
————————————————
题解：
把握好题意的上半部分即可，即通过遍历将字符串的每一位都专门的选择出来，然后判断其是否为有效的字符，然后再判断这一位是奇数位还是偶数位，然后分别叫进行不同的操作即可，后面的内容对解答此题是无所谓的。
需要注意的是不能直接c*3,要先通过隐式转换变成整型才可，即减去一个‘0’。
// 验证成功返回1，否则返回0 int f(const char* s) { int k=1; int sum = 0; int i; for(i=0; s[i]!='\0'; i++){ char c = s[i]; if(c=='-' || c==' ') continue; sum +=k%2==1?(c-'0')*3:(c-'0') ; //填空位置 k++; if(k>12) break; }while(s[i]!='\0') i++; return (s[i-1]-'0') == (10-sum % 10)%10; }int main() { printf("%d\n",f("978-7-301-04815-3")); printf("%d\n",f("978-7-115-38821-6")); return 0; }

次数差 题目描述 x星球有26只球队，分别用a~z的26个字母代表。他们总是不停地比赛。 在某一赛段，哪个球队获胜了，就记录下代表它的字母，这样就形成一个长长的串。 国王总是询问：获胜次数最多的和获胜次数最少的有多大差距？（当然，他不关心那些一次也没获胜的，认为他们在怠工罢了）
输入，一个串，表示球队获胜情况（保证串的长度<1000）
要求输出一个数字，表示出现次数最多的字母比出现次数最少的字母多了多少次。
比如： 输入： abaabcaa
则程序应该输出： 4
解释：a出现5次，最多；c出现1次，最少。5-1=4
再比如： 输入： bbccccddaaaacccc
程序应该输出： 6
资源约定： 峰值内存消耗（含虚拟机） < 256M CPU消耗 < 1000ms
题目分析
本题可以直接使用哈希表存储每次出现的字母，接着对这个哈希表进行遍历，如果此时遍历到的哈希表的某一序列其存储值不为0，即为有效哈希表，然后对有效哈希表进行选择，选出出现最多的和出现最少的字母，即对应哈希表中存储数最大的和数最小的即可，然后做差得到答案。
题目代码
————————————————
#include #include #include int main() { char zfc[1000]; scanf("%s",zfc); int n = strlen(zfc); int hash[26] = {0}; for(int i=0; imax) { max = hash[i]; } if(hash[i]

耐摔指数 题目描述 x星球的居民脾气不太好，但好在他们生气的时候唯一的异常举动是：摔手机。 各大厂商也就纷纷推出各种耐摔型手机。x星球的质监局规定了手机必须经过耐摔测试，并且评定出一个耐摔指数来，之后才允许上市流通。
x星球有很多高耸入云的高塔，刚好可以用来做耐摔测试。塔的每一层高度都是一样的，与地球上稍有不同的是，他们的第一层不是地面，而是相当于我们的2楼。
如果手机从第7层扔下去没摔坏，但第8层摔坏了，则手机耐摔指数=7。 特别地，如果手机从第1层扔下去就坏了，则耐摔指数=0。 如果到了塔的最高层第n层扔没摔坏，则耐摔指数=n
为了减少测试次数，从每个厂家抽样3部手机参加测试。
如果已知了测试塔的高度，并且采用最佳策略，在最坏的运气下最多需要测试多少次才能确定手机的耐摔指数呢？
输入数据，一个整数n（3 例如： 输入： 3
程序应该输出： 2
解释： 手机a从2楼扔下去，坏了，就把b手机从1楼扔；否则a手机继续3层扔下
再例如： 输入： 7
程序应该输出： 3
解释： a手机从4层扔，坏了，则下面有3层，b,c 两部手机2次足可以测出指数； 若是没坏，手机充足，上面5,6,7 三层2次也容易测出。
资源约定： 峰值内存消耗（含虚拟机） < 256M CPU消耗 < 1000ms
题目分析
这是一道典型的动态规划问题，具体详解可以见我的另外一篇博客蓝桥杯——测试次数。
因为使用C语言进行编写会牵扯到大量的函数定义以及头文件，所以这里使用C++进行编写更容易。
题目代码
————————————————
#includeusing namespace std; int main() {//这里我模拟的直接是10000层楼的情况，如果想变成一个自己输入楼层数然后得出结果的可以在前面加一个输入程序即可。 int dp[10001][3]; for(int i=1; i<=10000; i++) { dp[i][1] = i; } for(int i=1; i<=10000; i++) { int Min = INT_MAX; for(int j=1; j<=i; j++) { dp[i][2] = 1+max(dp[i-j][2],dp[j-1][1]); Min = min(dp[i][2],Min); } dp[i][2] = Min; } for(int i=1; i<=10000; i++) { int Min = INT_MAX; for(int j=1; j<=i; j++) { dp[i][3] = 1+max(dp[i-j][3],dp[j-1][2]); Min = min(dp[i][3],Min); } dp[i][3] = Min; } printf("%d",dp[10000][3]); }

较小分数 题目描述 回到小学---- 真分数：分子小于分母的分数 既约分数：分子分母互质，也就是说最大公约数是1
x星球数学城的入口验证方式是： 屏幕上显示一个真分数，需要你快速地找到一个比它小的既约分数，要求这个分数越大越好。 同时限定你的这个分数的分母不能超过100。
如下代码很暴力地解决了这个问题，请仔细分析，并填写划线部分缺失的代码。
————————————————
题解：
首先明确代码是通过暴力枚举分数出现的可能然后判断他是否满足题意来编写的程序，逐步分析每步含义即可。
int gcd(int a, int b) { if(b==0) return a; return gcd(b,a%b); } int main() { // 这是屏幕上显示的那个分数 a/b int a = 7; int b = 13; int m,n; int max_a = 0; int max_b = 1; for(n=100; n>1; n--){ for(m=n-1; m>=1; m--){ if(m*b

    推荐阅读


    上一篇：蓝桥杯题解|蓝桥杯“字串排序“题解

    下一篇：用优先级队列优化dijkstra