[蓝桥杯]2017蓝桥省赛B组题目及详解

[蓝桥杯]2017蓝桥省赛B组题目及详解

/*———————————————————————————————————————————————————————————【结果填空题】T1 (分值：5)题目：购物单小明刚刚找到工作，老板人很好，只是老板夫人很爱购物。老板忙的时候经常让小明帮忙到商场代为购物。小明很厌烦，但又不好推辞。这不，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，不要填写任何多余的内容。特别提醒：不许携带计算器入场，也不能打开手机。————————————————————————————————————————————————————————————*///解法//excel 或 计算器//编程：输入输出 用循环 按照百位四舍五入/*———————————————————————————————————————————————————————————【结果填空题】T2 (分值：7)题目：等差素数列2,3,5,7,11,13,....是素数序列。类似：7,37,67,97,127,157 这样完全由素数组成的等差数列，叫等差素数数列。上边的数列公差为30，长度为6。2004年，格林与华人陶哲轩合作证明了：存在任意长度的素数等差数列。这是数论领域一项惊人的成果！有这一理论为基础，请你借助手中的计算机，满怀信心地搜索：长度为10的等差素数列，其公差最小值是多少？注意：需要提交的是一个整数，不要填写任何多余的内容和说明文字。————————————————————————————————————————————————————————————*/// 暴力 + 枚举/*长度为10的等差素数列st，要求公差最小1. 素数列： 2 3 5 7 11 13 17 19 21 23 ...Max2. 枚举首项：a1 a2 a3 a4 a5 a6 a7 a8 枚举公差： 1 x ... 2 x ... 枚举个数 3 x ...*/#include #include #include using namespace std ;typedef long long LL ;setall ;//判断是否素数bool isPrime(LL t) { for (int i = 2; i < t / 2; ++i) { if (t % i == 0) return false ; } return true ;}//等差素数列int f(LL a[], int n) { for (int i = 0; i < n; ++i) { //枚举首项 LL first = a[i] ; for (int delta = 1; delta < a[n - 1] - first; ++delta) { //枚举公差 int m = first ; for (int j = 1; j < 10; ++j) { //枚举个数 m += delta ; if (all.find(m) == all.end()) //m不是素数 break ; if (m > a[n - 1])break ; if (j == 9)//已经找到10项 return delta ; } } } return -1 ;}const int N=5000 ;LL a[N] ;int main(int argc, const char *argv[]) { a[0] = 2 ; a[1] = 3 ; all.insert(2) ; all.insert(3) ; int index = 2 ; LL t = 5 ; while (index < N) { if (isPrime(t)) { a[index++] = t ; all.insert(t) ; } t++ ; } cout << f(a, N) << endl ; return 0 ;}//结果：210/*———————————————————————————————————————————————————————————【结果填空题】T3 (分值：13)题目：承压计算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请你推算出：读数最大的电子秤的示数为多少？注意：需要提交的是一个整数，不要填写任何多余的内容。————————————————————————————————————————————————————————————*////**/#includeusing namespace std ;typedef long long LL ;LL arr[30][30] ;int main(int argc, char const *argv[]){ LL factor = 1 ; for (int i = 0; i < 30; ++i) { factor << 1 ; } //输入数据放入二维数组 for(int i = 0; i < 29; ++i) { for (int j = 0; j <= i; ++j) { LL a ; scanf("%d",&a) ; arr[i][j] = a*factor ; } } /*LL factor = 1 ; for (int i = 0; i < 30; ++i) { factor << 1 ; }*/ cout << factor << endl ; //自上而下处理a[i][j]*factor(2^30)——> //除以2,,计入a[i+1][j]和a[i+1][j+1] for (int i = 0; i < 29; ++i) { for (int j = 0; j <= i;++j) { LL ha = arr[i][j]/2 ; arr[i+1][j] += ha ; arr[[i+1][j+1]] += ha ; } } //最后对a[N-1]这一行进行排序， //查看最小值与factor的倍数关系决定最大值是多少 sort(arr[29],arr[29]+30) ; cout << arr[29][0]/2 << "," << arr[29][29]/2 << endl ; //循环处理第2~N-1行 return 0;}/*———————————————————————————————————————————————————————————【结果填空题】T4 (分值：17)题目：方格分割6x6的方格，沿着格子的边线剪开成两部分。要求这两部分的形状完全相同。如图：p1.png, p2.png, p3.png 就是可行的分割法。+--+--+--+--+--+--+| | | | | | |+--+--+--+--+--+--+| | | | | | |+--+--+--+--+--+--+| | | | | | |+--+--+--+--+--+--+| | | | | | |+--+--+--+--+--+--+| | | | | | |+--+--+--+--+--+--+| | | | | | |+--+--+--+--+--+--+试计算：包括这3种分法在内，一共有多少种不同的分割方法。注意：旋转对称的属于同一种分割法。请提交该整数，不要填写任何多余的内容或说明文字。————————————————————————————————————————————————————————————*////*思路：所有的点关于中心点对称 则得到的形状相等以中心作为起点，沿着四个方向分别剪裁dfs(加标注):(移动切割的方式关于中心点反向对称) 坐标：中心点作为坐标原点(0,0) 则有x,y轴上坐标： x(-): x(+): y(+)： y(-)： (相当于一个形状围绕中心点右旋转180度)*/#includeusing namespace std ;int ans ;int dire[][2] = { {-1,0} ; //向上 { 1,0} ; //向下 {0,-1} ; //向左 { 0,1} ; //向右}//记录已访问过的点坐标int vis[7][7] ;void dfs(int x,int y){ //出口 if(x==0 || y==0 || x==6 || y==6) { ans++ ; return ; } //当前的点标注为已访问 vis[x][y] = 1 ; //对称点也标注为已访问 vis[6-x][6-y] = 1 ; for (int k = 0; k < 4; ++k) { int nx = x + dire[k][0] ; int ny = y + dire[k][1] ; //形成新坐标 if(nx < 0 || nx > 6 || ny < 0 || ny > 6) continue ; if (!vis[nx][ny]) { dfs(nx,ny) ; } } //回溯 vis[x][y] = 0 ; vis[6-x][6-y] = 0 ; //对称}int main(int argc, char const *argv[]){ dfs(3,3) ; cout << ans/4 << endl ; return 0;}//结果：509/*———————————————————————————————————————————————————————————【代码填空题】T5 (分值：9)题目：取数位求1个整数的第k位数字有很多种方法。以下的方法就是一种。————————————————————————————————————————————————————————————*/// 求x用10进制表示时的数位长度 #includeusing namespace std ;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 _____________________; */ //不是求最后一位，去掉最后一位，进行递归 return f(x/10,k) ; //递归} int main(){ int x = 23574; printf("%d\n", f(x,3)); return 0;}/*———————————————————————————————————————————————————————————【代码填空题】T6 (分值：11)题目：最大公共子串最大公共子串长度问题就是：求两个串的所有子串中能够匹配上的最大长度是多少。比如："abcdkkk" 和 "baabcdadabc"，可以找到的最长的公共子串是"abcd",所以最大公共子串长度为4。下面的程序是采用矩阵法进行求解的，这对串的规模不大的情况还是比较有效的解法。请分析该解法的思路，并补全划线部分缺失的代码。————————————————————————————————————————————————————————————*///暴力枚举#include #include #define N 256int 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][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;}/*———————————————————————————————————————————————————————————【代码编程题】T7 (分值：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/04 [样例输出]----2002-03-04 2004-02-03 2004-03-02 [资源约定]：峰值内存消耗（含虚拟机） < 256MCPU消耗 < 1000ms请严格按要求输出，不要画蛇添足地打印类似：“请您输入...” 的多余内容。[注意]：main函数需要返回0;只使用ANSI C/ANSI C++ 标准;不要调用依赖于编译环境或操作系统的特殊函数。所有依赖的函数必须明确地在源文件中 #include 不能通过工程设置而省略常用头文件。提交程序时，注意选择所期望的语言类型和编译器类型。————————————————————————————————————————————————————————————*//* 如下解：//1960年1月1日至2059年12月31日//AA/BB/CC */#include #include #include using namespace std;bool isLeap(int year) { return (year % 4 == 0 && year % 100 != 0) || year % 400 == 0;}void i2s(int i, string &s) { stringstream ss; ss << i; ss >> s;}string f(int a, int b, int c) { if (a >= 0 && a <= 59)a += 2000; else if (a >= 60 && a <= 99)a += 1900; else return ""; if (b < 1 || b > 12)return ""; if (c < 1 || c > 31)return ""; bool _isLeap = isLeap(a); switch (b) { //日期校验 case 2: if (_isLeap && c > 29)return ""; if (!_isLeap && c > 28)return ""; break; case 4: if (c > 30)return ""; break; case 6: if (c > 30)return ""; break; case 9: if (c > 30)return ""; break; case 11: if (c > 30)return ""; break; default: break; } string _a, _b, _c; i2s(a, _a); i2s(b, _b); i2s(c, _c); if (_b.length() == 1)_b = "0" + _b; if (_c.length() == 1)_c = "0" + _c; return _a + "-" + _b + "-" + _c;}int main(int argc, const char *argv[]) { string in; cin >> in; int a = 0, b = 0, c = 0; a = (in[0] - '0') * 10 + (in[1] - '0'); b = (in[3] - '0') * 10 + (in[4] - '0'); c = (in[6] - '0') * 10 + (in[7] - '0'); string case1 = f(a, b, c); string case2 = f(c, a, b); string case3 = f(c, b, a); set ans; if (case1 != "")ans.insert(case1); if (case2 != "")ans.insert(case2); if (case3 != "")ans.insert(case3); for (set::iterator iter = ans.begin(); iter != ans.end(); iter++) { cout << *iter << endl; } return 0;}/*———————————————————————————————————————————————————————————【代码编程题】T8 (分值：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。例如，输入：2 4 5 程序应该输出：6 再例如，输入：2 4 6 程序应该输出：INF样例解释：对于样例1，凑不出的数目包括：1, 2, 3, 6, 7, 11。 对于样例2，所有奇数都凑不出来，所以有无限多个。 资源约定：峰值内存消耗（含虚拟机） < 256MCPU消耗 < 1000ms————————————————————————————————————————————————————————————*//*ax+by=c 不定方程的解 a=4 b=7 c=17这种情况下，xy实际上有解，7*2+(7-4)==3*7-1*4a、b互质，一定有解且解的数目无穷c是gcd(a,b)的倍数，方程一定有解，而且有无穷多解*///条件1：一定有解=>a、b互质//条件2：xy都是大于等于0的整数，在这个限定条件下有的c是无解的//那么c的上界是多少呢？至多是a*b/*ax+by=c 若ab互质，则xy一定有解且有无穷多个st：x,y >= 0,a 使得ax + by = c 无解的个数有限且Max{c|不定方程无解} = a*a - a - b若ab不互质，则不能保证有解(c&gcd(a,b)==0)有解<==>有无限多个c=>a0*x + a1*x1 + a2*x2 + ...+an*xn = c有解(a0,a1,a2..an互质)否则：若不互质，有无限多个c导致方程无解 有多少个C解不出? => 完全背包问题 1 2 3 4 5 6a0 2 0 √ × √ × √a1 3 0 √ √ × √ √a2 5 0 . . . . .a3 7 √ × . . . .*/#includeusing namespace std ;int n ;int a[101] ;bool f[] ;int gcd(int a,int b){ if(b==0) return a ; return gcd(b,a%b) ;}int main(int argc, char const *argv[]){ scanf("%d",&n) ; f[0] = true ; for (int i = 1; i <= n; ++i) { scanf("%d",&a[i]) ; if(i==1) g=a[i] ; //初始化最大公约数 else g = gcd(a[i],g) ; for (int j = 0; j < 10000; ++j) { if(f[j]) f[j+a[i]] = true ; } } if(g!=1) { printf("INF\n") ; } //统计个数 for (int i = 0； i < 10000； ++i) { if(!f[i]) { ans++ ; cout <不能通过工程设置而省略常用头文件。提交程序时，注意选择所期望的语言类型和编译器类型。————————————————————————————————————————————————————————————*///暴力枚举#includeusing namespace std ;int main(int argc, char const *argv[]){ freopen("/Users/linxu/Projects/lanqiaobei2019/2017_C_A/in7.txt","x2",stdin); int n,k ; int h[100000] ; int w[100000] ; //前缀和 cin >> n >> k ; for (int i = 0; i < n ; ++i) { cin >> h[i] >> w[i] ; } /* int r = 10001 ; int l = 1 ; while(l<=r) { int mid = (l+r)/2 ; int cnt = 0 ; for (int i = 0; i < n; ++i) { cnt += (h[i]/mid)*(w[i]/mid) ; } if(cnt >= k) { int mid = (l+r)/2 ; int cnt = 0 ; } }*/ for (int len = 100000; len >= 1; len--) { int cnt = 0 ; //每个巧克力块都按len来切割 for (int i = 0; i < n; ++i) { cnt += (h[i]/len) * (w[i]/len) ; } if(cnt >= k) { cout << len << endl ; return 0 ; } } return 0;}//二分法 优化#include using namespace std;int main(int argc, const char *argv[]) { freopen("/Users/linxu/Projects/lanqiaobei2019/2017_C_A/in7.txt","x2",stdin); int n, k ; int h[100000] ; int w[100000] ; cin >> n >> k ; for (int i = 0; i < n; ++i) { cin >> h[i] >> w[i] ; } int r = 100001 ; int l=1 ; int ans=0 ; while (l<=r) { int mid=(l+r)/2 ; int cnt = 0 ; //每个巧克力块，都按照len来切割 for (int i = 0; i < n; ++i) { cnt += (h[i] / mid) * (w[i] / mid) ; } if (cnt >= k) { l=mid+1 ; ans=mid ; } else { r=mid-1 ; } } cout<不能通过工程设置而省略常用头文件。数据规模与约定 ————————————————————————————————————————————————————————————*////* 1 2 3 4 5 //枚举i,j //模拟如下： i = 1 j=[1]× j=[1,2]× j=[1,2,3]√ j=[1,2,3,4]√ j=[1,2,3,4,5]× i = 2 j=[2]√ j=[2,3]× j=[2,3,4]× j=[2,3,4,5]√ i = 3 j=[3]× j=[3,4]× j=[3,4,5]√ i = 4 j=[4]√ j=[4,5]× i = 5 j=[5]× //结果为： [1,2,3] [1,2,3,4] [2,3,4,5] [3,4,5] [4] i:1~N (1 <= N, K <= 100000) j:i~N sumi~j : //优化方案：1.前缀和——>树状数组——>区间树 1 2 3 4 5s0：0 1 3 6 10 15si：E(i~k=0)QkSj - Si = i 得出区间和 *///本思路不够高效#includeusing namespace std ;int n,k ;int a[100010] ;int s[100010] ;int main(int argc, char const *argv[]){ cin >> n >> k ; s[0] = 0 ; for (int i = 1; i <= n; i++) { cin >> a[i] ; s[i] = s[i-1] + a[i] ; } long long ans = 0 ; //枚举i,j for (int i = 1; i <= n; i++) { for (int j = i; j <= n; ++j) { //i,j之间的区间和=s[j]-s[i-1] if((s[j]-s[i-1])%k==0) ans++ ; } } cout << ans << endl ; return 0;}//优化方案/*Q:1 2 3 4 5 6S:0 1 3 6 10 15cnt(si%k=0)=3cnt(si%k=1)=3(S2-S1 = S5-S1=S5-S2)%K = 0*/#include#include

Talk is cheap. Show me the code

版权声明：本文内容由网络用户投稿，版权归原作者所有，本站不拥有其著作权，亦不承担相应法律责任。如果您发现本站中有涉嫌抄袭或描述失实的内容，请联系我们jiasou666@gmail.com 处理，核实后本网站将在24小时内删除侵权内容。