2017蓝桥杯B组真题 B（等差素数列）C（承压计算）E（取数位）F（最大公共子串）

2024-02-02 18:48
文章标签 计算 最大 蓝桥 公共 2017 子串 素数 数位 组真题 承压

本文主要是介绍2017蓝桥杯B组真题 B（等差素数列）C（承压计算）E（取数位）F（最大公共子串），希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

B 等差素数列
在这里插入图片描述
题解：由题意知所求等差素数列长度为10，所以现在只需要考虑该数列的起始位置和公差，直接for循环暴力搜索，因为所求数列的每个元素都是素数，为了方便提前做一个素数打表。

代码如下

#include<stdio.h>
#include<string.h>
#include<algorithm>
using namespace std;
int a[100010];
void su()  //素数打表 
{int i,j;a[0]=a[1]=1;for(i=2;i<100000;i++){if(a[i]==0){for(j=2;i*j<100000;j++)a[i*j]=1;}}
}
int main()
{memset(a,0,sizeof(a));su();int i,j,k,s,flag=0;for(i=1;i<1000;i++)  //公差 {for(j=2;j*10<100000;j++)  //起始位置 {for(k=1;k<10;k++)  //连续十个都是素数 if(a[j+i*k]!=0)break;if(k==10){printf("%d\n",i);flag=1;break;}}if(flag)break;}return 0;}

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

题解； 为了方便计算和观察将数据转换为直角三角的形式如图
在这里插入图片描述
通过观察可得出第一列的重量为自身加正上方重量的一半，其他列为自身加上正上方和左上方重量的一半，然后for循环计算可得出结果。因题目数据输入太多容易出错，可略去输入直接将数据放入数组

代码如下

#include<stdio.h>
#include<string.h>
#include<algorithm>
using namespace std;
double a[50][50]
{{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}
};
int main()
{int i,j;double maxx=0,minn=9999999;for(i=1;i<=29;i++){for(j=0;j<=i;j++){if(j==0)a[i][j]=a[i][j]+a[i-1][j]/2.0;elsea[i][j]=a[i][j]+a[i-1][j-1]/2.0+a[i-1][j]/2.0;}}for(i=0;i<=29;i++){if(a[29][i]<minn)minn=a[29][i];if(a[29][i]>maxx)maxx=a[29][i];}printf("%.0lf\n",2086458231/minn*maxx);return 0;
}

E 取数位
在这里插入图片描述
题解； X为23574，输出结果为5，说明取的第三位，在调用的函数中返回的值为X%10，要想返回的值是5，就需要舍去X中5后边的74，再加上 if 判断可知满足条件的X长度为3，由此得出填空部分就是要舍去74，对X除以10调用两次可满足条件。

代码如下

#include<stdio.h>
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 f(x/10,3);  //填空
}
int main()
{int x = 23574;printf("%d\n", f(x,3));return 0;
}

F 最大公共子串

F 最大公共子串：最大公共子串长度问题就是：
求两个串的所有子串中能够匹配上的最大长度是多少。
比如："abcdkkk" 和 "baabcdadabc"，
可以找到的最长的公共子串是"abcd",所以最大公共子串长度为4。
下面的程序是采用矩阵法进行求解的，这对串的规模不大的情况还是比较有效的解法。
请分析该解法的思路，并补全划线部分缺失的代码。
注意：只提交缺少的代码，不要提交已有的代码和符号。也不要提交说明性文字。
#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)*N*N);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;
}

题解；这道题主要就是需要理解题中二维数组的含义，调用函数返回的值是max,而max是由a[ i ][ j ]得来的，再根据题意可知二维数组代表的就是最大公共子串的长度，再由函数中两个循环分别循环两个数组的长度以及 if 判断，可推断出a[ i ][ j ]表示的是第一个字符串的前 i 部分（不包含i）与第二个字符串的前 j 部分（不包含j）的最大公共子串的长度，所以可得出当第一个字符串的第 i-1个字符和第二个字符串的第 j-1个字符相等时，a[ i ][ j ] = a[ i-1 ][ j-1 ] + 1.

代码如下

#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)*N*N);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] = a[i-1][j-1]+1;  //填空if(a[i][j] > max) max = a[i][j];}}}return max;
}
int main()
{printf("%d\n", f("abcdkkk", "baabcdadabc"));return 0;
}

这篇关于2017蓝桥杯B组真题 B（等差素数列）C（承压计算）E（取数位）F（最大公共子串）的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！


