2017年第八届C/C++ B组蓝桥杯省赛真题

文章目录

• • 第一题：购物单(5分)
  • • • 题目描述
      • 题目分析
      • 题目代码
      • 题目答案
  • 第二题：等差素数列（7分）
  • • • 题目描述
      • 题目分析
      • 题目代码
      • 题目答案
  • 第三题：承压计算(13分)
  • • • 题目描述
      • 题目分析
      • 题目代码
      • 题目答案
  • 第四题：方格分割（17分）
  • • • 题目描述
      • 题目分析
      • 题目代码
      • 题目答案
  • 第七题：日期问题（19分）
  • • • 题目描述
      • 题目分析
      • 题目代码
  • 第八题：包子凑数（21分）
  • • • 题目描述
      • 题目分析
      • 题目代码
  • 第九题：分巧克力（23分）
  • • • 题目描述
      • 题目分析
      • 题目代码
  • 第十题：k倍区间（25分）
  • • • 题目描述
      • 题目分析
      • 题目代码

第一题：购物单(5分)

题目描述

小明刚刚找到工作，老板人很好，只是老板夫人很爱购物。老板忙的时候经常让小明帮忙到商场代为购物。小明很厌烦，但又不好推辞。
这不，XX大促销又来了！老板夫人开出了长长的购物单，都是有打折优惠的。小明也有个怪癖，不到万不得已，从不刷卡，直接现金搞定。现在小明很心烦，请你帮他计算一下，需要从取款机上取多少现金，才能搞定这次购物。
取款机只能提供100元面额的纸币。小明想尽可能少取些现金，够用就行了。 你的任务是计算出，小明最少需要取多少现金。以下是让人头疼的购物单，为了保护隐私，物品名称被隐藏了。

     180.9088       10.2565      56.1490     104.6590     100.3080     297.1550      26.7565     130.6250     240.2858     270.6280     115.8788     247.3495      73.2190     101.0050      79.5450     278.4470     199.2650      12.9790     166.3078     125.5058      84.9890     113.3568     166.5750      42.5690      81.9095     131.7880     255.8978     109.1790     146.6968     139.3365     141.1678     154.7480      59.4280      85.4468     293.7088     261.7965      11.3088     268.2758     128.2988     251.0380     208.3975     128.8875      62.0690     225.8775      12.8975      34.2875      62.1658     129.1250     218.3750     289.6980

需要说明的是，88折指的是按标价的88%计算，而8折是按80%计算，余者类推。
特别地，半价是按50%计算。
请提交小明要从取款机上提取的金额，单位是元。
答案是一个整数，类似4300的样子，结尾必然是00，不要填写任何多余的内容。
特别提醒：不许携带计算器入场，也不能打开手机。

题目分析

使用scanf读取数据，要控制输入的格式.Ctrl+Z (+两次回车)结束输入

题目代码

#includeusing namespace std;int main(){double sum = 0,price;int k;while(scanf(" %lf %d\n",&price,&k)) {sum += price* k /100;}cout<<sum<<endl;//5128.84 因为结果必然是00,所以答案为5200return 0;}

题目答案

5200

第二题：等差素数列（7分）

题目描述

2,3,5,7,11,13,…是素数序列。
类似：7,37,67,97,127,157 这样完全由素数组成的等差数列，叫等差素数数列。
上边的数列公差为30，长度为6。
2004年，格林与华人陶哲轩合作证明了：存在任意长度的素数等差数列。这是数论领域一项惊人的成果！

有这一理论为基础，请你借助手中的计算机，满怀信心地搜索：长度为10的等差素数列，其公差最小值是多少？
注意：需要提交的是一个整数，不要填写任何多余的内容和说明文字。

题目分析

暴力解题，使用三层循环

题目代码

#includeusing namespace std;bool book[100005];bool isPrime(int n) { //判断是否是素数for(int i = 2; i * i <= n; i++) {if(n%i==0) {return false;}}return true;}int main() {for(int i = 2; i<100005; i++) { //打表if(isPrime(i)) {book[i] = true;}}for(int i = 1; i < 100005; i++) { //数列的起始位置for(int j = 1; j<= 1000; j++) { //公差int flag = 0;for(int k = 0; k < 10; k++){if(!book[i+k*j]){flag = 1;break;}}if(!flag){cout<<j<<endl;//210return 0;}}}return 0;}

