2017年蓝桥杯省赛赛前集训题(共14题).doc

第1题：星系炸弹（2015年省赛C/C+B组第2题）在X星系的广袤空间中漂浮着许多X星人造“炸弹”，用来作为宇宙中的路标。每个炸弹都可以设定多少天之后爆炸。比如：阿尔法炸弹2015年1月1日放置，定时为15天，则它在2015年1月16日爆炸。有一个贝塔炸弹，2014年11月9日放置，定时为1000天，请你计算它爆炸的准确日期。请填写该日期，格式为 yyyy-mm-dd 即4位年份2位月份2位日期。比如：2015-02-19请严格按照格式书写。不能出现其它文字或符号。 结果：2017-08-05 解决方法：用Excel拖这个题会了的同学们把上课讲过的，课件上的，其他几道Excel拖动题都做一遍。第2题：（2015年校内选拔赛C/C+B组第3题）如果x的x次幂结果为10（参见【图1.png】），你能计算出x的近似值吗？显然，这个值是介于2和3之间的一个数字。请把x的值计算到小数后6位（四舍五入），并填写这个小数值。注意：只填写一个小数，不要写任何多余的符号或说明。#include #include #include using namespace std;int main()double x;for(x=2;x=3;x+=1e-7)if (abs(pow(x,x)-10)1e-6)coutfixedsetprecision(6)x;return 0;答案：2.506184其他类似题：ALGO-23一元三次方程求解第3题（全排列）注意：全排列必考！全排列必考！全排列必考！重要的事要说三遍！李白打酒（2014年省赛本科B组第3题）话说大诗人李白，一生好饮。幸好他从不开车。 一天，他提着酒壶，从家里出来，酒壶中有酒2斗。他边走边唱： 无事街上走，提壶去打酒。 逢店加一倍，遇花喝一斗。 这一路上，他一共遇到店5次，遇到花10次，已知最后一次遇到的是花，他正好把酒喝光了。 请你计算李白遇到店和花的次序，可以把遇店记为a，遇花记为b。则：babaabbabbabbbb 就是合理的次序。像这样的答案一共有多少呢？请你计算出所有可能方案的个数（包含题目给出的）。答案：14解法1：next_permutation的解法#include#includeusing namespace std;int main()int p15=1,1,1,1,1,2,2,2,2,2,2,2,2,2,2;/1是店，2是花 int sum,cnt=0;dosum=2;for(int i=0;i15;i+)if(pi=1)sum=1;else if(pi=2)sum-;if(sum=0) cnt+;while(next_permutation(p,p+14);/因为最后一次遇到的肯定是花，所以只排前14个数，不排最后一个coutcnt;return 0;解法2：交换大法解法#include using namespace std;#define N 14/因为最后一次肯定是花，所以只排14个数 int cnt;bool ok(int p,int begin,int end)for (int i = begin; i end; i+) if (pi = pend) return false; return true; void perms(int p,int start)int i;if(start=N-1)int sum=2;for(i=0;iN;i+)if(pi=1)sum=1;else if(pi=2)sum-;if(sum=1) cnt+;/倒数第2次，剩1斗酒 return;for(i=start;iN;i+)if (ok(p, start, i) swap(pstart,pi);perms(p,start+1);swap(pstart,pi);int main()int p=1,1,1,1,1,2,2,2,2,2,2,2,2,2;/1是店，2是花 perms(p,0);coutcnt; return 0;解法3：字符串全排列的解法#include#includeusing namespace std;int main()string s = aaaaabbbbbbbbb;/a是店，b是花 int sum,cnt=0;dosum=2;for(int i=0;i15;i+)if(si=a)sum=1;else if(si=b)sum-;if(sum=1) cnt+;while(next_permutation(s.begin(),s.end();coutcnt;return 0;解法4：递归解法#includeusing namespace std;int cnt=0;void f(int a,int b,int c)/a个店，b朵花，c升酒 if(a5|b9) return; f(a+1,b,c*2);f(a,b+1,c-1);if(a=5&b=9&c=1)cnt+;int main()f(0,0,2);coutcntendl;第4题（逻辑推理题）练习系统ADV-143 扶老奶奶过街 一共有5个红领巾，编号分别为A、B、C、D、E，老奶奶被他们其中一个扶过了马路。五个红领巾各自说话：A ：我和E都没有扶老奶奶B ：老奶奶是被C和E其中一个扶过大街的C ：老奶奶是被我和D其中一个扶过大街的D ：B和C都没有扶老奶奶过街E ：我没有扶老奶奶已知五个红领巾中有且只有个人说的是真话，请问是谁扶这老奶奶过了街？若有多个答案，在一行中输出，编号之间用空格隔开例如A B C D E（这显然不是正确答案）解法1-位运算#include using namespace std;#define N 5int main()int i,j,t,aN;for (i = 0x10; i 0; i=1)t=i;for (j = N-1; j = 0; j-)aj = t & 1;t=1;/ABCDE5个变量存5个人的真假话状态，1为真话,0为假话 int A=(a0+a4=0);/A ：我和E都没有扶老奶奶int B=(a2+a4=1);/B ：老奶奶是被C和E其中一个扶过大街的int C=(a2+a3=1);/C ：老奶奶是被我和D其中一个扶过大街的int D=(a1+a2=0);/D ：B和C都没有扶老奶奶过街int E=(a4=0);/E ：我没有扶老奶奶if(A+B+C+D+E=2)/5个人有且只有个人说的是真话for (j = 0; j N; j+)if(aj) coutchar(A+j) ;return 0;解法2-全排列#include#includeusing namespace std;#define N 5 int main()int aN=1,0,0,0,0;/1扶了。0没扶。do/ABCDE5个变量存5个人的真假话状态，1为真话,0为假话 int A=(a0+a4=0);/A ：我和E都没有扶老奶奶int B=(a2+a4=1);/B ：老奶奶是被C和E其中一个扶过大街的int C=(a2+a3=1);/C ：老奶奶是被我和D其中一个扶过大街的int D=(a1+a2=0);/D ：B和C都没有扶老奶奶过街int E=(a4=0);/E ：我没有扶老奶奶if(A+B+C+D+E=2)/5个人有且只有个人说的是真话for (int i = 0; i N; i+)if(ai) coutchar(A+i) ;while(prev_permutation(a,a+N);return 0;解法3-递归（大材小用了）#includeusing namespace std;#define N 5 int aN;/1扶了。0没扶。 void f(int k)int i; if(k=N)int sum=0;for(i=0;iN;i+)sum+=ai;if(sum=1)/只有一个人扶了 /ABCDE5个变量存5个人的真假话状态，1为真话,0为假话 int A=(a0+a4=0);/A ：我和E都没有扶老奶奶int B=(a2+a4=1);/B ：老奶奶是被C和E其中一个扶过大街的int C=(a2+a3=1);/C ：老奶奶是被我和D其中一个扶过大街的int D=(a1+a2=0);/D ：B和C都没有扶老奶奶过街int E=(a4=0);/E ：我没有扶老奶奶if(A+B+C+D+E=2)/5个人有且只有个人说的是真话for (i = 0; i N; i+)if(ai) coutchar(A+i)=0;i-)ak=i;f(k+1);int main()f(0);return 0;第5题：牌型种数（2015年省赛C/C+B组第7题） 小明被劫持到X赌城，被迫与其他3人玩牌。 一副扑克牌（去掉大小王牌，共52张），均匀发给4个人，每个人13张。 这时，小明脑子里突然冒出一个问题： 如果不考虑花色，只考虑点数，也不考虑自己得到的牌的先后顺序，自己手里能拿到的初始牌型组合一共有多少种呢？答案： 3598180解法1:暴力法，比较慢，5秒左右出答案，但不容易出错#include using namespace std;int main()int a1,a2,a3,a4,a5,a6,a7,a8,a9,a10,a11,a12,a13;/13种点数 int cnt=0;for(a1=0;a1=4;a1+)for(a2=0;a2=4;a2+)for(a3=0;a3=4;a3+)for(a4=0;a4=4;a4+)for(a5=0;a5=4;a5+)for(a6=0;a6=4;a6+)for(a7=0;a7=4;a7+)for(a8=0;a8=4;a8+)for(a9=0;a9=4;a9+)for(a10=0;a10=4;a10+)for(a11=0;a11=4;a11+)for(a12=0;a12=4;a12+)for(a13=0;a13=4;a13+)if(a1+a2+a3+a4+a5+a6+a7+a8+a9+a10+a11+a12+a13=13)cnt+;coutcnt;return 0;解法2:DFS+剪枝，秒杀#include using namespace std;int cnt=0;void f(int sum,int n)int i;if(sum13|(13-n)*4+sum13) return;/剪枝 if(sum=13) cnt+;return;for(i=0;i=4;i+)f(sum+i,n+1);int main()f(0,0);coutcnt;return 0;第6题：单位分数（组合问题）（2015年校内选拔赛C/C+B组第6题） 形如：1/a 的分数称为单位分数。 可以把1分解为若干个互不相同的单位分数之和。 例如： 1 = 1/2 + 1/3 + 1/9 + 1/18 1 = 1/2 + 1/3 + 1/10 + 1/15 1 = 1/3 + 1/5 + 1/7 + 1/9 + 1/11 + 1/15 + 1/35 + 1/45 + 1/231 等等，类似这样的分解无穷无尽。 我们增加一个约束条件：最大的分母必须不超过30 请你求出分解为n项时的所有不同分解法。 数据格式要求： 输入一个整数n，表示要分解为n项（n12） 输出分解后的单位分数项，中间用一个空格分开。 每种分解法占用一行，行间的顺序按照分母从小到大排序。 例如， 输入： 4 程序应该输出： 1/2 1/3 1/8 1/24 1/2 1/3 1/9 1/18 1/2 1/3 1/10 1/15 1/2 1/4 1/5 1/20 1/2 1/4 1/6 1/12 再例如， 输入： 5 程序应该输出： 1/2 1/3 1/12 1/21 1/28 1/2 1/4 1/6 1/21 1/28 1/2 1/4 1/7 1/14 1/28 1/2 1/4 1/8 1/12 1/24 1/2 1/4 1/9 1/12 1/18 1/2 1/4 1/10 1/12 1/15 1/2 1/5 1/6 1/12 1/20 1/3 1/4 1/5 1/6 1/20 资源约定： 峰值内存消耗 256M CPU消耗 2000ms题目分析：题目有点坑。题意说不超过30，那理应可以等于30的，但是当n=5时，1/2 1/3 1/12 1/20 1/30也应该是正确的。可是，题目给的答案却没有这个解，所以，不能等于30注意一定要剪枝，不剪的话会超过2000ms，剪枝之后大约428ms#include #include using namespace std;int a11;/n12int n;void C(int begin,int m,double sum)/从begin开始，选n个数中的第m个，已选出的数的和是sumint i;if(m1)/剪枝，很重要，不剪的话会超过2000ms return;if(m=n)if(abs(sum-1)1e-9)for(i=0;in;i+)cout1/ai;if(i!=n-1)cout ;coutendl;return;for(i=begin;in;C(2,0,0);/从2开始，选n个数中的第0个，已选出的数的和是0 return 0;第7题（背包问题）练习系统ALGO-115 算法训练 和为T#includeusing namespace std;long long a100;int flag100; long long T;int n;int cnt;bool ok()for(int i=0;i=0;i-)if(flagi)coutai ;coutn;for(i=n-1;i=0;i-)cinai;cinT;f(0,0);coutcnt;return 0;第8题（高精度整数和浮点数）两个题，分别用Java的BigInteger和BigDecimal来做。因为只求最后结果，如果用C/C+很麻烦，而用JAVA BigInteger和BigDecimal来做很简单，所以不论C/C+还是JAVA组，都要学会以下两道题的JAVA解法。1. 梅森素数(6分)2013预赛Java A组第3题如果一个数字的所有真因子之和等于自身，则称它为“完全数”或“完美数” 例如：6 = 1 + 2 + 3 28 = 1 + 2 + 4 + 7 + 14 早在公元前300多年，欧几里得就给出了判定完全数的定理： 若 2n - 1 是素数，则 2(n-1) * (2n - 1) 是完全数。 其中 表示“乘方”运算，乘方的优先级比四则运算高，例如：23 = 8， 2 * 23 = 16, 23-1 = 7 但人们很快发现，当n很大时，判定一个大数是否为素数到今天也依然是个难题。 因为法国数学家梅森的猜想，我们习惯上把形如：2n - 1 的素数称为：梅森素数。 截止2013年2月，一共只找到了48个梅森素数。 新近找到的梅森素数太大，以至于难于用一般的编程思路窥其全貌，所以我们把任务的难度降低一点： 1963年，美国伊利诺伊大学为了纪念他们找到的第23个梅森素数 n=11213，在每个寄出的信封上都印上了“211213-1 是素数”的字样。 211213 - 1 这个数字已经很大(有3000多位)，请你编程求出这个素数的十进制表示的最后100位。答案：85867185275866024396023352835139449800643270302781042241449718836805416897847962673914760876963921912. 黄金连分数(2013省赛题)import java.math.BigDecimal;public class Main public static void main(String args) BigDecimal b=BigDecimal.ONE; for(int i=0;i500;i+) b=b.add(BigDecimal.ONE); b=BigDecimal.ONE.divide(b,101,BigDecimal.ROUND_HALF_UP); System.out.println(b.setScale(100,BigDecimal.ROUND_HALF_UP); 第9题（进制转换）1. 十进制转十六进制(递归), 练习系统-基础练习-BASIC-10问题描述十六进制数是在程序设计时经常要使用到的一种整数的表示方式。它有0,1,2,3,4,5,6,7,8,9,A,B,C,D,E,F共16个符号，分别表示十进制数的0至15。十六进制的计数方法是满16进1，所以十进制数16在十六进制中是10，而十进制的17在十六进制中是11，以此类推，十进制的30在十六进制中是1E。给出一个非负整数，将它表示成十六进制的形式。输入格式输入包含一个非负整数a，表示要转换的数。0=a=2147483647输出格式输出这个整数的16进制表示样例输入30样例输出1E#include using namespace std;string s=0123456789ABCDEF;void f(int n) if(n=16) f(n4); coutn; f(n); return 0;2./十六进制转十进制 /练习系统-基础练习-BASIC-11问题描述从键盘输入一个不超过8位的正的十六进制数字符串，将它转换为正的十进制数后输出。注：十六进制数中的1015分别用大写的英文字母A、B、C、D、E、F表示。样例输入FFFF样例输出65535#include using namespace std;int main()int i,t;unsigned sum=0;string s;cins;for(i=0;si;i+)t=si=9?si-0:si-A+10;sum=(sum4)+t;coutsum;return 0;第10题（排序）ADV-13最小乘积(提高型)#include #include using namespace std;bool cmp(int x,int y) return xy;int main() int a1000,b1000; int T,n,i; cinT; while(T-) cinn; for(i=0;iai; for(i=0;ibi; sort(a,a+n); sort(b,b+n,cmp); int sum=0; for(i=0;in;i+) sum+=ai*bi; coutsumendl; return 0;第11题（打印题）上三角，2011年省赛题#include int M2020;int idx=1;void tri(int r,int c,int n)/从坐标(r,c)的元素开始三角填数，三角形上边长为nint i;if(n=0) return;for(i=0;in;i+)/填充三角形上边长Mrc+i=idx+;for(i=1;in;i+)/填充三角形斜边长Mr+ic+n-1-i=idx+;for(i=2;in;i+)/填充三角形左边长Mr+n-ic=idx+;tri(r+1,c+1,n-3);/递归int main()int n,i,j;scanf(%d,&n);tri(0,0,n);for(i=0;in;i+)for(j=0;jn-i;j+)printf(%4d,Mij);/每个数据宽度为4，右对齐。printf(n);return 0;第12题（求余运算符的妙用）移动距离（2015年省赛C/C+B组第8题） X星球居民小区的楼房全是一样的，并且按矩阵样式排列。其楼房的编号为1,2,3. 当排满一行时，从下一行相邻的楼往反方向排号。 比如：当小区排号宽度为6时，开始情形如下： 1 2 3 4 5 6 12 11 10 9 8 7 13 14 15 . 我们的问题是：已知了两个楼号m和n，需要求出它们之间的最短移动距离（不能斜线方向移动） 输入为3个整数w m n，空格分开，都在1到10000范围内 w为排号宽度，m,n为待计算的楼号。 要求输出一个整数，表示m n 两楼间最短移动距离。 例如： 用户输入： 6 8 2 则，程序应该输出： 4 再例如： 用户输入： 4 7 20 则，程序应该输出： 5有同学居然说，前面7题做了一个小时。第8题做了2个小时没做出来。掌握了求余运算课件里的单变量矩阵坐标转双变量的方法，就很容易了#include #include using namespace std;int main()int w,m,n;int i,j;/m的行号列号 int x,y;/n的行号列号 cinwmn;m-,n-;/题目要求的序号从1开始，减一表示从0开始 i=m/w;/m的行号j=m%w;/m的列号if(i%2=1) j=w-1-j;/奇数列要调整 x=n/w;/n的行号 y=n%w;/n的列号if(x%2=1) y=w-1-y;/奇数列要调整coutabs(i-x)+abs(j-y);return 0;第13题（回溯算法） “数独”是当下炙手可热的智力游戏。一般认为它的起源是“拉丁方块”，是大数学家欧拉于1783年发明的。 如图1.jpg所示：6x6的小格被分为6个部分（图中用不同的颜色区分）,每个部分含有6个小格（以下也称为分组）。 开始的时候，某些小格中已经填写了字母（ABCDEF之一）。需要在所有剩下的小格中补填字母。 全部填好后，必须满足如下约束： 1. 所填字母只允许是A,B,C,D,E,F 中的某一个。 2. 每行的6个小格中，所填写的字母不能重复。 3. 每列的6个小格中，所填写的字母不能重复。 4. 每个分组（参见图中不同颜色表示）包含的6个小格中，所填写的字母不能重复。 为了表示上的方便，我们用下面的6阶方阵来表示图1.jpg对应的分组情况（组号为05）： 000011 022013 221113 243333 244455 445555 用下面的数据表示其已有字母的填写情况： 02C 03B 05A 20D 35E 53F 很明显，第一列表示行号，第二列表示列号，第三列表示填写的字母。行号、列号都从0开始计算。 一种可行的填写方案（此题刚好答案唯一）为： E F C B D A A C E D F B D A B E C F F B D C A E B D F A E C C E A F B D 你的任务是：编写程序，对一般的拉丁方块问题求解，如果多解，要求找到所有解。 【输入、输出格式要求】 用户首先输入6行数据，表示拉丁方块的分组情况。 接着用户输入一个整数n (n36), 表示接下来的数据行数 接着输入n行数据，每行表示一个预先填写的字母。 程序则输出所有可能的解（各个解间的顺序不重要）。 每个解占用7行。 即，先输出一个整数，表示该解的序号（从1开始），接着输出一个6x6的字母方阵，表示该解。 解的字母之间用空格分开。 如果找不到任何满足条件的解，则输出“无解” 例如：用户输入： 000011 022013 221113 243333 244455 445555 6 02C 03B 05A 20D 35E 53F 则程序输出： 1 E F C B D A A C E D F B D A B E C F F B D C A E B D F A E C C E A F B D 再如，用户输入： 001111 002113 022243 022443 544433 555553 7 04B 05A 13D 14C 24E 50C 51A 则程序输出： 1 D C E F B A E F A D C B A B F C E D B E D A F C F D C B A E C A B E D F 2 D C E F B A E F A D C B A D F B E C B E C A F D F B D C A E C A B E D F 3 D C F E B A A E B D C F F D A C E B B F E A D C E B C F A D C A D B F E 4 D C F E B A B E A D C F A D C F E B F B E A D C E F B C A D C A D B F E 5 D C F E B A E F A D C B A B C F E D B E D A F C F D B C A E C A E B D F 6 D C F E B A E F A D C B A B D F E C B E C A F D F D B C A E C A E B D F 7 D C F E B A E F A D C B A D B F E C B E C A F D F B D C A E C A E B D F 8 D C F E B A F E A D C B A D B C E F B F E A D C E B C F A D C A D B F E 9 D C F E B A F E A D C B A F C B E D B D E A F C E B D C A F C A B F D E#include using namespace std;char a66;/存放分组情况char c66;/存放数独int cnt;bool ok(int row,int col)int i,j;for(i=0;i6;i+)/检查行if(crowi=crowcol&i!=col) return false;for(i=0;i6;i+)/检查列if(cicol=crowcol&i!=row) return false;for(i=0;i6;i+)/检查同一区域for(j=0;j6;j+)if(aij=arowcol&cij=crowcol&!(i=row&j=col) return false;return true;void sudoku(int idx)int i,j;char k;if(idx=36) cout+cntendl;for(i = 0; i 6; i+)for(j = 0; j 6; j+) coutcij; if(j!=5) cout ;coutendl;return;int row = idx / 6; int col = idx % 6; if(crowcol=0)for(k=A;k=F;k+)crowcol=k;/填字母if(ok(row,col) sudoku(idx+1);/如果不冲突，则继续递归填下一个crowcol=0;else/遇到预先填好的字母sudoku(idx+1);int main()int i,j,n;string s;for(i=0;iai;cinn;while(n-)cins;int x=s0-0;int y=s1-0;cxy=s2;sudoku(0);if(cnt=0) cout无解endl;return 0;第14题（bfs算法）ADV-147 算法提高 学霸的迷宫 问题描述 学霸抢走了大家的作业，班长为了帮同学们找回 作业，决定去找学霸决斗。但学霸为了不要别人打扰，住在一个城堡里，城堡外面是一个二维的格子迷宫，要进城堡必须得先通过迷宫。因为班长还有妹子要陪，磨 刀不误砍柴功，他为了节约时间，从线人那里搞到了迷宫的地图，准备提前计算最短的路线。可是他现在正向妹子解释