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

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

2、参考代码 锦囊1锦囊2锦囊3问题描述编写一个程序，输入3个整数，然后程序将对这三个整数按照从大到小进行排列。输入格式：输入只有一行，即三个整数，中间用空格隔开。输出格式：输出只有一行，即排序后的结果。输入输出样例样例输入9 2 30样例输出30 9 2#include#include#define num 100int main(void)int i,j,t,a3=0;for (i=0;i3;i+)scanf(%d,&ai);for (i=0;i3;i+)for (j=i;j3;j+)if (ai=aj)t=ai;ai=aj;aj=t;for (i=0;i3;i+)printf(%d,ai);

3、if(i!=2) printf( );printf(n);return 0; 算法训练 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）

4、又如：1315=210+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 int l=0;char temp1000=0;void show(int n) if(n=0) temp

5、l=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 ) templ=+;l+;templ=2;l+;templ=(;l+; show(j); templ=);l+; int main()int n;scanf(%d,&n);show(n);

6、printf(%s,temp); return 0;算法训练 前缀表达式 时间限制：1.0s 内存限制：512.0MB 查看参考代码 锦囊1锦囊2锦囊3问题描述编写一个程序，以字符串方式输入一个前缀表达式，然后计算它的值。输入格式为：“运算符 对象1 对象2”，其中，运算符为“+”（加法）、“-”（减法）、“*”（乘法）或“/”（除法），运算对象为不超过10的整数，它们之间用一个空格隔开。要求：对于加、减、乘、除这四种运算，分别设计相应的函数来实现。输入格式：输入只有一行，即一个前缀表达式字符串。输出格式：输出相应的计算结果（如果是除法，直接采用c语言的“/”运算符，结果为整数）。输入输出样例

7、样例输入+ 5 2样例输出7#includeint main() int a2; int i,j; char c=getchar(); for(i=0;i2;i+) scanf(%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指的是具有如下特性的两个单词：在这两个单词当中，每一个英文

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

9、x=j;j=ai;ai=amax;amax=j;void strtoupper(char a,int len)int i;for(i=0;i=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;il1;i+)if(ai!=bi) return 0;return 1;int mystrlen(char *p)int l=0;while(*p+!=0)l+;return l;int main()char s11000=0,s21000=0;int l1,l2;scan

10、f(%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);return 0;算法训练 出现次数最多的整数 时间限制：1.0s 内存限制：512.0MB 查看参考代码 锦囊1锦囊2锦囊3问题描述编写一个程序，读入一组整数，这组整数是按照从小到大的顺序排列的，它们的个数N也是由用户输入的，最多不会超过20。然后程序将对这个数组进行统计，把出现次

11、数最多的那个数组元素值打印出来。如果有两个元素值出现的次数相同，即并列第一，那么只打印比较小的那个值。输入格式：第一行是一个整数N，N 20；接下来有N行，每一行表示一个整数，并且按照从小到大的顺序排列。输出格式：输出只有一行，即出现次数最多的那个元素值。输入输出样例样例输入5100150150200250样例输出150#include int main()int n,i,j,t,max=1,num=0;scanf(%d,&n);if(n0)int an;for(i=0;in;i+)scanf(%d,a+i);j=num=a0;t=1;for(i=1;imax)max=t;num=ai; el

12、set=1;j=ai;printf(%d,num);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=60S中所有字符都是小写

13、英文字母。提示枚举所有可能的子串，统计出现次数，找出符合条件的那个#include#includeint 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 = 0; for(s=i+1;L=s;L+) for(a=0;as+1-L;a+)/赋值 for(b = 0;b L;b+) strab=Sa+b; strab = 0; for(i = 0;i a-1;)/比

14、较 for(b = 0;ba;b+) if(strb0!=0) for(c = 0;cL;c+) tempc=strbc; tempc = 0; ttongji = 1; i+; strb0 = 0; break; for(b+;b 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

15、查看参考代码 锦囊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,0,-1)*(0,1,3) = 1

16、* 0 +0*1+(-1)*3=-3 # includeint 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(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;

17、i+)for(j=1;j=n;j+)printf(%d ,cij);printf(n);return 0;算法训练 大小写转换 时间限制：1.0s 内存限制：512.0MB 查看参考代码 锦囊1锦囊2锦囊3问题描述编写一个程序，输入一个字符串（长度不超过20），然后把这个字符串内的每一个字符进行大小写变换，即将大写字母变成小写，小写字母变成大写，然后把这个新的字符串输出。输入格式：输入一个字符串，而且这个字符串当中只包含英文字母，不包含其他类型的字符，也没有空格。输出格式：输出经过转换后的字符串。输入输出样例样例输入AeDb样例输出aEdB#include int main()int i;ch

