ACM题目及答案

QwertyuiopasdfghjklzxcvbnmqwertyuiopasdfghjklzxcvbnmqwertyuiopasdfghjklzxcvbnmqwertyuiopasdfghjklzxcvbnmqwertyuiopasdfghjklzxcvbnmqwertyuiopasdfghjklzxcvbnmqwertyuiopasdfghjklzxcvbnmqwertyuiopasdfghjklzxcvbnmqwertyuiopasdfghjklzxcvbnmqwertyuiopasdfghjklzxcvbnmqwertyuiopasdfghjklzxcvbnmqwertyuiopasdfghjklzxcvbnmqwertyuiopasdfghjklzxcvbnmqwertyuiopasdfghjklzxcvbnmqwertyuiozxcvbnmqwertyuiopasdfghjklzxcvbnmqwertyuiopasdfghjklzxcvbnmqwertyuiopasdfghjklzxcvbnmrtyuiopasdfghjklzxcvbnmqwertyuiopasdfghjklzxcvbnmqwertyuiopasdfghjklzxcvbnmqwertyuiopasdfghjklzxcvbnmqwertyuiopasdfghjklzxcvbnmqwertyuiopasdfghjklzxcvbnSinciscoACM答案2010/11/10Sincisco小组成员排球队员站位问题i【题目】排球队员站位问题┏━━━━━━━━┓图为排球场的平面图，其中一、二、三、四、五、六为位置编号，┃┃二、三、四号位置为前排，一、六、五号位为后排。某队比赛时，┃┃一、四号位放主攻手，二、五号位放二传手，三、六号位放副攻┠──┬──┬──┨手。队员所穿球衣分别为１，２，３，４，５，６号，但每个队┃四│三│二┃员的球衣都与他们的站位号不同。已知１号、６号队员不在后排，┠──┼──┼──┨２号、３号队员不是二传手，３号、４号队员不在同一排，５号、┃五│六│一┃６号队员不是副攻手。┗━━┷━━┷━━┛编程求每个队员的站位情况。【算法分析】本题可用一般的穷举法得出答案。也可用回溯法。#includecstdlib#includeiostreamusingnamespacestd;intcounter=0;voiddisplay(intplace[]){for(inti=1;i=6;i++){coutplace[i]\t;if(i%3==0)cout\n;}coutendl;}booljudge(intmark,intplace[]){switch(mark){case1:returntrue;case2:returnplace[2]!=5&&place[2]!=6;case3:returnplace[3]!=2&&place[3]!=3;case4:returnplace[4]!=1&&place[4]!=2&&place[4]!=3&&place[4]!=6;case5:returnplace[5]!=1&&place[5]!=5&&place[5]!=6;case6:returnplace[6]!=1&&place[6]!=6;}}boolothers(intplace[]){intm=1,n=1;for(inti=0;i=6;i++){if(place[i]==3)m=i-1;if(place[i]==4)n=i-1;}returnm/3!=n/3;}voidbacktrace(intmark,intplace[],intpeople[]){for(inti=1;i=6;i++){if(people[i]!=0){place[mark]=people[i];if(judge(mark,place)){if(mark==6&&others(place)){counter++;display(place);}else{people[i]=0;backtrace(mark+1,place,people);people[i]=i;}}}}}intmain(intargc,char*argv[]){int*place=newint[7];int*people=newint[7];for(inti=1;i=6;i++)people[i]=i;backtrace(1,place,people);coutThetotalmethodsiscounterendl;system(PAUSE);returnEXIT_SUCCESS;}数字布置问题【题目】把1-8这8个数放入下图8个格中,要求相邻的格(横,竖,对角线)上填的数不连续.┌─┐│①│┌─┼─┼─┐│②│③│④│├─┼─┼─┤│⑤│⑥│⑦│└─┼─┼─┘│⑧│└─┘#includecstdlib#includeiostreamusingnamespacestd;voiddisplay(intfield[],intmark){for(inti=1;i=mark;i++)coutfield[i]\t;coutendl;}boolcontinues(intm,intn){if((m-n==-1)||(m-n==1)){returntrue;}else{returnfalse;}}booljudge(intmark,intfield[]){switch(mark){case1:returntrue;case2:returntrue;case3:if(continues(field[3],field[1])||continues(field[3],field[2]))returnfalse;elsereturntrue;case4:if(continues(field[3],field[4]))returnfalse;elsereturntrue;case5:if(continues(field[5],field[2]))returnfalse;elsereturntrue;case6:if(continues(field[3],field[6])||continues(field[5],field[6]))returnfalse;elsereturntrue;case7:if(continues(field[7],field[4])||continues(field[7],field[6]))returnfalse;elsereturntrue;case8:if(continues(field[8],field[6]))returnfalse;elsereturntrue;}}voidbacktrace(intnum[],intfield[],intmark){for(inti=1;i=8;i++){if(num[i]!=0){field[mark]=num[i];if(judge(mark,field)){if(mark==8)display(field,mark);else{num[i]=0;backtrace(num,field,mark+1);num[i]=i;}}}}}intmain(intargc,char*argv[]){int*num;int*field;num=newint[9];field=newint[9];for(inti=0;i9;i++){num[i]=i;}backtrace(num,field,1);system(PAUSE);returnEXIT_SUCCESS;}改错题下列程序的功能是：一只甲虫在一个迷宫(一个10×10的矩阵表示)中移动，迷宫中有若干个柱子（在矩阵中表示为值为1的单元）。甲虫从迷宫中的某个位置出发，按照预先设置的指令在迷宫中行进：指令是一串由1~4组成的数字，分别代表行进的4个方向：1代表向上，2代表向右，3代表向下，4代表向左。当按照移动指令移动后的位置是一个柱子或超出了迷宫的范围则忽略该步指令。最终程序将显示指令序列结束后的甲虫所处的位置。修改后的结果：#includeiostream.hintm[5][5]={1,0,0,1,0,0,1,0,1,1,0,0,0,0,0,1,0,1,0,0,0,1,1,0,0};//迷宫，1－柱子intisPole(intx,inty){if(m[x][y]==1)return1;elsereturn0;}voidmove(intd[],intx[2],intn){intnx,ny;for(inti=0;in;i++){switch(d[i]){case1:ny=x[1]-1;break;case2:nx=x[0]+1;break;case3:ny=x[1]+1;break;case4:nx=x[0]-1;break;default:break;}if(isPole(nx,ny)||nx0||nx4||ny0||ny4)continue;x[0]=nx;x[1]=ny;}}voidmain(){intx[2];intd[]={2,2,3,3,1,3,3,4,4,1,2,3,2,2,4};//指令集cout输入初始位置:;cinx[0]x[1];move(d,x,sizeof(d[0])/sizeof(d));coutThefinalpositionis:x[0],x[1]endl;}2、给定一个整数n，求出所有连续的且和为n正整数。比如对于整数27，结果为2~7、8~10、13和14，因为这些数之间的整数的和都是27。注意：并不是所有的整数都有结果，例如不存在连续的整数和为16。为了提高计算的效率，程序所采用的算法如下：(1)从1开始计算连续的整数和sum，直到sum不小于n为止；(2)在第i步，如果sum=i+(i+1)+…+j比n大，则去掉连加的最左端的数i，如果sum比n小，在连加的右端加上一个数(j+1)；(3)如果和sum=i+(i+1)+…+j等于n，则i+(i+1)+…+j为一组解，输出该解，并将连加的右端加上(j+1)；(4)重复2，3步，直到i大于n/2为止。#includecstdlib#includeiostreamusingnamespacestd;voiddispaly(intleft,intright,intnum){cout第num组解为：;for(inti=left;i=right;i++){couti\t;}coutendl;}voidtemp(intn){intleft=1;intright=1;intsum=1;intnum=0;for(;left=n/2;){if(sumn){right++;sum=sum+right;}if(sumn){sum=sum-left;left++;}if(sum==n){num++;dispaly(left,right,num);sum=sum-left;left++;}}}intmain(intargc,char*argv[]){intn;cout给定的整数为：endl;cinn;temp(n);system(PAUSE);returnEXIT_SUCCESS;}3、北大3051SatellitePhotographsDescriptionFarmerJohnpurchasedsatellitephotosofWxHpixelsofhisfarm(1=W=80,1=H=1000)andwishestodeterminethelargest'contiguous'(connected)pasture.Pasturesarecontiguouswhenanypairofpixelsinapasturecanbeconnectedbytraversingadjace