蓝桥杯练习题库 3算法训练题

1、算法训练 图形显示  时间限制：1.0s   内存限制：512.0MB      查看参考代码 锦囊1锦囊2锦囊3问题描述编写一个程序，首先输入一个整数，例如5，然后在屏幕上显示如下的图形（5表示行数）：* * * * * * * * * * *#include<stdio.h>int main()int i,j,a100100,n; while(scanf("%d",&n)!=EOF) for(i=0;i<n;i+) for(j=0;j<n-i;j+) printf("*"

2、;); if(j!=n-i-1) printf(" "); if(j=n-1-i) printf("n");   算法训练 排序  时间限制：1.0s   内存限制：512.0MB      查看参考代码 锦囊1锦囊2锦囊3问题描述编写一个程序，输入3个整数，然后程序将对这三个整数按照从大到小进行排列。输入格式：输入只有一行，即三个整数，中间用空格隔开。输出格式：输出只有一行，即排序后的结果。输入输出样例样例输入9 2 30样例输出30 9 2#include<stdio.h>#in

3、clude<stdlib.h>#define num 100int main(void)int i,j,t,a3=0;for (i=0;i<3;i+)scanf("%d",&ai);for (i=0;i<3;i+)for (j=i;j<3;j+)if (ai<=aj)t=ai;ai=aj;aj=t;for (i=0;i<3;i+)printf("%d",ai);if(i!=2) printf(" ");printf("n");return 0;  算法训练

4、 2的次幂表示  时间限制：1.0s   内存限制：512.0MB      查看参考代码 锦囊1锦囊2锦囊3问题描述任何一个正整数都可以用2进制表示，例如：137的2进制表示为10001001。将这种2进制表示写成2的次幂的和的形式，令次幂高的排在前面，可得到如下表达式：137=27+23+20现在约定幂次用括号来表示，即ab表示为a（b）此时，137可表示为：2（7）+2（3）+2（0）进一步：7=22+2+20 （21用2表示）3=2+20 所以最后137可表示为：2（2（2）+2+2（0）+2（2+2（0）+2（0）又如：1315=21