题目答案

210

第三题：承压计算(13分)

题目描述

X星球的高科技实验室中整齐地堆放着某批珍贵金属原料。
每块金属原料的外形、尺寸完全一致，但重量不同。
金属材料被严格地堆放成金字塔形。

 75 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 65 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 38 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 42 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 1X 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
请你推算出：读数最大的电子秤的示数为多少？
注意：需要提交的是一个整数，不要填写任何多余的内容。

笨笨有话说：
不断的除2，加到下面，除2,加到下面,… 不会浮点精度溢出吧？
歪歪有话说：
怕除不开还不好办， 把每个数字扩大一定的倍数不就好了。

题目分析

模拟

题目大意:金属块以金字塔的形式堆叠而成,最后一层(30)是一排电子秤.每个物体的重量最终都会均分到下面紧邻的物体上,最终分到电子秤上.

每个方块承受的重量 = 上方与其紧邻的两个方块的承受质量 / 2 + 自身的重量

所以只需要用一个二维数组arr,将每个方块承受的重量存起来,然后从上到下,从左到右,就可以推出最后一排电子秤上的质量了.

说一下精度,由于计算每个木块的承受质量时,原料承受的质量是上一层对应原料的量(质量+承受的质量) / 2.举个栗子,第一层的方块质量为7,均分到最后一层的称上的重量就是 7 / (2^29),相当于就成0了.这肯定影响最后结果的准确性的.所以我们为了提高精度,就要缩小计量单位,把每个方块的质量 * (2^29).这样就可以保证计算过程中不会出现浮点数情况了.(至少得>= 2^29, 也可以更大哦.)

另外,因为本题数据量较大,要使用long long int类型计算.

题目代码

#includeusing namespace std;long long int arr[35][35],max1,min1,num;int main(){for(int i = 1; i <= 29; i++){//初始化arr,重量整体扩大2^29. 因为下面会有29次 /2 for(int j = 1; j <= i;j++){cin>>num;arr[i][j] = num*(1<<29)+arr[i-1][j-1]/2+arr[i-1][j]/2;}}for(int j = 1; j<=30; j++) {arr[30][j] = arr[29][j-1]/2+arr[29][j]/2;if(j==1){//min1和max1初始化 min1 = arr[30][j];max1 = arr[30][j];}if(arr[30][j]>max1){max1 = arr[30][j];}if(arr[30][j] < min1){min1 = arr[30][j];}cout<<arr[30][j]<<" ";}cout<<endl;int bs = 2086458231 / min1;//咱们是按照最低精度(2^29,当然可以更大),这样才可以保证准确无误.所以最后要看下与电子秤相差的倍数.我们的最大值也要进行变换. cout<< max1 * bs <<endl;//72665192664return 0;}

题目答案

72665192664

第四题：方格分割（17分）

题目描述

6x6的方格，沿着格子的边线剪开成两部分。
要求这两部分的形状完全相同。
如图：p1.png, p2.png, p3.png 就是可行的分割法

试计算：
包括这3种分法在内，一共有多少种不同的分割方法。
注意：旋转对称的属于同一种分割法。
请提交该整数，不要填写任何多余的内容或说明文字。

题目分析

每一种对称分割都必然要经过中间的点,关于这个点对称,即(3,3). 以该点为起点,向两个相反的方向搜索,直到走到正方形的边缘,则找到一种方案. 然后进行回溯,寻找其他方案. 因为一种分割方法可以转换为四种方向,所以最后答案还要/4.

题目代码

#includeusing namespace std;int arr[10][10],vis[10][10],ans;//arr地图  vis:标记是否走过int NEXT[4][2] = {//方向数组-1,0,//上1,0,//下0,-1,//左0,1//右};void dfs(int x,int y) {if(x==0||x==6||y==0||y==6) {ans++;return;}for(int i = 0; i < 4; i++) {int tx = x+NEXT[i][0];int ty = y + NEXT[i][1];if(tx<0||tx>6||ty<0||ty>6) { //越界continue;}if(!vis[tx][ty]) {vis[tx][ty]  = 1;vis[6-tx][6-ty] = 1;//相反方向进行搜索. dfs(tx,ty);vis[tx][ty]  = 0;//进行回溯,因为要寻找所有的方法vis[6-tx][6-ty] = 0;}}}int main() {vis[3][3] = 1;//进行标记dfs(3,3);cout<<ans/4<<endl;//因为一种分割方法最后可以转换为四个方向,所以最后答案还要/4return 0;}