http://www.chinasem.cn/article/671631。

相关文章

poj2406（连续重复子串）

poj2406（连续重复子串）

题意:判断串s是不是str^n，求str的最大长度。 解题思路：kmp可解，后缀数组的倍增算法超时。next[i]表示在第i位匹配失败后，自动跳转到next[i]，所以1到next[n]这个串 等于 n-next[n]+1到n这个串。 代码如下； #include<iostream>#include<algorithm>#include<stdio.h>#include<math.
阅读更多...
poj3261（可重复k次的最长子串）

poj3261（可重复k次的最长子串）

题意：可重复k次的最长子串 解题思路：求所有区间[x,x+k-1]中的最小值的最大值。求sa时间复杂度Nlog(N),求最值时间复杂度N*N，但实际复杂度很低。题目数据也比较水，不然估计过不了。 代码入下： #include<iostream>#include<algorithm>#include<stdio.h>#include<math.h>#include<cstring
阅读更多...
spoj705( 求不相同的子串个数)

spoj705( 求不相同的子串个数)

题意：求串s的不同子串的个数 解题思路：任何子串都是某个后缀的前缀，对n个后缀排序，求某个后缀的前缀的个数，减去height[i](第i个后缀与第i-1 个后缀有相同的height[i]个前缀)。 代码如下： #include<iostream>#include<algorithm>#include<stdio.h>#include<math.h>#include<cstrin
阅读更多...
poj1330（LCA最近公共祖先）

poj1330（LCA最近公共祖先）

题意：求最近公共祖先 思路：之前学习了树链剖分，然后我就用树链剖分的一小部分知识就可以解这个题目了，记录每个结点的fa和depth。然后查找时，每次将depth大的结点往上走直到x = y。 代码如下： #include<iostream>#include<algorithm>#include<stdio.h>#include<math.h>#include<cstring>
阅读更多...
poj 1113 凸包+简单几何计算

poj 1113 凸包+简单几何计算

题意： 给N个平面上的点，现在要在离点外L米处建城墙，使得城墙把所有点都包含进去且城墙的长度最短。 解析： 韬哥出的某次训练赛上A出的第一道计算几何，算是大水题吧。 用convexhull算法把凸包求出来，然后加加减减就A了。 计算见下图： 好久没玩画图了啊好开心。 代码： #include <iostream>#include <cstdio>#inclu
阅读更多...
uva 1342 欧拉定理（计算几何模板）

uva 1342 欧拉定理（计算几何模板）

题意： 给几个点，把这几个点用直线连起来，求这些直线把平面分成了几个。 解析： 欧拉定理： 顶点数 + 面数 - 边数= 2。 代码： #include <iostream>#include <cstdio>#include <cstdlib>#include <algorithm>#include <cstring>#include <cmath>#inc
阅读更多...
uva 11178 计算集合模板题

uva 11178 计算集合模板题

题意： 求三角形行三个角三等分点射线交出的内三角形坐标。 代码： #include <iostream>#include <cstdio>#include <cstdlib>#include <algorithm>#include <cstring>#include <cmath>#include <stack>#include <vector>#include <
阅读更多...
XTU 1237 计算几何

XTU 1237 计算几何

题面： Magic Triangle Problem Description: Huangriq is a respectful acmer in ACM team of XTU because he brought the best place in regional contest in history of XTU. Huangriq works in a big compa
阅读更多...
poj 3723 kruscal，反边取最大生成树。

poj 3723 kruscal，反边取最大生成树。

题意： 需要征募女兵N人，男兵M人。 每征募一个人需要花费10000美元，但是如果已经招募的人中有一些关系亲密的人，那么可以少花一些钱。 给出若干的男女之间的1~9999之间的亲密关系度，征募某个人的费用是10000 - （已经征募的人中和自己的亲密度的最大值）。 要求通过适当的招募顺序使得征募所有人的费用最小。 解析： 先设想无向图，在征募某个人a时，如果使用了a和b之间的关系
阅读更多...
poj 3258 二分最小值最大

poj 3258 二分最小值最大

题意： 有一些石头排成一条线，第一个和最后一个不能去掉。 其余的共可以去掉m块，要使去掉后石头间距的最小值最大。 解析： 二分石头，最小值最大。 代码： #include <iostream>#include <cstdio>#include <cstdlib>#include <algorithm>#include <cstring>#include <c
阅读更多...

Copyright China编程 23002807@qq.com

沪ICP备2023033072号-2