5、0+28+25+2+1所以1315最后可表示为：2（2（2+2（0）+2）+2（2（2+2（0）+2（2（2）+2（0）+2+2（0）输入格式正整数（1<=n<=20000）输出格式符合约定的n的0，2表示（在表示中不能有空格）样例输入137样例输出2(2(2)+2+2(0)+2(2+2(0)+2(0)样例输入1315样例输出2(2(2+2(0)+2)+2(2(2+2(0)+2(2(2)+2(0)+2+2(0)提示用递归实现会比较简单，可以一边递归一边输出#include <stdio.h>int l=0;char temp1000=0;void show(int n)

6、 if(n=0) templ='0'l+;return ; if(n=2) templ='2',l+;return ; int a15=0,i=0,j; while(n!=0) ai=n%2; n/=2; i+; for(j=i-1;j>=0;j-) if(aj=1) if(j=1) if(templ-1=')' | templ-1='2' ) templ='+'l+;templ='2'l+; else if(templ-1=')' | templ-1='2'

7、) templ='+'l+;templ='2'l+;templ='('l+; show(j); templ=')'l+; int main()int n;scanf("%d",&n);show(n);printf("%s",temp); return 0;算法训练 前缀表达式  时间限制：1.0s   内存限制：512.0MB      查看参考代码 锦囊1锦囊2锦囊3问题描述编写一个程序，以字符串方式输入一个前缀表达式，然后计算它的

8、值。输入格式为：“运算符 对象1 对象2”，其中，运算符为“+”（加法）、“-”（减法）、“*”（乘法）或“/”（除法），运算对象为不超过10的整数，它们之间用一个空格隔开。要求：对于加、减、乘、除这四种运算，分别设计相应的函数来实现。输入格式：输入只有一行，即一个前缀表达式字符串。输出格式：输出相应的计算结果（如果是除法，直接采用c语言的“/”运算符，结果为整数）。输入输出样例样例输入+ 5 2样例输出7#include<stdio.h>int main() int a2; int i,j; char c=getchar(); for(i=0;i<2;i+) scanf(&

9、quot;%d",&ai); if(c='+') j=a0+a1; else if(c='-') j=a0-a1; else if(c='*') j=a0*a1; else if(c='/') j=a0/a1; printf("%d",j); return 0;算法训练 Anagrams问题  时间限制：1.0s   内存限制：512.0MB      查看参考代码 锦囊1锦囊2锦囊3问题描述Anagrams指的是具有如下特性的两个单词：在这两

10、个单词当中，每一个英文字母（不区分大小写）所出现的次数都是相同的。例如，“Unclear”和“Nuclear”、“Rimon”和“MinOR”都是Anagrams。编写一个程序，输入两个单词，然后判断一下，这两个单词是否是Anagrams。每一个单词的长度不会超过80个字符，而且是大小写无关的。输入格式：输入有两行，分别为两个单词。输出格式：输出只有一个字母Y或N，分别表示Yes和No。输入输出样例样例输入UnclearNuclear样例输出Y#include <stdio.h>void sort(char a,int len)int i,j,max;for(i=0;i<le

11、n;i+)max=i;for(j=i+1;j<len;j+)if(aj>amax) max=j;j=ai;ai=amax;amax=j;void strtoupper(char a,int len)int i;for(i=0;i<len;i+)if(ai>='a' && ai<='z') ai-=32;int mystrcmp(char a,int l1,char b,int l2)if(l1!=l2) return 0;int i;for(i=0;i<l1;i+)if(ai!=bi) return 0;ret

12、urn 1;int mystrlen(char *p)int l=0;while(*p+!=0)l+;return l;int main()char s11000=0,s21000=0;int l1,l2;scanf("%s%s",s1,s2);l1=mystrlen(s1);l2=mystrlen(s2);strtoupper(s1,l1);strtoupper(s2,l2);sort(s1,l1);sort(s2,l2); if(mystrcmp(s1,l1,s2,l2) printf("Y"); else printf("N")

13、;return 0;算法训练 出现次数最多的整数  时间限制：1.0s   内存限制：512.0MB      查看参考代码 锦囊1锦囊2锦囊3问题描述编写一个程序，读入一组整数，这组整数是按照从小到大的顺序排列的，它们的个数N也是由用户输入的，最多不会超过20。然后程序将对这个数组进行统计，把出现次数最多的那个数组元素值打印出来。如果有两个元素值出现的次数相同，即并列第一，那么只打印比较小的那个值。输入格式：第一行是一个整数N，N £ 20；接下来有N行，每一行表示一个整数，并且按照从小到大的顺序排列。输出格式：输出只有一行，即出现

14、次数最多的那个元素值。输入输出样例样例输入5100150150200250样例输出150#include <stdio.h>int main()int n,i,j,t,max=1,num=0;scanf("%d",&n);if(n>0)int an;for(i=0;i<n;i+)scanf("%d",a+i);j=num=a0;t=1;for(i=1;i<n;i+)if(ai=j)+t;if(t>max)max=t;num=ai; elset=1;j=ai;printf("%d",num);

15、return 0;  算法训练 字串统计  时间限制：1.0s   内存限制：512.0MB      查看参考代码 锦囊1锦囊2锦囊3问题描述给定一个长度为n的字符串S，还有一个数字L，统计长度大于等于L的出现次数最多的子串（不同的出现可以相交），如果有多个，输出最长的，如果仍然有多个，输出第一次出现最早的。输入格式第一行一个数字L。第二行是字符串S。L大于0，且不超过S的长度。输出格式一行，题目要求的字符串。输入样例1：4bbaabbaaaaa输出样例1：bbaa输入样例2：2bbaabbaaaaa输出样例2：aa数据规模和约定n

16、<=60S中所有字符都是小写英文字母。提示枚举所有可能的子串，统计出现次数，找出符合条件的那个#include<stdio.h>#include<string.h>int main()char S1000,str10001000,temp100,out100;int L,i=0,s,otongji=0,ttongji,a,b,c;scanf("%d%c%c",&L,&S0,&S0);while(Si!='n') scanf("%c",&Si+1); i+; Si = '

17、0' for(s=i+1;L<=s;L+) for(a=0;a<s+1-L;a+)/赋值 for(b = 0;b < L;b+) strab=Sa+b; strab = '0' for(i = 0;i < a-1;)/比较 for(b = 0;b<a;b+) if(strb0!='0') for(c = 0;c<L;c+) tempc=strbc; tempc = '0' ttongji = 1; i+; strb0 = '0' break; for(b+;b<a;b+) if(!

18、strcmp(strb,temp) ttongji+; i+; strb0 = '0' if(ttongji > otongji|(ttongji=otongji&&strlen(temp)>strlen(out) strcpy(out,temp); otongji = ttongji; i = 0; while(outi != '0') printf("%c",outi); i+; getchar();return 0;算法训练 矩阵乘法  时间限制：1.0s   内存限制：512.0MB&#

19、160;     查看参考代码 锦囊1锦囊2锦囊3问题描述输入两个矩阵，分别是m*s，s*n大小。输出两个矩阵相乘的结果。输入格式第一行，空格隔开的三个正整数m,s,n（均不超过200）。接下来m行，每行s个空格隔开的整数，表示矩阵A（i，j）。接下来s行，每行n个空格隔开的整数，表示矩阵B（i，j）。输出格式m行，每行n个空格隔开的整数，输出相乘後的矩阵C（i，j）的值。样例输入2 3 21 0 -11 1 -30 31 23 1样例输出-3 2-8 2提示矩阵C应该是m行n列，其中C(i,j)等于矩阵A第i行行向量与矩阵B第j列列向量的内积。例如样例中C(1,1)=(1

20、,0,-1)*(0,1,3) = 1 * 0 +0*1+(-1)*3=-3 # include<stdio.h>int main()int m,s,n,i,j,k,a200200,b200200,c200200;scanf("%d%d%d",&m,&s,&n);for(i=1;i<=m;i+)for(j=1;j<=s;j+)scanf("%d",&aij);for(i=1;i<=s;i+)for(j=1;j<=n;j+)scanf("%d",&bij);for

21、(i=1;i<=m;i+)for(j=1;j<=n;j+)cij=0;for(i=1;i<=m;i+)for(j=1;j<=n;j+)for(k=1;k<=s;k+)cij=cij+aik*bkj;for(i=1;i<=m;i+)for(j=1;j<=n;j+)printf("%d ",cij);printf("n");return 0;算法训练 大小写转换  时间限制：1.0s   内存限制：512.0MB      查看参考代码 锦囊1锦囊2锦囊3问题描述编写

22、一个程序，输入一个字符串（长度不超过20），然后把这个字符串内的每一个字符进行大小写变换，即将大写字母变成小写，小写字母变成大写，然后把这个新的字符串输出。输入格式：输入一个字符串，而且这个字符串当中只包含英文字母，不包含其他类型的字符，也没有空格。输出格式：输出经过转换后的字符串。输入输出样例样例输入AeDb样例输出aEdB#include <stdio.h>int main()int i;char ch100;gets(ch);i=0;while(chi!='0')if(chi<='z'&&chi>='a

23、9;)chi-=32;else chi+=32;i+;puts(ch);return 0;算法训练 动态数组使用  时间限制：1.0s   内存限制：512.0MB      查看参考代码 锦囊1锦囊2锦囊3从键盘读入n个整数，使用动态数组存储所读入的整数，并计算它们的和与平均值分别输出。要求尽可能使用函数实现程序代码。平均值为小数的只保留其整数部分。样例输入53 4 0 0 2样例输出9 1样例输入73 2 7 5 2 9 1样例输出29 4#include <stdio.h>int main()int i,n,a100,b100

24、,sum=0,avg=0;scanf("%d",&n);for(i=0;i<n;i+)scanf("%d",&bi);ai=bi;sum=sum+ai;avg=sum/n;printf("%d %dn",sum,avg);return 0;算法训练 删除数组零元素  时间限制：1.0s   内存限制：512.0MB      查看参考代码 锦囊1锦囊2锦囊3从键盘读入n个整数放入数组中，编写函数CompactIntegers，删除数组中所有值为0的元素，其后元素向

25、数组首端移动。注意，CompactIntegers函数需要接受数组及其元素个数作为参数，函数返回值应为删除操作执行后数组的新元素个数。输出删除后数组中元素的个数并依次输出数组元素。样例输入: （输入格式说明：5为输入数据的个数，3 4 0 0 2 是以空格隔开的5个整数）53 4 0 0 2样例输出:（输出格式说明：3为非零数据的个数，3 4 2 是以空格隔开的3个非零整数）33 4 2样例输入70 0 7 0 0 9 0样例输出27 9样例输入30 0 0样例输出0算法训练 最小乘积(基本型)  时间限制：1.0s   内存限制：512.0MB   

26、  查看参考代码 锦囊1锦囊2锦囊3问题描述给两组数，各n个。请调整每组数的排列顺序，使得两组数据相同下标元素对应相乘，然后相加的和最小。要求程序输出这个最小值。例如两组数分别为:1 3-5和-2 4 1那么对应乘积取和的最小值应为：(-5) * 4 + 3 * (-2) + 1 * 1 = -25输入格式第一个行一个数T表示数据组数。后面每组数据，先读入一个n，接下来两行每行n个数，每个数的绝对值小于等于1000。n<=8,T<=1000输出格式一个数表示答案。样例输入231 3 -5-2 4 151 2 3 4 51 0 1 0 1样例输出-256#include&l

27、t;stdio.h>void sort1(int *a,int n)int i,j;int tmp;for(i=0;i<n-1;i+)for(j=0;j<n-1-i;j+)if(aj>aj+1)tmp=aj;aj=aj+1;aj+1=tmp;void sort2(int *a,int n)int i,j;int tmp;for(i=0;i<n-1;i+)for(j=0;j<n-1-i;j+)if(aj<aj+1)tmp=aj;aj=aj+1;aj+1=tmp;int main(void)int T;int n,i;int total;int a8,b8

28、,c8;scanf("%d",&T);while(T)total=0;scanf("%d",&n);for(i=0;i<n;i+)scanf("%d",&ai);for(i=0;i<n;i+)scanf("%d",&bi);sort1(a,n);sort2(b,n);for(i=0;i<n;i+)ci=ai*bi;for(i=0;i<n;i+)total+=ci;printf("%dn",total);T-;return 0;算法训练 To

29、rry的困惑(基本型)  时间限制：1.0s   内存限制：512.0MB      查看参考代码 锦囊1锦囊2锦囊3问题描述Torry从小喜爱数学。一天，老师告诉他，像2、3、5、7这样的数叫做质数。Torry突然想到一个问题，前10、100、1000、10000个质数的乘积是多少呢？他把这个问题告诉老师。老师愣住了，一时回答不出来。于是Torry求助于会编程的你，请你算出前n个质数的乘积。不过，考虑到你才接触编程不久，Torry只要你算出这个数模上50000的值。输入格式仅包含一个正整数n，其中n<=100000。输出格式输出一行，即

30、前n个质数的乘积模50000的值。样例输入1样例输出2#include<stdio.h>int pr100010;int top;int isPrime(int n)int i;for(i = 0; i < top; i+)if(n % pri = 0)return 0;return 1;int findNextPrime(void)int n = prtop - 1 + 1;while(!isPrime(n)n+;prtop+ = n;return n;int main(void)int i, n;int result = 2;scanf("%d", &

31、amp;n);pr0 = 2;top = 1;for(i = 1; i < n; i+)int x = findNextPrime();result *= x;result %= 50000;printf("%d", result);return 0;算法训练 寻找数组中最大值  时间限制：1.0s   内存限制：512.0MB      查看参考代码 锦囊1锦囊2锦囊3问题描述对于给定整数数组a,寻找其中最大值，并返回下标。输入格式整数数组a,数组元素个数小于1等于100。输出数据分作两行：第一行只有一个数，表示数组

32、元素个数；第二行为数组的各个元素。输出格式输出最大值，及其下标样例输入33 2 1样例输出3 0#include <stdio.h>int main()int n,i,k,max;scanf ("%d",&n);int an;for(i=0;i<n;i+)scanf("%d",&ai);max=a0;for(i=0;i<n;i+)if(ai>=max)max=ai;k=i;printf("%d %d",max,k);return 0;算法训练 关联矩阵  时间限制：1.0s &#

33、160; 内存限制：512.0MB      查看参考代码 锦囊1锦囊2锦囊3问题描述有一个n个结点m条边的有向图，请输出他的关联矩阵。输入格式第一行两个整数n、m，表示图中结点和边的数目。n<=100,m<=1000。接下来m行，每行两个整数a、b，表示图中有(a,b)边。注意图中可能含有重边，但不会有自环。输出格式输出该图的关联矩阵，注意请勿改变边和结点的顺序。样例输入5 91 23 11 52 52 32 33 24 35 4样例输出1 -1 1 0 0 0 0 0 0-1 0 0 1 1 1 -1 0 00 1 0 0 -1 -1 1 -1 0

34、0 0 0 0 0 0 0 1 -10 0 -1 -1 0 0 0 0 1#include<stdio.h>int main()int i, ii,n,m, a10002;scanf("%d%d", &n, &m);for ( i = 0; i < m; i+)scanf("%d%d", &ai0, &ai1);for ( i = 1; i <=n; i+)for (ii = 0; ii < m; ii+)if (i=aii0)printf("1 ");elseif (i=

35、aii1)printf("-1 ");elseprintf("0 ");printf("n");return 0;算法训练 操作格子  时间限制：1.0s   内存限制：256.0MB      查看参考代码 锦囊1锦囊2锦囊3问题描述有n个格子，从左到右放成一排，编号为1-n。共有m次操作，有3种操作类型：1.修改一个格子的权值，2.求连续一段格子权值和，3.求连续一段格子的最大值。对于每个2、3操作输出你所求出的结果。输入格式第一行2个整数n，m。接下来一行n个整数表示n个格子的初

36、始权值。接下来m行，每行3个整数p,x,y，p表示操作类型，p=1时表示修改格子x的权值为y，p=2时表示求区间x,y内格子权值和，p=3时表示求区间x,y内格子最大的权值。输出格式有若干行，行数等于p=2或3的操作总数。每行1个整数，对应了每个p=2或3操作的结果。样例输入4 31 2 3 42 1 31 4 33 1 4 样例输出63 数据规模与约定对于20%的数据n <= 100，m <= 200。对于50%的数据n <= 5000，m <= 5000。对于100%的数据1 <= n <= 100000，m <= 100000，0 <= 格

37、子权值 <= 10000。锦囊1使用线段树。 锦囊2线段树的每个结点记录下这一段区间所有数的和以及最大值即可。 #include <stdio.h>#define N 100000#define A 1000#define B 100int sum(int* a, int m, int n) int i, s = 0; for (i = m; i <= n; i+) s += ai; return s;int max(int* a, int m, int n) int i, s = am; for (i = m + 1; i <= n; i+) if (s <

38、; ai) s = ai; return s;int main() int i, j, k, m, n; int a100000, b1000003, cA2 = 0; scanf("%d%d", &n, &m); for (i = 0; i < n; i+) scanf("%d", &ai); for (i = 0; i < m; i+) for (j = 0; j < 3; j+) scanf("%d", &bij); for (i = 0; i < (n + B - 1)

39、/ B; i+) ci0 = ci1 = ai * B; for (j = i * B + 1; j < i * B + B && j < n; j+) ci0 += aj; if (ci1 < aj) ci1 = aj; for (i = 0; i < m; i+) if (bi0 = 1) c(bi1 - 1) / B0 += bi2 - abi1 - 1; k = (bi1 - 1) / B; if (ck1 <= bi2) ck1 = bi2; else if (abi1 - 1 = ck1) abi1 - 1 = bi2; ck1 = m

40、ax(a, k * B, k * B + B > n ? n - 1 : k * B + B - 1); abi1 - 1 = bi2; else if (bi0 = 2) int s = 0; bi1-, bi2-; int o = bi2 / B - bi1 / B; if (o < 2) s = sum(a, bi1, bi2); else s = sum(a, bi1, (bi1 + B) / B * B - 1); s += sum(a, bi2 / B * B, bi2); for (j = bi1 / B + 1; j < bi2 / B; j+) s += c

41、j0; printf("%dn", s); else if (bi0 = 3) int s = 0, t; bi1-, bi2-; int o = bi2 / B - bi1 / B; if (o < 2) s = max(a, bi1, bi2); else s = max(a, bi1, (bi1 + B) / B * B - 1); t = max(a, bi2 / B * B, bi2); if (s < t) s = t; for (j = bi1 / B + 1; j < bi2 / B; j+) if (s < cj1) s = cj1

42、; printf("%dn", s); return 0;/ test/ 1.cpp/* ID: Firwaless LANG: C+ TASK: */#include <cstdio>#include <algorithm>struct Tree int sum, max;Tree tree1 << 18;void scan(int &n) char c; c = getchar(); if (c = EOF) return ; while (c < '0' | c > '9') c

43、= getchar(); n = c - '0' while (c = getchar(), c >= '0' && c <= '9') n *= 10; n += c - '0' void put(int n) int cnt = 0; char s16; if (n = 0) putchar('0'); return ; for( ; n; n /= 10) scnt+ = n % 10 + '0' while (cnt-) putchar(scnt); void u

44、pdate(int n, int v) for (n += (1 << 17),treen.sum = treen.max = v, n >>= 1; n; n >>= 1) treen.max = std:max(treen + n.max, treen + n + 1.max); treen.sum = treen + n.sum + treen + n + 1.sum; int query(int s, int t, int func) int sum = 0, max = 0; for (s += (1 << 17) - 1, t +=

45、(1 << 17) + 1; s t 1; s >>= 1, t >>= 1) if (s & 1) sum += trees 1.sum; max = std:max(max, trees 1.max); if (t & 1) sum += treet 1.sum; max = std:max(max, treet 1.max); return func ? max : sum;int main() int n, m, i, a, b, c; scan(n);scan(m); for (i = 1; i <= n; +i) scan(a); update(i, a); while (m-) scan(c);scan(a);scan(b); c = 1 && (update(a, b), 0); c = 2 &am