18、ar ch100;gets(ch);i=0;while(chi!=0)if(chi=a)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 int main()int i,n,a100,b100,sum=0,

19、avg=0;scanf(%d,&n);for(i=0;in;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的元素，其后元素向数组首端移动。注意，CompactIntegers函数需要接受数组及其元素个数作为参数，函数返回值应为删除操作执行后数组的新元素个数。输出删除后数组中元素的个数并依次输出数组元

20、素。样例输入: （输入格式说明：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 查看参考代码 锦囊1锦囊2锦囊3问题描述给两组数，各n个。请调整每组数的排列顺序，使得两组数据相同下标元素对应相乘，然后相加的和最小。要求程序输出这个最小值。例如两组数分别为:1 3-5和-2 4 1那么对应乘积取和的最小值应为

21、：(-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#includevoid sort1(int *a,int n)int i,j;int tmp;for(i=0;in-1;i+)for(j=0;jaj+1)tmp=aj;aj=aj+1;aj+1=tmp;void sort2(int *a,int n)int i,j;int t

22、mp;for(i=0;in-1;i+)for(j=0;jn-1-i;j+)if(ajaj+1)tmp=aj;aj=aj+1;aj+1=tmp;int main(void)int T;int n,i;int total;int a8,b8,c8;scanf(%d,&T);while(T)total=0;scanf(%d,&n);for(i=0;in;i+)scanf(%d,&ai);for(i=0;in;i+)scanf(%d,&bi);sort1(a,n);sort2(b,n);for(i=0;in;i+)ci=ai*bi;for(i=0;in;i+)total+=ci;printf(%dn,

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

24、000的值。样例输入1样例输出2#includeint 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, &n);pr0 = 2;top = 1;for(i = 1; i n; i+)int x

25、 = findNextPrime();result *= x;result %= 50000;printf(%d, result);return 0;算法训练 寻找数组中最大值 时间限制：1.0s 内存限制：512.0MB 查看参考代码 锦囊1锦囊2锦囊3问题描述对于给定整数数组a,寻找其中最大值，并返回下标。输入格式整数数组a,数组元素个数小于1等于100。输出数据分作两行：第一行只有一个数，表示数组元素个数；第二行为数组的各个元素。输出格式输出最大值，及其下标样例输入33 2 1样例输出3 0#include int main()int n,i,k,max;scanf (%d,&n);in

26、t an;for(i=0;in;i+)scanf(%d,&ai);max=a0;for(i=0;i=max)max=ai;k=i;printf(%d %d,max,k);return 0;算法训练 关联矩阵 时间限制：1.0s 内存限制：512.0MB 查看参考代码 锦囊1锦囊2锦囊3问题描述有一个n个结点m条边的有向图，请输出他的关联矩阵。输入格式第一行两个整数n、m，表示图中结点和边的数目。n=100,m=1000。接下来m行，每行两个整数a、b，表示图中有(a,b)边。注意图中可能含有重边，但不会有自环。输出格式输出该图的关联矩阵，注意请勿改变边和结点的顺序。样例输入5 91 23 11

27、 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 00 0 0 0 0 0 0 1 -10 0 -1 -1 0 0 0 0 1#includeint 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=

28、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个格子的初始权值。接下来m行，每行3个整数p,x,y，p表示操作类型，p=1时表示修改格子x的权值为y，p=2时表示求区间x,y内格子权值和，p=3

29、时表示求区间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 = 格子权值 = 10000。锦囊1使用线段树。 锦囊2线段树的每个结点记录下这一段区间所有数的和以及最大值即可。 #include #define N 100000#define A 1000#define

30、 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 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(

31、%d, &ai); for (i = 0; i m; i+) for (j = 0; j 3; j+) scanf(%d, &bij); for (i = 0; i (n + B - 1) / 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 n ?

32、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 += cj0; printf(%dn, s); else if (bi0 = 3) int

33、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; printf(%dn, s); return 0;/ test/ 1.cpp/* ID: Firwaless LANG: C+ TASK: */

34、#include #include struct Tree int sum, max;Tree tree1 18;void scan(int &n) char c; c = getchar(); if (c = EOF) return ; while (c 9) c = 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 /

35、= 10) scnt+ = n % 10 + 0; while (cnt-) putchar(scnt); void update(int n, int v) for (n += (1 = 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 += (1 = 1,

36、 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 & (put(query(a, b, 0), putchar(n), 0); c = 3 & (put(query(a, b, 1), putchar(n), 0); return 0;算法训练 逆序对 时间限制：1.0s 内存限制：256.0MB 查看参考代码 锦囊1使用平衡树。 锦囊2从叶子到根依次处理，每次