ACM程序设计-赛题样例.doc

座位调整 题目描述：百度办公区里到处摆放着各种各样的零食。百度人力资源部的调研发现，员工如果可以在自己喜欢的美食旁边工作，工作效率会大大提高。因此，百度决定进行一次员工座位的大调整。调整的方法如下：1 首先将办公区按照各种零食的摆放分成 N 个不同的区域。（例如：可乐区，饼干区，牛奶区等等）。2 每个员工对不同的零食区域有不同的喜好程度（喜好程度度的范围为 1 100 的整数， 喜好程度越大表示该员工越希望被调整到相应的零食区域）。3 由于每个零食区域可以容纳的员工数量有限，人力资源部希望找到一个最优的调整方案令到总的喜好程度最大。数据输入：第一行包含两个整数 N ， M ，（ 1=N ， M=300 ）。分别表示 N 个区域和 M 个员工。第二行是 N 个整数构成的数列 a ，其中 ai 表示第 i 个区域可以容纳的员工数， (1=ai=M ， a1+a2+.+aN=M) 。紧接着是一个 M*N 的矩阵 P ， P （ i ， j ）表示第 i 个员工对第 j 个区域的喜好度。答案输出：对于每个测试数据，输出可以达到的最大的喜好程度。输入样例3 31 1 1100 50 25100 50 25100 50 25输出样例175#includevoidmain()intn,m,l=0,i,j,s,t,sum=0;inta100,p100100,b100,c100;for(i=0;i100;i+)ai=0,ci=0,bi=0;for(j=0;j100;j+)pij=0;scanf(%d%d,&n,&m);for(i=0;in;i+)scanf(%d,&ai);for(i=0;in;i+)for(j=0;j=m)gotofinish;if(l0)for(s=0;sl;s+)t=cs;for(j=0;jm;j+)ptj=0;for(s=0;sm;s+)bs=0;for(s=0;sn;s+)bs=psi;for(s=0;sn-1;s+)for(j=0;jn-1-s;j+)if(bjbj+1)t=bj;bj=bj+1;bj+1=t;/printf(%dt,b0);/test+;for(s=0;s=ai)i+;gotofrist;for(t=0;tn;t+)if(bs=pti)cl=t;l+;break;elsecontinue;s+;gotosec;finish:/printf(n);printf(最大的喜好程度为：%dn,sum);/printf(%d,test);#include#includevoidmain()ints,t,u,v,w,x,y,z,sum=0,a20,b2020,c20,d20,sumx80,*p=sumx,max;scanf(%d%d,&x,&y);for(z=0;zx;z+)scanf(%d,&az);for(z=0;zy;z+)cz=z;dz=z;for(w=0;wy;w+)for(z=0;zx;z+)scanf(%d,&bwz);sum=0;for(z=0;zy;z+)sum+=b0z;for(w=z;wy-1;w+)dw=dw+1;for(w=0;wy-1;w+)s=dw;sum+=b1s;for(v=w;vy-2;v+)dv=dv+1;for(u=0;uy-2;u+)s=du;sum+=b1s;for(t=u;ty-3;t+)du=du+1;for(t=0;ty-3;t+)s=dt;sum+=b2s;for(z=0;zmax)max=sumxt;t+;printf(%dn,max);#include#includeintmain(intargc,char*argv)intN,M,*a,*p,*temp,i,j,k,max=0;printf(Pleaseinputareaandstaffnum:);scanf(%d%d,&N,&M);a=(int*)malloc(sizeof(int)*N);printf(nPleaseinputstaffnumofeacharea:);for(i=0;iN;i+)scanf(%d,&ai);p=(int*)malloc(sizeof(int)*N);printf(nPleaseinputlike:);for(i=0;iM;i+)pi=(int*)malloc(sizeof(int)*M);for(i=0;iM;i+)for(j=0;jN;j+)scanf(%d,&pij);temp=(int*)malloc(sizeof(int)*M);for(i=0;iN;i+)if(iN-1)for(j=0;jM;j+)k=i+1;tempj=0;while(kN)tempj+=pji-pjk;k+;inttemp1,temp2;while(ai)temp1=-101;temp2=0;for(j=0;jtemp1)temp1=tempj;temp2=j;max+=ptemp2i;printf(%d%d%dn,ptemp2i,temp2,i);for(intm=0;mN;m+)ptemp2m=-101;printf(n);for(intq=0;qM;q+)for(intw=0;wN;w+)printf(%d,pqw);printf(n);temptemp2=-101;ai-;elseinttemp3,temp4;while(ai)temp3=-101;temp4=0;for(j=0;jtemp3)temp3=pji;temp4=j;max+=ptemp4i;printf(%d%d%dn,ptemp4i,temp4,i);for(intm=0;mN;m+)ptemp4m=-101;printf(n);for(intq=0;qM;q+)for(intw=0;wN;w+)printf(%d,pqw);printf(n);temptemp4=-101;ai-;printf(Max=%dn,max);return0;/Yourprogramshouldreturn0onnormaltermination.蝈蝈式的记分 内容描述：蝈蝈小朋友刚刚学会了 0-9 这十个数字 , 也跟爸爸妈妈来参加百度每周进行的羽毛球活动。但是他还没有球拍高，于是大人们叫他记录分数。聪明的蝈蝈发现只要记录连续得分的情况就可以了，比如用“ 3 2 4 ” 可以表示一方在这一局中连得三分后，输了两分，接着又连得到四分。可是，后来大人们发现蝈蝈只会用 0-9 这十个数字，所以当比赛选手得分超过 9 的时候，他会用一个 X 来表示 10 完成记分。但问题是，当记录为“ X 3 5 ” 的时候，蝈蝈自己也记不起来是一方连续得到十三分后，再输五分；还是先赢十分输三分再赢五分。因为百度内部就要开始进行羽毛球联赛了，要先摸清大家的实力才好分组比赛呢于是，大人们想知道以前每局的比分是怎样的，以及谁获得了胜利。要是遇到了根据比赛记录无法确认比赛进程的情况，也要输出相应的提示哦。需要帮蝈蝈进一步说明的是，比赛是五局三胜的，每局先获得二十一分的为胜，但是胜方必须领先对手两分或以上，否则必须继续比赛直到一方超出对手两分为止，比分多的一方获胜。任何一方先获得三局的胜利后就获得胜利，比赛也相应的结束。而且蝈蝈保证是完整的无多余信息的记录了比赛。输入数据：以 point.in 为输入文件，文件中首行只有一个整数 M ，表示蝈蝈记录了多少场比赛的分数。每场比赛用两行记录，第一行是一个整数 N(N=1000) 表示当前这个记录中有多少个字符，第二行就是具体的 N 个字符表示记录的分数。输出数据：相应的内容将输出到 point.out 文件中，对应每一个分数记录，输出相应的每局分数，每局分数都使用两个整数表示，表示两个选手的得分，中间用 : 分隔开；每组分数记录间使用一个空行分隔开。如果相应的比赛结果无法预测的时候，以” Unknown “一个单词独占一行表示。输入和输出结果数据样例：输入样例3239 7 3 6 2 4 7 8 3 2 7 9 X 2 2 1 2 1 X 1 X 1 1259 3 8 5 4 8 3 9 8 4 X X X X 2 X X X X 2 8 4 9 2 4437 7 7 7 7 3 4 5 6 7 6 5 4 2 1 3 5 7 9 7 5 3 1 3 0 9 9 3 9 3 2 1 1 1 5 1 5 1 5 1 5 5 1输出样例21:1724:2221:3Unknown21:1420:2221:2321:1621:9足球比赛吉林一中将举办一年一度的足球比赛。Andy的班级即将面临一组强队，就是去年的冠军队。Andy在比赛之前做了充分的准备，搜集了许多关于这支队伍的信息。在这支队伍中有N1个队员，通过过去比赛记录来看，他们总是在某些固定的队员之间传球。我们把对方的守门员编号为1号，我们的球门编号为N号，其他的为对方球员。资料里给出若干个整数对（ai，bi），表示球会从ai传到bi，如果ai1，代表球从对方守门员开出，如果biN，代表球攻入我方大门。其他情况均为对方队友间的传球配合。每组传球，还会给出一个实数pi，表示对方传球成功的概率，我方成功防守的概率就是1pi。我们会选择一些对方的传球路线做重点防御，使得不会出现某条从对方守门员到我方大门路径完全没有防守。假设我们选取的防御集合为S，我们定义了估价函数F（S）表示该种防守的可靠值现在你需要计算这个可靠值最大值。输入输入包含多组测试数据。数据的第一行包含两个整数N，M (1= N = 100, 1= M = 400), 接下来M行，每行包含三个数字ai bi Pi (1 = ai, bi = N , 0 = Pi = 1 ).输入文件结束于 N = M = 0.输出对于每组数据，如果最大值为0，输出“The opponent is too strong!” 如果最大值为1，输出“The opponent is too week!”，否则输出这个最大值，保留6位小数。样例输入4 41 2 0.52 4 0.62 3 0.53 4 0.84 41 2 1.02 3 1.03 4 1.02 4 1.04 41 2 02 3 1.03 4 1.02 4 1.00 0样例输出0.500000The opponent is too strong!The opponent is too week!提示对于第一组样例数据，我们可以选择第一条路线做重点防御，此时 F 为 ( (1-0.5) 1 ) = 0.5。如果我们选择第三条和第四条路线做重点防御，此时F为 ( (1-0.6) * (1-0.8) ) (1/2) = 0.282843。只选择第三条路线是不合法的，对方可以通过1，2，4将球轻松送入我方大门。#include#includefloatodds_of_lines=1.0;floatodds_of_total=0.0;structwayintstart;intend;floatodds;structwaystack10;intps=0;voidpush(structwaya)stackps=a;ps+;voidpop()ps-;voidseek(structway*ways,intfirst,intgoal,intlines)inti=0;for(;i=lines;i+)if(i!=lines)if(waysi.start=first)push(waysi);if(stackps-1.end=goal)inti=0;for(;ips;i+)odds_of_lines*=stacki.odds;odds_of_total+=odds_of_lines;odds_of_lines=1.0;pop();elseseek(ways,stackps-1.end,goal,lines);elseif(i=lines)intmain()intgoal;intlines;scanf(%d%d,&goal,&lines);getchar();structway*ways=(structway*)malloc(sizeof(structway)*lines);inti;for(i=0;i=1)printf(Theopponentistoostrong!n);elseif(odds_of_total=0)printf(Theopponentistooweek!n);elseprintf(%.6fn,odds_of_total);return0;说明：测试的时候是分组输入的，例如测试题目上给定的第一组数据。输入44120.5240.6230.5340.8可以测试第一组，然后程序会结束，接着可以测试第二组，就是说输入：44121.0231.0341.0241.0以此类推。平方数给出包含M个数字的列表，和列表中所有数字的所有质因数。求出最长的子列表，使得子列表中所有数字的乘积是一个完全平方数。输入输入文件包含多组测试数据。第一行包含两个整数N , M ( 1 = N = 30 , 1 = M = 30000 ). N 是质因数的个数。接下来一行有N个整数，给出所有的质因数。然后一行包含M个整数，给出列表。输入文件结束于N = M = 0.输出对于每组数据，输出最长子列表的两个位置坐标l r。l是该子列表在列表中的起始位置，r是结束位置。如果多种情况都满足子列表长度最大，输出l最小的一个。如果不存在这样的子列表输出“None”。样例输入3 42 3 54 9 25 63 42 3 56 6 3 30 0样例输出1 31 4#includeintbegin=0,end=0;intjudge(intm)/判断m是否是完全平方数inti=2;intcount;while(m!=1)count=0;if(mi)return0;while(m%i=0)m/=i;count+;if(count%2)return0;i+;return1;voidoperate(int*a,intn,intm)intx,y;inti;inttotal=1;for(i=m;iend-begin)begin=x+1;end=y+1;return;elseoperate(a,n-1,m);voidmain()intn,i;inta100;printf(输入数组长度n：);scanf(%d,&n);printf(输入数组元素：);for(i=0;in;i+)scanf(%d,&ai);for(i=0;in;i+)operate(a,n,i);printf(%d%d,begin,end);技能树Problem玩过Diablo的人对技能树一定是很熟悉的。一颗技能树的每个结点都是一项技能，要学会这项技能则需要耗费一定的技能点数。只有学会了某一项技能以后，才能继续学习它的后继技能。每项技能又有着不同的级别，级别越高效果越好，而技能的升级也是需要耗费技能点数的。有个玩家积攒了一定的技能点数，他想尽可能地利用这些技能点数来达到最好的效果。因此他给所有的级别都打上了分，他认为效果越好的分数也越高。现在他要你帮忙寻找一个分配技能点数的方案，使得分数总和最高。Input该题有多组测试数据。每组测试数据第一行是一个整数n（1=n=20）,表示所有不同技能的总数。接下来依次给出n个不同技能的详细情况。每个技能描述包括5行。第一行是该技能的名称。第2行是该技能在技能树中父技能的名称，名称为None则表示该技能不需要任何的先修技能便能学习。第3行是一个整数L（1=LNEXT=NULL;Au=*T;scanf(%d,&num);for(i=0;iNEXT=NULL;Bu-NameSon=(char*)malloc(sizeof(char)*CHAR_LEN);Bu-NameFather=(char*)malloc(sizeof(char)*CHAR_LEN);Bu-NeedPoint=(int*)malloc(sizeof(int)*INT_LEN);Bu-Score=(int*)malloc(sizeof(int)*INT_LEN);getchar();gets(Bu-NameSon);gets(Bu-NameFather);scanf(%d,&Bu-MaxLeve);for(j=0;jMaxLeve;j+)scanf(%d,Bu-NeedPoint+j);for(j=0;jMaxLeve;j+)scanf(%d,Bu-Score+j);Au-NEXT=Bu;Au=Bu;returnnum;intLocatFath(SkillTree*T,char*Name)intLct;SkillTreeAu;Au=(*T)-NEXT;Lct=1;while(Au)if(strcmp(Au-NameSon,Name)Au=Au-NEXT;Lct+;elsereturnLct;return-1;SkillTreeGradFath(SkillTree*T,intnPos)intLc;SkillTreeAu;Au=(*T)-NEXT;Lc=1;while(Au&(LcNEXT;Lc+;if(Lc=nPos&Au)returnAu;returnNULL;intMaxScore(SkillTree*T,intRemain,int*Grade)inti,MaxS,Sum=0,LS,LF,Td;SkillTreeAu;while(Remain0)MaxS=-1;Au=(*T)-NEXT;LS=1;while(Au)LF=LocatFath(T,Au-NameFather);for(i=*(Grade+LS-1)+1;iMaxLeve;i+)if(MaxSScore+i-1)&(Remain=*(Au-NeedPoint+i-1)if(i=1)if(strcmp(Au-NameFather,None)&LF!=-1&*(Grade+LF-1)0)|(!strcmp(Au-NameFather,None)MaxS=*(Au-Score+i-1);Td=LS;elsebreak;elseif(i1)&(*(Grade+LS-1)=i-1)MaxS=*(Au-Score+i-1);Td=LS;elsebreak;elsebreak;Au=Au-NEXT;LS+;if(MaxS!=-1)(*(Grade+Td-1)+;Au=GradFath(T,Td);Remain-=*(Au-NeedPoint+*(Grade+Td-1)-1);Sum+=MaxS;elsebreak;returnSum;main()inti,R,N,MaxP,*G;SkillTreet;N=CreatSkillTree(&t);G=(int*)malloc(sizeof(int)*N);scanf(%d,&R);for(i=0;iN;i+)scanf(%d,G+i);MaxP=MaxScore(&t,R,G);printf(%d,MaxP);getch();嗅探器Problem某军搞信息对抗实战演习.红军成功地侵入了蓝军的内部网络.蓝军共有两个信息中心.红军计划在某台中间服务器上安装一个嗅探器,从而能够侦听到两个信息中心互相交换的所有信息.但是蓝军的网络相当的庞大,数据包从一个信息中心传到另一个信息中心可以不止有一条通路.现在需要你尽快地解决这个问题.应该把嗅探器安装在哪个中间服务器上才能保证所有的数据包都能被捕获?Input该题含有多组测试数据。第一行一个整数n(1=n=100),表示蓝军网络中服务器的数目.接下来若干行是对蓝军网络的拓扑结构描述.每行是两个整数i,j表示编号为I和编号为j的两台服务器间存在连接(显然连接是双向的).服务器的编号从1开始.描述一两个0结束.再接下来一行是两个整数a,b分别表示两个中心服务器的编号.Output输出编号。如果有多个解输出编号最小的一个.如果找不到任何解,输出”No solution”.Sample Input52 12 51 45 32 35 10 04 2Sample Output1陶陶摘苹果【问题描述】陶陶家的院子里有一棵苹果树，每到秋天树上就会结出10个苹果。苹果成熟的时候，陶陶就会跑去摘苹果。陶陶有个30厘米高的板凳，当她不能直接用手摘到苹果的时候，就会踩到板凳上再试试。现在已知10个苹果到地面的高度，以及陶陶把手伸直的时候能够达到的最大高度，请帮陶陶算一下她能够摘到的苹果的数目。假设她碰到苹果，苹果就会掉下来。【输入文件】输入文件apple.in包括两行数据。第一行包含10个100到200之间（包括100和200）的整数（以厘米为单位）分别表示10个苹果到地面的高度，两个相邻的整数之间用一个空格隔开。第二行只包括一个100到120之间（包含100和120）的整数（以厘米为单位），表示陶陶把手伸直的时候能够达到的最大高度。【输出文件】输出文件apple.out包括一行，这一行只包含一个整数，表示陶陶能够摘到的苹果的数目。【样例输入】100 200 150 140 129 134 167 198 200 111110【样例输出】5#includeintmain()inthigh10,height,counter=0;scanf(%d%d%d%d%d%d%d%d%d%d,&high0,&high1,&high2,&high3,&high4,&high5,&high6,&high7,&high8,&high9);scanf(%d,&height);for(inti=0;i=highi)counter+;printf(%d,counter);#includeintmain()FILE*fp;inta10=0,i,h,n=0;fp=fopen(apple.in.txt,r);if(fp=NULL)printf(文件打开失败n);exit(0);for(i=0;i10;i+)fscanf(fp,%d,&ai);fscanf(fp,%d,&h);h=h+30;for(i=0;i=ai)n+;printf(%dn,n);fclose(fp);#includeintmain(void)inta11=0,i=0,j,n=0;for(i=1;i=10;i+)scanf(%d,&ai);scanf(%d,&j);j=j+30;for(i=1;i=ai)n+;printf(%dn,n);幻方矩阵Problem description幻方是一种很有意思的数字矩阵，在很早著名的九宫八卦阵就与幻方有关。幻方的定义为：1 到 N*N 的整数填入N*N的方格中，每行