搜索
主站题库p1000A+BProblem【背景】为大家熟悉本系统创建本题！【描述】输入两个自然数，输出他们的和【输入格式】输出两个自然数x,y【输出格式】一个数，即x和y的和【样例输入】125300【样例输出】425【时间限制】各个测试点1s【题解】这倒我就不讲了，没什么好注意。【参考程序】programghfjk;vara,b:longint;beginreadln(a,b);writeln(a+b);end.p1001第K极值【描述】给定一个长度为N(0n=10000)的序列，保证每一个序列中的数字a[i]是小于maxlongint的非负整数，编程要求求出整个序列中第k大的数字减去第k小的数字的值m，并判断m是否为质数。(0k=n)【输入格式】第一行为2个数n，k（含义如上题）第二行为n个数，表示这个序列【输出格式】：如果m为质数则第一行为'YES'(没有引号）第二行为这个数m否则第一行为'NO'第二行为这个数m【样例输入】5212345【样例输出】YES2【时间限制】各个测试点1s【数据范围】20%数据满足0n=1050%数据满足0n=5000100%数据满足0n=10000a[i]=maxlongint【注释】对于第K大的详细解释:如果一个序列为122223第1大为3第2大为2第3大为2第4大为2第5大为1第K小与上例相反另外需要注意的是最小的质数是2,如果小于2的话,请直接输出NO【题解】这道题很简单，先快排，在按要求判断该数是否为素数。注释里的话一定要看！！（有很多人吃亏）【参考程序】programdfj;varn,k,i:longint;a:array[1..10000]oflongint;procedureqs(l,r:longint);vari,j,m,t:longint;begini:=l;j:=r;m:=a[(l+r)DIV2];repeatwhilea[i]mdoinc(i);whilea[j]mdodec(j);ifi=jthenbegint:=a[i];a[i]:=a[j];a[j]:=t;inc(i);dec(j);end;untilij;ifirthenqs(i,r);ifljthenqs(l,j);end;functionprime(x:longint):boolean;vari:longint;beginifx=1thenexit(false);ifx=2thenexit(true);fori:=2totrunc(sqrt(x))doifxmodi=0thenexit(false);exit(true);end;beginreadln(n,k);fori:=1tondoread(a[i]);qs(1,n);ifprime(a[n-k+1]-a[k])thenwriteln('YES')elsewriteln('NO');writeln(a[n-k+1]-a[k]);end.p1002谁拿了最多奖学金【描述】某校的惯例是在每学期的期末考试之后发放奖学金。发放的奖学金共有五种，获取的条件各自不同：1)院士奖学金，每人8000元，期末平均成绩高于80分（80），并且在本学期内发表1篇或1篇以上论文的学生均可获得；2)五四奖学金，每人4000元，期末平均成绩高于85分（85），并且班级评议成绩高于80分（80）的学生均可获得；3)成绩优秀奖，每人2000元，期末平均成绩高于90分（90）的学生均可获得；4)西部奖学金，每人1000元，期末平均成绩高于85分（85）的西部省份学生均可获得；5)班级贡献奖，每人850元，班级评议成绩高于80分（80）的学生干部均可获得；只要符合条件就可以得奖，每项奖学金的获奖人数没有限制，每名学生也可以同时获得多项奖学金。例如姚林的期末平均成绩是87分，班级评议成绩82分，同时他还是一位学生干部，那么他可以同时获得五四奖学金和班级贡献奖，奖金总数是4850元。现在给出若干学生的相关数据，请计算哪些同学获得的奖金总数最高（假设总有同学能满足获得奖学金的条件）。【输入格式】输入的第一行是一个整数N（1=N=100），表示学生的总数。接下来的N行每行是一位学生的数据，从左向右依次是姓名，期末平均成绩，班级评议成绩，是否是学生干部，是否是西部省份学生，以及发表的论文数。姓名是由大小写英文字母组成的长度不超过20的字符串（不含空格）；期末平均成绩和班级评议成绩都是0到100之间的整数（包括0和100）；是否是学生干部和是否是西部省份学生分别用一个字符表示，Y表示是，N表示不是；发表的论文数是0到10的整数（包括0和10）。每两个相邻数据项之间用一个空格分隔。【输出格式】输出包括三行，第一行是获得最多奖金的学生的姓名，第二行是这名学生获得的奖金总数。如果有两位或两位以上的学生获得的奖金最多，输出他们之中在输入文件中出现最早的学生的姓名。第三行是这N个学生获得的奖学金的总数。【样例输入】4YaoLin8782YN0ChenRuiyi8878NY1LiXin9288NN0ZhangQin8387YN1【样例输出】ChenRuiyi900028700【题解】快排+字符串处理，仔细一点就可以AC。【参考程序】programjk;varn,i,j,k,l,max:longint;b,c,f,g:array[1..100]oflongint;a,d,e:array[1..100]ofstring;st:string;procedureinit;vari,l:longint;s,t:string;beginreadln(n);fori:=1tondobeginreadln(s);l:=pos('',s);a[i]:=copy(s,1,l-1);delete(s,1,l);l:=pos('',s);t:=copy(s,1,l-1);val(t,b[i]);delete(s,1,l);l:=pos('',s);t:=copy(s,1,l-1);val(t,c[i]);delete(s,1,l);l:=pos('',s);d[i]:=copy(s,1,l-1);delete(s,1,l);l:=pos('',s);e[i]:=copy(s,1,l-1);delete(s,1,l);val(s,f[i]);end;end;begininit;fillchar(g,sizeof(g),0);fori:=1tondobeginif(b[i]80)and(f[i]=1)theninc(g[i],8000);if(b[i]85)and(c[i]80)theninc(g[i],4000);ifb[i]90theninc(g[i],2000);if(b[i]85)and(e[i]='Y')theninc(g[i],1000);if(c[i]80)and(d[i]='Y')theninc(g[i],850);end;max:=0;l:=0;fori:=1tondobeginl:=l+g[i];ifg[i]maxthenbeginmax:=g[i];st:=a[i];end;end;writeln(st);writeln(max);writeln(l);end.P1003越野跑【描述】为了能在下一次跑步比赛中有好的发挥，贝茜在一条山路上开始了她的训练。贝茜希望能在每次训练中跑得尽可能远，不过她也知道农场中的一条规定：奶牛独自进山的时间不得超过M秒(1=M=10,000,000)。整条山路被贝茜划分成T个长度相同的小段(1=T=100,000)，并且，贝茜用S_i表示第i个小段的路况。S_i为u，f，d这3个字母之一，它们分别表示第i个小段是上坡、平地，或是下坡。贝茜要花U秒(1=U=100)才能跑完一段上坡路，跑完一段平地的耗时是F秒(1=F=100)，跑完一段下坡路要花D秒(1=D=100)。注意，沿山路原路返回的时候，原本是上坡路的路段变成了下坡路，原本是下坡路的路段变成了上坡路。贝茜想知道，在能按时返回农场的前提下，她最多能在这条山路上跑多远。【输入格式】*第1行:5个用空格隔开的整数：M，T，U，F，以及D*第2..T+1行:第i+1行为1个字母S_i，描述了第i段山路的路况【输出格式】*第1行:输出1个整数，为贝茜在按时回到农场的前提下，最多能跑到多远【样例输入】135321ufudf【样例输出】3【题解】模拟一下跑步的过程。用s记录跑到第i段路并返回的时间若s=m则输出i并退出，若sm则输出I-1并退出。【参考程序】programdfjk;vari,s,m,t,u,f,d:longint;a:array[1..100000]ofchar;beginreadln(m,t,u,f,d);fori:=1totdoreadln(a[i]);s:=0;fori:=1totdobegincasea[i]of'u':s:=s+u+d;'f':s:=s+2*f;'d':s:=s+u+d;end;ifs=mthenbreak;end;ifs=mthenwriteln(i);ifsmthenwriteln(i-1);end.p1004滑雪【描述】trs喜欢滑雪。他来到了一个滑雪场，这个滑雪场是一个矩形，为了简便，我们用r行c列的矩阵来表示每块地形。为了得到更快的速度，滑行的路线必须向下倾斜。例如样例中的那个矩形，可以从某个点滑向上下左右四个相邻的点之一。例如24-17-16-1，其实25-24-23…3-2-1更长，事实上这是最长的一条。【输入】第1行:两个数字r，c(1=r,c=100)，表示矩阵的行列。第2..r+1行:每行c个数，表示这个矩阵。【输出】仅一行:输出1个整数，表示可以滑行的最大长度。【样例输入】5512345161718196152425207142322218131211109【样例输出】25【题解】这道题用动态规划+记忆化搜索求解【参考程序】programgj;constdx:array[1..4]of-1..1=(-1,0,1,0);dy:array[1..4]of-1..1=(0,-1,0,1);vari,j,r,c,max,t:longint;a:array[1..100,1..100]oflongint;f:array[1..100,1..100]oflongint;functiondfs(x,y:longint):longint;vari,nx,ny,t,temp:longint;beginiff[x,y]0thenbegindfs:=f[x,y];exit;end;t:=1;fori:=1to4dobeginnx:=x+dx[i];ny:=y+dy[i];if(nx0)and(nx=r)and(ny0)and(ny=c)thenifa[x,y]a[nx,ny]thenbegintemp:=dfs(nx,ny)+1;iftemptthent:=temp;end;end;f[x,y]:=t;dfs:=t;end;beginreadln(r,c);fori:=1tordoforj:=1tocdoread(a[i,j]);max:=0;fillchar(f,sizeof(f),0);fori:=1tordoforj:=1tocdobegint:=dfs(i,j);f[i,j]:=t;iftmaxthenmax:=t;end;writeln(max);end.p1005采药【描述】辰辰是个天资聪颖的孩子，他的梦想是成为世界上最伟大的医师。为此，他想拜附近最有威望的医师为师。医师为了判断他的资质，给他出了一个难题。医师把他带到一个到处都是草药的山洞里对他说：“孩子，这个山洞里有一些不同的草药，采每一株都需要一些时间，每一株也有它自身的价值。我会给你一段时间，在这段时间里，你可以采到一些草药。如果你是一个聪明的孩子，你应该可以让采到的草药的总价值最大。”如果你是辰辰，你能完成这