算法训练-普通试题

1、试题编号 ALGO-101算法训练图形显示问题描述编写一个程序，首先输入一个整数，例如5,然后在屏幕上显示如下的图形(5表示行数)：*本题的C+参考代码如下：#includeusingnamespacestd;intmain()intn;cinn;for(inti=0;in;i+)for(intj=1;j=n-i;j+)cout*;if(jn-i)cout;elsecoutendl;return0;本题的C参考代码如下：#includeintmain()inti,j,a100100,n;while(scanf(%d,&n)!=EOF)for(i=0;in;i+)for(j=0;jn-i;j+)

2、printf(*);if(j!=n-i-1)printf();if(j=n-1-i)printf(n);试题编号 ALGO-97算法训练排序问题描述编写一个程序，输入3个整数，然后程序将对这三个整数按照从大到小进行排列。输入格式：输入只有一行，即三个整数，中间用空格隔开。输出格式：输出只有一行，即排序后的结果。输入输出样例样例输入9230样例输出3092本题的C+参考代码如下：#includeusingnamespacestd;intmain()inta,b,t,c;while(cinabc)if(ab)t=a;a=b;b=t;if(ac)t=a;a=c;c=t;if(bc)t=b;b=c;c

3、=t;coutabcendl;return0;本题的C参考代码如下：#include#include#definenum100intmain(void)inti,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);if(i!=2)printf();printf(n);return0;试题编号 ALGO-96算法训练2的次哥表示问题描述任何一个正整数都可以用2进制表示，例如：137的2进制表示为10001001。

