蓝桥杯决赛题答案(2).doc

2011年暑假蓝桥杯决赛题附答案1 四方定理数论中有著名的四方定理：所有自然数至多只要用四个数的平方和就可以表示。我们可以通过计算机验证其在有限范围的正确性。对于大数，简单的循环嵌套是不适宜的。下面的代码给出了一种分解方案。请仔细阅读，填写空缺的代码（下划线部分）。注意：请把填空的答案（仅填空处的答案，不包括题面）存入考生文件夹下对应题号的“解答.txt”中即可。直接写在题面中不能得分。#include #include using namespace std; int f(int n, int a, int idx) if(n=0) return 1; / 填空1 if(idx=4) return 0; for(int i=(int)sqrt(double)n); i=1; i-) aidx = i; if(f(n-i*i,a,idx+1) return 1; / 填空2 return 0; int main(int argc, char* argv) for(;) int number; printf(输入整数(110亿)：); scanf(%d,&number); int a = 0,0,0,0; int r = f(number, a, 0); printf(%d: %d %d %d %dn, r, a0, a1, a2, a3); return 0; 2 加密在对文本进行简单加密的时候，可以选择用一个n位的二进制数，对原文进行异或运算。解密的方法就是再执行一次同样的操作。加密过程中n位二进制数会循环使用。并且其长度也可能不是8的整数倍。下面的代码演示了如何实现该功能。请仔细阅读，填写空缺的代码（下划线部分）。注意：请把填空的答案（仅填空处的答案，不包括题面）存入考生文件夹下对应题号的“解答.txt”中即可。直接写在题面中不能得分。#include #include #include using namespace std; void f(char* buf, unsigned char* uckey, int n) int i; for(i=0; in; i+) bufi = bufi uckeyi; int main(int argc, char* argv) char p = abcd中国人123; / 待加密串 char* key = 11001100010001110; /以串的形式表达的密匙，运算时要转换为按位存储的形式。 int np = strlen(p); int nk = strlen(key); unsigned char* uckey = (unsigned char*)malloc(np); / 密匙串需要按位的形式循环拼入 uckey中 int i; for(i=0; inp*8; i+) if(keyi%nk=1) uckeyi/8=uckeyi/8|(1(i%nk); / 填空1 else uckeyi/8=uckeyi/8&(1(i%nk); / 填空2 f(p, uckey, strlen(p); printf(%sn, p); f(p, uckey, strlen(p); printf(%sn, p); free(uckey); return 0; 3 公倍数为什么1小时有60分钟，而不是100分钟呢？这是历史上的习惯导致。但也并非纯粹的偶然：60是个优秀的数字，它的因子比较多。事实上，它是1至6的每个数字的倍数。即1,2,3,4,5,6都是可以除尽60。我们希望寻找到能除尽1至n的的每个数字的最小整数。不要小看这个数字，它可能十分大，比如n=100, 则该数为：69720375229712477164533808935312303556800请编写程序，实现对用户输入的 n （n100）求出1n的最小公倍数。例如：用户输入：6程序输出：60用户输入：10程序输出：2520要求考生把所有函数写在一个文件中。调试好后，存入与考生文件夹下对应题号的“解答.txt”中即可。相关的工程文件不要拷入。 对于编程题目，要求选手给出的解答完全符合ANSI C标准，不能使用c+特性；不能使用诸如绘图、中断调用等硬件相关或操作系统相关的API。#include #include #include using namespace std; int main() int num101; int result45; int n; while(scanf(%d,&n)&n0) memset(result,0,sizeof(result); for (int i=1;i101;+i) numi=i; for (int i=2;in+1;+i) for (int j=1;ji-1;+j) if (numi%numj=0) numi/=numj; result1=6; for (int i=4;in+1;+i) for (int j=1;j43;+j) resultj*=numi; for (int j=1;j0;-i) if (resulti!=0) k=i; break; for (int i=k;i0;-i) printf(%d,resulti); printf(n); return 0; 4 地铁换乘为解决交通难题，某城市修建了若干条交错的地铁线路，线路名及其所属站名如stations.txt所示。线1苹果园.四惠东线2西直门车公庄.建国门线4.其中第一行数据为地铁线名，接下来是该线的站名。当遇到空行时，本线路站名结束。下一行开始又是一条新线.直到数据结束。如果多条线拥有同一个站名，表明：这些线间可以在该站换车。为引导旅客合理利用线路资源，解决交通瓶颈问题，该城市制定了票价策略：1. 每条线路可以单独购票，票价不等。2. 允许购买某些两条可换乘的线路的联票。联票价格低于分别购票。单线票价和联合票价如 price.txt 所示。线1 180.线13 114线1,线2 350线1,线10 390.每行数据表示一种票价线名与票价间用空格分开。如果是联票，线名间用逗号分开。联票只能包含两条可换乘的线路。现在的问题是：根据这些已知的数据，计算从A站到B站最小花费和可行的换乘方案。比如，对于本题目给出的示例数据如果用户输入：五棵松,奥体中心程序应该输出：-(线1,线10)-线8 = 565如果用户输入：五棵松,霍营程序应该输出：-线1-(线4,线13) = 440可以看出，用户输入的数据是：起始站，终到站，用逗号分开。程序输出了购票方案，在括号中的表示联票，短横线(-)用来分开乘车次序。等号后输出的是该方案的花费数值。请编程解决上述问题。注意：1. 我们测试您的程序时，所用数据与题目中的示例数据不同，但格式完全一样。2. 当多个方案有相同的最小花费，输出任意一个方案即可。要求考生把所有函数写在一个文件中。调试好后，存入与考生文件夹下对应题号的“解答.txt”中即可。相关的工程文件不要拷入。 对于编程题目，要求选手给出的解答完全符合ANSI C标准，不能使用c+特性；不能使用诸如绘图、中断调用等硬件相关或操作系统相关的API。文件price.txt内容如下：线1 180线2 250线4 160线5 270线8 175线10 226线13 114线1,线2 350线1,线10 390线1,线5 410线1,线4 330线10,线13 310线2,线5 390线4,线10 370线4,线13 260文件station.txt内容如下：线1苹果园古城路八角游乐园八宝山玉泉路五棵松万寿路公主坟军事博物馆木樨地南礼士路复兴门西单天安门西天安门东王府井东单建国门永安里国贸大望路四惠四惠东线2西直门车公庄阜成门复兴门长椿街宣武门和平门前 门崇文门北京站建国门朝阳门东四十条东直门雍和宫安定门鼓楼大街积水潭线4公益西桥角门西马家堡北京南站陶然亭菜市口宣武门西单灵境胡同西四平安里新街口西直门动物园国家图书馆魏公村人民大学海淀黄庄中关村北京大学东门圆明园西苑北宫门安河桥北线5天通苑北天通苑天通苑南立水桥立水桥南北苑路北大屯路东惠新西街北口惠新西街南口和平西桥和平里北街雍和宫北新桥张自忠路东四灯市口东单崇文门磁器口天坛东门蒲黄榆刘家窑宋家庄线8森林公园南门奥林匹克公园奥体中心北土城线10巴沟苏州街海淀黄庄知春里知春路西土城牡丹园健德门北土城安贞门惠新西街南口芍药居太阳宫三元桥亮马桥农业展览馆团结湖呼家楼金台夕照国贸双井劲松线13西直门大钟寺知春路五道口上地西二旗龙泽回龙观霍营立水桥北苑望京西芍药居光熙门柳芳东直门5 连通问题in.bmp 文件如下：t1.bmp文件如下：BMP是常见的图像存储格式。如果用来存黑白图像（颜色深度=1），则其信息比较容易读取。与之相关的数据：（以下偏移均是从文件头开始）偏移：10字节, 长度4字节： 图像数据真正开始的位置。偏移：18字节, 长度4字节： 位图的宽度，单位是像素。偏移：22字节, 长度4字节： 位图的高度，单位是像素。从图像数据开始处，每个像素用1个二进制位表示。从图片的底行开始，一行一行向上存储。Windows规定图像文件中一个扫描行所占的字节数必须是4字节的倍数，不足的位均以 0 填充。例如，图片宽度为45像素，实际上每行会占用8个字节。可以通过Windows自带的画图工具生成和编辑二进制图像。需要在“属性”中选择“黑白”，指定为二值图像。可能需要通过 查看 | 缩放 | 自定义. 把图像变大比例一些，更易于操作。图像的左下角为图像数据的开始位置。白色对应1，黑色对应0我们可以定义：两个点距离如果小于2个像素，则认为这两个点连通。也就是说：以一个点为中心的九宫格中，围绕它的8个点与它都是连通的。如：t1.bmp 所示，左下角的点组成一个连通的群体；而右上角的点都是孤立的。程序的目标是：根据给定的黑白位图，分析出所有独立连通的群体，输出每个连通群体的面积。所谓面积，就是它含有的像素的个数。输入数据固定存在in.bmp中。如示例的in.bmp,程序应该输出：128152133该输出表示：共有4个连通群体。输出的连通体面积间的顺序可以随意。请编程解决上述问题。我们测试程序的时候，会使用不同的in.bmp文件。要求考生把所有函数写在一个文件中。调试好后，存入与考生文件夹下对应题号的“解答.txt”中即可。相关的工程文件不要拷入。 对于编程题目，要求选手给出的解答完全符合ANSI C标准，不能使用c+特性；不能使用诸如绘图、中断调用等硬件相关或操作系统相关的API。spanstyle=font-size:16px;#includeWindows.h#includestdio.h #includestring.h #includemalloc.h unsignedchar*pBmpBuf;/读入图像数据的指针 intbmpWidth;/图像的宽 intbmpHeight;/图像的高 RGBQUAD*pColorTable;/颜色表指针 intbiBitCount;/图像类型，每像素位数 boolreadBmp(char*bmpName)/二进制读方式打开指定的图像文件 FILE*fp=fopen(bmpName,rb);if(fp=0)return0;/跳过位图文件头结构BITMAPFILEHEADER fseek(fp,sizeof(BITMAPFILEHEADER),0);/定义位图信息头结构变量，读取位图信息头进内存，存放在变量head中 BITMAPINFOHEADERhead;fread(&head,sizeof(BITMAPINFOHEADER),1,fp);/获取图像宽、高、每像素所占位数等信息 bmpWidth=head.biWidth;bmpHeight=head.biHeight;biBitCount=head.biBitCount;/定义变量，计算图像每行像素所占的字节数（必须是4的倍数） intlineByte=(bmpWidth*biBitCount/8+3)/4*4;/灰度图像有颜色表，且颜色表表项为256 if(biBitCount=8)/申请颜色表所需要的空间，读颜色表进内存 pColorTable=newRGBQUAD256;fread(pColorTable,sizeof(RGBQUAD),256,fp);/申请位图数据所需要的空间，读位图数据进内存 pBmpBuf=newunsignedcharlineByte*bmpHeight;fread(pBmpBuf,1,lineByte*bmpHeight,fp);/关闭文件 fclose(fp);return1;voidmain()charinFileName90,out