题目答案

509

第七题：日期问题（19分）

题目描述

小明正在整理一批历史文献。这些历史文献中出现了很多日期。小明知道这些日期都在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/042002-03-042004-02-032004-03-02

资源约定：
峰值内存消耗（含虚拟机） < 256M
CPU消耗 < 1000ms

题目分析

模拟 用scanf控制输入,然后就是模拟三种情况是否符合.最后可以使用set进行排序输出.

题目代码

#includeusing namespace std;int months[13] = {0,31,29, 31,30,31,30,31,31,30,31,30,31 };set<string> jh;//用于排序,默认从小到大排void judgeRN(int year){if((year%4==0 && year %100!=0) || year % 400 ==0){months[2] = 29;//是闰年 }else{months[2] = 28;}} bool check(int& year,int month,int date) {//检查当前这种方案是否符合if(year<=59){//修改年为正确的格式 year+=2000;}else{year+=1900;}if(month<1||month>12){//月 return false;}judgeRN(year);if(date<1 || date > months[month]){return false;}return true;}void solve(int year,int month,int date){string res = "";//判断年月日是否符合条件 if(check(year,month,date)){//修改month和date到对应的格式res += to_string(year) ;res+="-";if(month < 10){res+="0";}res+= to_string(month);res+="-";if(date<10){res+="0";}res+=to_string(date);jh.insert(res);}}int main() {//年00-99  月:0-12  日:0-31/30/28/29int AA,BB,CC;scanf("%d/%d/%d",&AA,&BB,&CC);//用C语言的scanf控制输入,非常之精妙!solve(AA,BB,CC);//要看清题目,只有是三种情况,不要自作聪明哦. //solve(AA,CC,BB);//solve(BB,AA,CC);//solve(BB,CC,AA) ;solve(CC,AA,BB);solve(CC,BB,AA);for(set<string>::iterator it = jh.begin(); it != jh.end(); it++){cout<<*it<<endl;}return 0;}

第八题：包子凑数（21分）

题目描述

小明几乎每天早晨都会在一家包子铺吃早餐。他发现这家包子铺有 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。

输入输出样例

示例 1

输入

245

输出

6

样例说明

凑不出的数目包括：1, 2, 3, 6, 7, 11。

示例 2

输入

246

输出

INF

样例说明

所有奇数都凑不出来，所以有无限多个

运行限制

• 最大运行时间：1s
• 最大运行内存: 256M

题目分析

完全背包+不定方程

不定方程: ax+by=c

• 假设a,b互质,那么x,y一定有解且有无穷个. 但当x,y>=0,ax+by=c此时导致方程无解c的个数是有限的.
• 如果a,b不互质,则不能保证有解. 说明a,b不互质的情况下有无穷多个c使得方程无解.

对于a1x1+a2x2+a3x3+⋯+anxn=ca1x1+a2x2+a3x3+⋯+anxn=c

• 如果a1,a2,a3,⋯,ana1,a2,a3,⋯,an互质，x1,x2,x3,⋯,xnx1,x2,x3,⋯,xn一定有解且有无穷多个。但此时导致方程无解的cc的个数有限，也就是凑不出的包子数目有限。

• 如果a1,a2,a3,⋯,ana1,a2,a3,⋯,an不互质，那么就有无穷多个c使得方程无解，也就是有无穷多个包子数目凑不出来，所以输出INF。

动规五部曲

1. 确定dp数组的含义

dp[i]:代表 包子个数为i,是否可以凑出.

2. 确定递推公式

当前需要的包子数(背包容量),可以由使用当前这种类型的笼子 和 不使用当前类型的笼子组成. 之间是 或 的关系,因为我们求的是是否有这种方案,只有存在就达到我们的目的. 所以递推公式 dp[j] = dp[j] | dp[j-type[i]];

3. dp数组初始化

根据递推公式,当前dp[j]需要用到之前的dp[j-type[i]].dp[0]代表 包子个数为0时,是否有合适的笼子方案,那就不需要笼子呗,所以dp[0] = true

