清华机试题目

2015年详见2015清华复试机试题.pdf2014年(回忆版)首先，机试使用的是C++语言，编译器和DEV-CPP5.4.0是一样的，当然机器上也有VC++VS等环境可以使用，那就自行确保程序的正确性了，因为提交后不会给任何反馈信息，只显示已提交。（从2014年的机试开始，清华已经不再沿用原来的机试方案了，改为了CCF软件能力测试（详见：）。4小时5道题，不像其他OJ会反馈程序的结果，没有任何得分信息）。1.n个数中相反数的对数。输入n个不同数，求这n个数中相反数的对数。比如1和-1是一对相反数，这些数的绝对值小于1000。2.窗口层次问题：像windows窗口一样，同一个点有可能有多个窗口叠加，此时点击这个点，位于该点顶层的窗口会被选中，同时直接到最顶层来。输入n个窗口的对角坐标（x1，y1）（x2，y2）(x1x2y1y2)和m个点击坐标（顺序点击）。输出每次选中的窗口编号（按照窗口输入顺序1-n编号）若点击的地方没有任何窗口，就输出“XXXX”（这里字符串忘记了）3．命令行命令选项问题:直接上测试用例解释,以下是输入albw:x//这一行是声明有效的选项字母，每个单个字母都是一个有效选项，后带冒号的意味带参数，因此w选项带参数ls–b-a–w15–w20document–l//输入的命令针对上面一行的输出为Case1:-a–b–w20Ls是工具命令不用处理–a–b都是合法选项，所以输出。document是非法，遇见非法字符后不再分析后面的-l，输出时按字母顺序，有参数的还需要输出最后一次出现的有效参数，上例中w最后一次出现时带的参数是20故输出20。下面有多行ls就依次输出Case2Case3等等4.无线网络：输入n个路由器的坐标x和y,以及每个路由器收发半径r,收发半径之内的路由器可以相互直接联系。再输入m个坐标，这m个坐标中可以最多再添加K个路由器。最终计算输入的第一个路由器和第二个路由器(输入时的顺序)之间的最短路径长度(需要经过的其他路由器的个数+1)。5.作业调度问题：一个计算机有2个CPU和1个GPU输入n，然后接下来n行，输入每个任务的abcd.(abcd均在10以内)，含义为a：用单个CPU完成所需时间。b：用2个CPUc：用单个CPU+GPUd：用2个CPU+1个GPU。这n个任务的处理顺序可以打乱，意思就是两个任务可以使用aa、ac、ca这三种方式并行执行。也可以选择bd中较短的时间串行执行。最终计算n个任务全部执行完所需的最短时间PS：今年清华机试变成CCF软件能力认证测试，考试时间为4个小时，题目提交后也不给任何信息，只显示已提交。2012年题目1483：求最大最小数输入N个（N=10000）数字，求出这N个数字中的最大值和最小值。每个数字的绝对值不大于1000000。#includestdio.h#includestdlib.h#includelimits.hintFindMinMax(longlongintA[],intsize,longlongint&min,longlongint&max){min=A[0];max=A[0];for(inti=1;isize;i++){if(A[i]max){max=A[i];}if(A[i]min){min=A[i];}}return0;}intmain(){inti,N;longlongintmin,max;longlongintArray[10001];while(scanf(%d,&N)!=EOF){for(i=0;iN;i++){scanf(%lld,&Array[i]);}FindMinMax(Array,N,min,max);printf(%lld%lld\n,max,min);}//whilereturn0;}题目1482：玛雅人的密码玛雅人有一种密码，如果字符串中出现连续的2012四个数字就能解开密码。给一个长度为N的字符串，（2=N=13）该字符串中只含有0,1,2三种数字，问这个字符串要移位几次才能解开密码，每次只能移动相邻的两个数字。例如02120经过一次移位，可以得到20120,01220,02210,02102，其中20120符合要求，因此输出为1.如果无论移位多少次都解不开密码，输出-1。#includeiostream#includecstring#includequeueusingnamespacestd;constintN=1600000;boolused[N];intn;typedefstructNode{intnum,cnt;chararr[14];}Node;queueNodeQ;voidswap(char*str,inti,intj){inttemp=str[i];str[i]=str[j];str[j]=temp;}booltest(char*str){for(inti=0;i=n-4;i++){if(str[i]=='2'&&str[i+1]=='0'&&str[i+2]=='1'&&str[i+3]=='2')returntrue;}returnfalse;}intstringToInt(char*str){intres=0;for(inti=0;str[i];i++){res=3*res+str[i]-'0';}returnres;}intbfs(){while(!Q.empty()){Nodetemp=Q.front();intcnt=temp.cnt;Q.pop();if(test(temp.arr)){returntemp.cnt;}for(inti=0;in-1;i++){swap(temp.arr,i,i+1);intnum=stringToInt(temp.arr);if(!used[num]){used[num]=true;Nodetemp1;temp1.cnt=cnt+1;strcpy(temp1.arr,temp.arr);temp1.num=num;Q.push(temp1);swap(temp.arr,i,i+1);}else{swap(temp.arr,i,i+1);}}}return-1;}intmain(intargc,char*argv[]){while(cinn){charstr[14];cinstr;if(n4){cout-1endl;continue;}memset(used,0,sizeof(used));while(!Q.empty())Q.pop();Nodenode;intnum=stringToInt(str);used[num]=true;node.num=num,node.cnt=0;strcpy(node.arr,str);Q.push(node);intres=bfs();coutresendl;}return0;}题目1491：求1和2的个数给定正整数N，函数F(N)表示小于等于N的自然数中1和2的个数之和，例如：1,2,3,4,5,6,7,8,9,10序列中1和2的个数之和为3，因此F(10)=3。输入N，求F(N)的值，1=N=10^100(10的100次方)若F(N)很大，则求F(N)mod20123的值。#includecstdio#includecstring#includecmath#includestringusingnamespacestd;#defineMOD20123into[201];intjudge(char*str){inti,mod,len;len=strlen(str);mod=0;for(i=0;i=len-1;i++){mod=(mod*10+str[i]-'0')%MOD;}returnmod;}intdfs(char*str){intlen,sum;len=strlen(str);if(len==1){if(str[0]='1')return1;elsereturn0;}sum=(len-1)*o[len-2];if(str[0]=='0')returndfs(str+1)%MOD;elseif(str[0]=='1')return(sum+judge(str+1)+1+dfs(str+1))%MOD;elseif(str[0]'1')return((str[0]-'0')*sum+o[len-1]+dfs(str+1))%MOD;return0;}intdfs2(char*str){intlen,sum;len=strlen(str);if(len==1){if(str[0]='2')return1;elsereturn0;}sum=(len-1)*o[len-2];if(str[0]=='0')returndfs2(str+1)%MOD;elseif(str[0]=='1')return(sum+dfs2(str+1))%MOD;elseif(str[0]=='2')return(2*sum+judge(str+1)+1+dfs2(str+1))%MOD;elseif(str[0]'2')return((str[0]-'0')*sum+o[len-1]+dfs2(str+1))%MOD;return0;}intmain(){charstr[201];inti;o[0]=1;for(i=1;i=101;i++)o[i]=(10*o[i-1])%MOD;while(scanf(%s,str)!=EOF)printf(%d\n,(dfs(str)+dfs2(str))%MOD);return0;}2011年题目1086：最小花费在某条线路上有N个火车站，有三种距离的路程，L1，L2，L3,对应的价格为C1,C2,C3.其对应关系如下:距离s票价0S=L1C1L1S=L2C2L2S=L3C3输入保证0L1L2L310^9,0C1C2C310^9。每两个站之间的距离不超过L3。当乘客要移动的两个站的距离大于L3的时候，可以选择从中间一个站下车，然后买票再上车，所以乘客整个过程中至少会买两张票。现在给你一个L1，L2，L3，C1，C2,C3。然后是AB的值，其分别为乘客旅程的起始站和终点站。然后输入N，N为该线路上的总的火车站数目，然后输入N-1个整数，分别代表从该线路上的第一个站，到第2个站，第3个站，……，第N个站的距离。根据输入，输出乘客从A到B站的最小花费。#includeiostream#defineMAXN2211686018427387904#defineMAXS30000longlongl1,l2,l3,c1,c2,c3,rout[MAXS];longlongspe(intstart,intend){inttemp=rout[end]-rout[start];if(temp=l1){returnc1;}if(temp=l2){returnc2;}if(temp=l3){returnc3;}returnMAXN;}usingnamespacestd;intmain(intargc,char*argv[]){longlongtemp,i,j,a,b,n,spend[MAXS];while(cinl1l2l3c1c2c3){for(i=temp=0;iMAXS;i++){rout[i]=spend[i]=MAXN;}cinab;cinn;rout[1]=0;for(i=2;i=n;i++){cinrout[i];}for(i=a,spend[a]=0;ib;i++){for(j=i+1;rout[j]-rout[i]=l3&&jMAXS;j++){temp=spe(i,j);if(spend[j]temp+spend[i]){spend[j]=temp