4、将这种2进制表示写成2的次哥的和的形式，令次哥高的排在前面，可得到如下表达式:137=2A7+2A3+2A0现在约定哥次用括号来表示，即aAb表示为a(b)此时，137可表示为：2(7)+2(3)+2(0)进一步：7=2人2+2+2人0(2人1用2表示)3=2+2人0所以最后137可表示为：2(2(2)+2+2(0)+2(2+2(0)+2(0)又如：1315=2人10+2人8+2A5+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表示(在表示中不能有空格)样例

5、输入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)提示用递归实现会比较简单，可以一边递归一边输出本题的C+参考代码如下:#includeusingnamespacestd;/递归实现思路是先转换成二进制intfun(intn)inti=0;inta20=0;intm=n;while(m)ai=m%2;m/=2;i+;for(intj=i-1;j=0;j-)/高位到低位排列但是要注意每位的权改变if(aj=1)/若是最后一个1则之后不要加号intflag=1;for

6、(intk=j-1;k=0;k-)if(ak=1)flag=0;break;if(flag)/是最后一位if(j=1)cout2;elseif(j=0)cout2(j);elsecout2(;fun(j);cout);else不是最后一位if(j=1)cout2+;elseif(j=O)cout2(j)+;else(cout2(;fun(j)；cout)+;)return0;intmain()(intn;cinn;fun(n);coutendl;return0;本题的C参考代码如下：I#includeint1=0;chartemp1000=0;voidshow(intn)(if(n=O)tem

7、pl=O;l+;return;if(n=2)templ=2,l+;return;inta15=0,i=0j;while(n!=0)(ai=n%2;n/=2;i+；)for(j=i-1；j=O;j-)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+;)intmain()(intn;scanf(%d,&n);show(n);printf(%s,temp);return0;试题编号 A

8、LGO-93算法训练前缀表达式问题描述编写一个程序，以字符串方式输入一个前缀表达式，然后计算它的值。输入格式为：“运算符对象1对象2”，其中，运算符为“+”（加法）、“-（减法）、一（乘法）或“/”（除法），运算对象为不超过10的整数，它们之间用一个空格隔开。要求：对于加、减、乘、除这四种运算，分别设计相应的函数来实现。输入格式：输入只有一行，即一个前缀表达式字符串。输出格式：输出相应的计算结果（如果是除法，直接采用c语言的“/”运算符，结果为整数）。输入输出样例样例输入+52样例输出7本题的C+参考代码如下：#includeusingnamespacestd;intmain（）charc;i

9、nta,b;cincab;intres;if（c=+）res=a+b;elseif（c=-）res=a-b;elseif（c=*）res=a*b;elseres=a/b;coutres;return0;本题的C参考代码如下:#includeintmain()inta2;inti,j；charc=getchar();for(i=0;i2;i+)scanf(%d”,&ai);if(c=+)j=a0+a1;elseif(c=-)j=a0-a1；elseif(c=*)j=a0*a1；elseif(c=/)j=a0/a1；printf(%d,j);return0;试题编号 ALGO-91算法训练Anag

10、rams问题问题描述Anagrams指的是具有如下特性的两个单词：在这两个单词当中，每一个英文字母(不区分大小写)所出现的次数都是相同的。例如，Unclear和Nuclear、Rimon和MinOR”都是Anagrams。编写一个程序，输入两个单词，然后判断一下，这两个单词是否是Anagrams。每一个单词的长度不会超过80个字符，而且是大小写无关的。输入格式：输入有两行，分别为两个单词。输出格式：输出只有一个字母丫或N,分别表示Yes和No。输入输出样例样例输入UnclearNuclear样例输出Y本题的C+参考代码如下：#include#include#include#include#in

11、clude#include#include#include#include#includeusingnamespacestd;charGetCapital(charc)if(c=Z)returnc;elsereturnc-(a-A);intmain(intargc,char*argv)mapa,b;stringt;cint;for(inti=0;it;for(inti=0;it.length();i+)bGetCapital(ti)+;if(a=b)coutY;elsecoutN;return0;本题的C参考代码如下：#includevoidsort(chara口,intlen)inti,j,

12、max;for(i=0;ilen;i+)max=i;for(j=i+1;jamax)max=j;j=ai;ai=amax;amax=j;voidstrtoupper(chara,intlen)inti;for(i=0;i=a&ai=z)ai-=32;intmystrcmp(chara口,intl1,charb,intl2)if(l1!=l2)return0;inti;for(i=0;in;if(n=0)return0;string*a=newstringn;inti;for(i=0;iai;stringnumber=a0;intcount=1;intflag=1;for(i=1;icount)

13、count=flag;number=ai-1;flag=1;coutnumberendl;return0;本题的C参考代码如下：#includeintmain()intn,i,j,t,max=1,num=0;scanf(%d,&n);if(n0)intan;for(i=0;in;i+)scanf(%d,a+i);j=num=a0;t=1;for(i=1;imax)max=t;num=ai;elset=1;j=ai;printf(%d,num);return0;试题编号 ALGO-88算法训练字串统计问题描述给定一个长度为n的字符串S,还有一个数字L,统计长度大于等于L的出现次数最多的子串（不同

14、的出现可以相交），如果有多个，输出最长的，如果仍然有多个，输出第一次出现最早的。输入格式第一行一个数字L。第二行是字符串SoL大于0,且不超过S的长度。输出格式一行，题目要求的字符串。输入样例1:4bbaabbaaaaa输出样例1:bbaa输入中例2：2bbaabbaaaaa输出样例2：aa数据规模和约定n=60S中所有字符都是小写英文字母。提示枚举所有可能的子串，统计出现次数，找出符合条件的那个本题的C+参考代码如下：#include#includeintmain()chars65,str65;intmax=0,t,n,len;scanf(%d%s,&n,s);len=strlen(s);i

15、f(n=n;i-)ssi=tti尸0；for(intj=0;j=len-i;j+)t=1;for(intk=0;ki;k+)ssk=sk+j;for(intx=j+1;x=len-i;x+)for(inty=0;ymax)max=t;strcpy(str,ss);/printf(%sn,str);printf(%sn,str);本题的C参考代码如下：#include#includeintmain()charS1000,str10001000,temp100,out100;intL,i=0,s,otongji=0,ttongji,a,b,c;scanf(%d%c%c,&L,&S0,&S0);wh

16、ile(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;bL;b+)strab=Sa+b;)strab=0;)for(i=0;ia-1;)/比较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+;botong川|(ttongji=otongji&strlen(temp)strlen(out)strcpy(out,temp);otongji=ttongj

17、i;)i=0;while(outi!=0)printf(%c,outi);i+;getchar();return0;试题编号 ALGO-86算法训练矩阵乘法问题描述输入两个矩阵，分别是m*s,s*n大小。输出两个矩阵相乘的结果。输入格式第一行，空格隔开的三个正整数m,s,n(均不超过200)。接下来m行，每行s个空格隔开的整数，表示矩阵A(i,j)。接下来s行，每行n个空格隔开的整数，表示矩阵B(i,j)。输出格式m行，每行n个空格隔开的整数，输出相乘彳麦的矩阵C(i,j)的值。样例输入23210-111-3031231样例输出-32-82提示矩阵C应该是m行n歹U,其中C(i,j)等于矩阵A

18、第i行行向量与矩阵B第j列列向量的内积。例如样例中C(1,1)=(1,0,-1)*(0,1,3)=1*0+0*1+(-1)*3=-3本题的C+参考代码如下:#include#include#include#includeintmain()intm,s,n;intsum=0;inti,j,l；inta200200,b200200,c200200;scanf(%d%d%d,&m,&s,&n);for(i=0;im;i+)for(j=0;js;j+)scanf(%d”,&aij);for(i=0;is;i+)for(j=0;jn;j+)scanf(%d”,&bij);for(i=0;im;i+)fo

19、r(j=0;jn;j+)for(l=0;ls;l+)sum+=(ail*b皿);cij=sum;sum=0;for(i=0;im;i+)for(j=0;jn;j+)printf(%d,cij);printf(n);return0;本题的C参考代码如下：#includeintmain()intm,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);)fo

20、r(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);)return0;试题编号ALGO-84算法训练大小写转换问题描述编写一个程序，输入一个字符串(长度不超过20),然后把这个字符串内的每一个字符进行大小写变换，即将大写字母变成小写，小写字母变成大写，然后把这个新的字符串输出。输入格式：输入一个字符串，而且这个字符串当中只包含英文字母，不包含其他

21、类型的字符，也没有空格。输出格式：输出经过转换后的字符串。输入输出样例样例输入AeDb样例输出aEdB本题的C+参考代码如下：#include#includeusingnamespacestd;intmain()stringstr;cinstr;unsignedi;for(i=0;i=A&stri=a&stri=z)stri-=32;coutstr;return0;本题的C参考代码如下:#includeintmain()inti;charch100;gets(ch)；i=0;while(chi!=0)if(chi=a)chi-=32;elsechi+=32;i+；puts(ch);return

22、0;试题编号 ALGO-81算法训练动态数组使用从键盘读入n个整数，使用动态数组存储所读入的整数，并计算它们的和与平均值分别输出。要求尽可能使用函数实现程序代码。平均值为小数的只保留其整数部分。样例输入534002样例输出91样例输入73275291样例输出294本题的C+参考代码如下:#includeusingnamespacestd;intmain()intn,a,sum=0;cinn;for(inti=0;ia;sum+=a;coutsumsum/nendl;return0;本题的C参考代码如下:#includeintmain()inti,n,a100,b100,sum=0,avg=0;

23、scanf(%d,&n);for(i=0;in;arr=newintn;intnum=0;for(inti=0;iarri;if(arri!=0)+num;coutnumendl;for(inti=0;in;+i)if(arri=0)continue;coutarri;return0;本题的C参考代码如下：#includestdio.hintCompactIntegers(inta口，intlen)inti,j,k;for(k=0;klen;k+)for(i=0;ilen;i+)if(ai=0)for(j=i;jlen-1;j+)aj=aj+1;len-;returnlen;voidprint

24、(inta,intlen)inti;for(i=0;ilen;i+)printf(%d,ai);printf(n);intmain()inta100000;intn;scanf(%d,&n);inti;for(i=0;i1)printf(%dn,len);print(a,len);elseprintf(%d,0);getchar();getchar();getchar();return0;试题编号 ALGO-53算法训练最小乘积(基本型)问题描述给两组数，各n个。请调整每组数的排列顺序，使得两组数据相同下标元素对应相乘，然后相加的和最小。要求程序输出这个最小值。例如两组数分别为：13-5和-2

25、41那么对应乘积取和的最小值应为：(-5)*4+3*(-2)+1*1=-25输入格式第一个行一个数T表示数据组数。后面每组数据，先读入一个n,接下来两行每行n个数，每个数的绝又直小于等于1000。n=8,T=1000输出格式一个数表示答案。样例输入2313-5-24151234510101样例输出-256本题的C+参考代码如下：#include#includeusingnamespacestd;inta8,b8;intmain()intT,n;inti,j;cinT;while(T-)(intsum=0;cinn;for(i=0;iai;for(i=0;ibi;sort(a,a+n);sort

26、(b,b+n);for(i=0;in;i+)(sum+=ai*bn-1-i;coutsumendl;return0;本题的C参考代码如下:#includevoidsort1(int*a,intn)(inti,j;inttmp;for(i=0;in-1;i+)for(j=0;jaj+1)(tmp=aj;aj=aj+1;aj+1=tmp;voidsort2(int*a,intn)(inti,j;inttmp;for(i=0;in-1;i+)for(j=0;jn-1-i;j+)if(ajaj+1)tmp=aj;aj=aj+1;aj+1=tmp;intmain(void)intT;intn,i;int

27、total;inta8,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,total);T-;return0;试题编号 ALGO-51算法训练Torry的困惑（基本型）问题描述Torry从小喜爱数学。一天，老师告诉他，像2、3、5、7这样的数叫做质数。Torry突然想到一个问题，前

28、10、100、1000、10000个质数的乘积是多少呢？他把这个问题告诉老师。老师愣住了，一时回答不出来。于是Torry求助于会编程的你，请你算出前n个质数的乘积。不过，考虑到你才接触编程不久，Torry只要你算出这个数模上50000的值。输入格式仅包含一个正整数n,其中n=100000。输出格式输出一行，即前n个质数的乘积模50000的值。样例输入1样例输出2本题的C+参考代码如下:#includeusingnamespacestd;inta100005;intmain()unsignedinti,j,n,cnt=1,cj=2;cinn;if(n=1)cout2endl;return0;a0

29、=2;for(i=3;i2000000;i+)for(j=0;ji)break;elseif(!(i%aj)break;if(aj*aji)acnt+=i;cj=(cj%50000)*(i%50000);if(cnt=n)break;coutcj%50000endl;return0;本题的C参考代码如下:#includeintpr100010;inttop;intisPrime(intn)inti;for(i=0;itop;i+)if(n%pri=0)return0;return1;intfindNextPrime(void)intn=prtop-1+1;while(!isPrime(n)n+

30、;prtop+=n;returnn;intmain(void)inti,n;intresult=2;scanf(%d,&n);pr0=2;top=1;for(i=1;in;i+)intx=findNextPrime();result*=x;result%=50000;printf(%d,result);return0;试题编号 ALGO-49算法训练寻找数组中最大值问题描述对于给定整数数组a口，寻找其中最大值，并返回下标。输入格式整数数组a,数组元素个数小于1等于100。输出数据分作两行：第一行只有一个数,表示数组元素个数；第二行为数组的各个元素。输出格式输出最大值，及其下标样例输入3321样

31、例输出30本题的C+参考代码如下：#include#include#includeusingnamespacestd;intmain()intn,a1000,max,ans;cinn;for(inti=0;iai;max=a0;ans=0;for(inti=1;imax)max=ai;ans=i;coutmaxans;return0;本题的C参考代码如下:#includeintmain()intn,i,k,max;scanf(%d,&n);intan;for(i=0;in;i+)scanf(%d”,&ai);max=a0;for(i=0;i=max)max=ai;k=i;printf(%d%d

32、,max,k);return0;试题编号 ALGO-48算法训练关联矩阵问题描述有一个n个结点m条边的有向图，请输出他的关联矩阵。输入格式第一行两个整数n、m,表示图中结点和边的数目。n=100,m=1000。接下来m行，每行两个整数a、b,表示图中有(a,b)边。注意图中可能含有重边，但不会有自环。输出格式输出该图的关联矩阵，注意请勿改变边和结点的顺序。样例输入5912311 52 53 34 35 26 37 4样例输出1-11000000-100111-1000100-1-11-1000000001-100-1-100001本题的C+参考代码如下：#include#includeusin

33、gnamespacestd;intans1011001;intmain()intn,m;inta,b;cinnm;for(inti=1;i=m;i+)scanf(%d%d,&a,&b);ansai=1;ansbi=-1;for(inti=1;i=n;i+)for(intj=1;j=m-1;j+)printf(%d,ansij);printf(%dn,ansim);return0;本题的C参考代码如下:#includeintmain()inti,ii,n,m,a10002;scanf(%d%d,&n,&m);for(i=0;im;i+)scanf(%d%d,&ai0,&ai1);for(i=1;

34、i=n;i+)for(ii=0;iim;ii+)if(i=aii0)printf(1);elseif(i=aii1)printf(-1);elseprintf(0);printf(n);return0;试题编号 ALGO-42算法训练送分啦问题描述这题想得分吗？想，请输出“yes”；不想，请输出“no输出格式输出包括一行，为“yes”或“no”。本题的C+参考代码如下：#include#includeusingnamespacestd;intmain()printf(yesn);return0;本题的C参考代码如下：#include#includeintmain()printf(yesn);r

35、eturn0;试题编号 ALGO-8算法训练操作格子问题描述有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时表示求区间x,y内格子最大的权值。输出格式有若干行，彳T数等于p=2或3的操作总数。每行1个整数，对应了每个p=2或3操作的结果。样例输入4

36、31 2342 13143314样例输出63数据规模与约定对于20%的数据n=100,m=200。对于50%的数据n=5000,m=5000。对于100%的数据1=n=100000,m=100000,0=格子权值=10000。本题的C+参考代码如下:/test/1.cpp/*ID:FirwalessLANG:C+TASK:*/#include#includestructTreeintsum,max;Treetree118;voidscan(int&n)charc;c=getchar();if(c=EOF)return;while(c9)c=getchar();n=c-0;while(c=get

37、char(),c=0&c=9)n*=10;n+=c-0;voidput(intn)intcnt=0;chars16;if(n=0)putchar(0);return;for(;n;n/=10)scnt+=n%10+0;while(cnt-)putchar(scnt);voidupdate(intn,intv)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;intquery(ints,intt,intfunc)intsum=0,max=0;for(

38、s+=(117)-1,t+=(1=1,t=1)if(s&1)sum+=treesA1.sum;max=std:max(max,treesA1.max);if(t&1)sum+=treetA1.sum;max=std:max(max,treetA1.max);returnfunc?max:sum;intmain()intn,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),pu

39、tchar(n),0);c=3&(put(query(a,b,1),putchar(n),0);return0;本题的C参考代码如下:#include#defineN100000#defineA1000#defineB100intsum(int*a,intm,intn)inti,s=0;for(i=m;i=n;i+)s+=ai;returns;intmax(int*a,intm,intn)inti,s=am;for(i=m+1;i=n;i+)if(sai)s=ai;returns;intmain()inti,j,k,m,n;inta100000,b1000003,cA2=0;scanf(%d%d,&n,&m);for(i=0;in;i+)scanf(%d,&ai);for(i=0;im;i+)for(j=0;j