4. 确定遍历顺序

根据递推顺序,当前dp[j]需要用到之前的dp[j-type[i]],所以遍历顺序是从左到右 ,因为是完全背包,所以外层for遍历物品,内层for遍历背包大小.

5.举例dp数组

题目代码

#includeusing namespace std;const int N = 105;const int M = 30;bool dp[M];//dp数组:代表 包子个数为i,是否可以凑出.int n;int type[N],g,cnt;//类型数组//打印dp void print(){for(int i = 0;i <=M;i++){cout<<dp[i]<<" ";}cout<<endl;}int main() {cin>>n;for(int i = 1; i<= n; i++) {cin>>type[i];if(i == 1) {g = type[i];} else {g = __gcd(type[i],g);}}if(g>1) {cout<<"INF"<<endl;return 0;}//递推dpdp[0] = true;//初始化, //print();for(int i = 1; i<=n; i++) { //遍历外层物品for(int j = type[i]; j <= M;j++){//遍历背包容量 dp[j]  = dp[j] | dp[j-type[i]];//状态转移方程   只要有一种方案凑出就好,所以用 | 操作. }//print();}for(int i = 1;i <= M;i++) {if(!dp[i]){cnt++;}}cout<<cnt<<endl; return 0;}

第九题：分巧克力（23分）

题目描述

儿童节那天有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 106 55 6

样例输出：

2

资源约定：
峰值内存消耗（含虚拟机） < 256M
CPU消耗 < 1000ms

题目分析

题目的意思是把巧克力分成大小相同的正方形给小朋友,所以需要满足两个条件

• 巧克力的 大小要尽可能的大
• 切割后的正方形巧克力的总数要 >= 小朋友人数

假设一块巧克力长为 X,宽为Y,切割成的正方形边长为w,则该个达巧克力可以切割出小正方形的块数是 X/w * Y/w ,巧克力题目已经给出了,我们需要做的事列举可能的切割边长.

巧克力长宽以及个数范围都为 (1 <= Hi, Wi <= 100000 ),所以使用暴力模拟很可能超时. 我们采用二分法来枚举可能出现的巧克力边长,时间复杂度就成了 $O(log2n)$.

题目代码

#includeusing namespace std;const int M = 100005;int n,k,L,R,ans,mid,arr[M][2];//arr:巧克力数组,存储巧克力的长和宽 bool judge(int x){//判断用当前边长分割巧克力 方案是否可行 int res = 0;for(int i = 0;i < n;i++){int num1 = arr[i][0]/x;int num2 = arr[i][1]/x;res+=num1*num2;}if(res>=k){return true;}return false;}int main(){cin>>n>>k;for(int i = 0; i < n;i++){//初始化巧克力数组 cin>>arr[i][0]>>arr[i][1];} //二分查找寻找合适位置L =  1;R = 100000;while(L <= R){ //left > right如果最后一步 if left=mid  mid = (L+R) / 2;  // 5 6   L = 6  mid = 6 X  R = 5if(judge(mid)){L = mid+1;}else{R = mid - 1;}}cout<<R<<endl;//最后不知道输入R还是L可以举个例子,比如 L = 5,R = 6时,judge[5]是true.但是judge[6] 是false的...然后走一下流程就懂了 return 0;}

第十题：k倍区间（25分）

题目描述

给定一个长度为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 212345

程序应该输出：

6

资源约定：
峰值内存消耗（含虚拟机） < 256M
CPU消耗 < 2000ms

题目分析

前缀和+枚举 具体思路和详细后序补上. 先附上某位大佬的代码.

题目代码

#includeusing namespace std;typedef long long ll;const int N=1e5+5;int sum[N],cnt[N],n,k;ll ans;int main(){scanf("%d%d",&n,&k),cnt[0]=1;for(int i=1;i<=n;i++){scanf("%d",&sum[i]),sum[i]=(sum[i-1]+sum[i])%k;ans+=cnt[sum[i]];cnt[sum[i]]++;}printf("%lld\n",ans);return 0;}

备注:由于蓝桥杯不再考察补全代码题型，所以未整理总结其思路

如果有收获！！！ 希望老铁们来个三连，点赞、收藏、转发。
创作不易，别忘点个赞，可以让更多的人看到这篇文章，顺便鼓励我写出更好的博客