浙江大学10年计算机上机题(含答案).pdf

《浙江大学10年计算机上机题(含答案).pdf》由会员分享，可在线阅读，更多相关《浙江大学10年计算机上机题(含答案).pdf（25页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、一、A+B题目描述:给定两个整数A和B,其表示形式是：从个位开始，每三位数用逗号，”隔开。现在请计算A+B的结果，并以正常形式输出。输入：输入包含多组数据数据，每组数据占一行，由两个整数A和B组 成(-1 0人9 A,B1 0A9)o输出：请计算A+B的结果，并以正常形式输出，每组数据占一行。样例输入：-2 3 4,5 6 7,8 9 0 1 2 3,4 5 6,7 8 91,2 3 4 2,3 4 5,6 7 8样例输出：-1 1 1 1 1 1 1 0 12 3 4 6 9 1 2答案：给大家记住数据吧，如果你是用高进度计算的。注意：你的结果是否有前缀0；0 是否带负号；999 110,0

2、00-900-0-00-01999 1010,001-10,000#include#inciude#include#includeusing namespace std;int main()(string strA,strB;while(cinstrAstrB)long numA=0;for(int i=0;i=strA.length()-l;i+)(if(strAi=0)(numA=numA*10+strAi-O;)long numB=0;for(int/去掉否则出现变量重复 i=0;i=strB.length()-l;i+)(if(strBi=(X)(numB=numB*10+strBi-

3、O;)if(strAO&strBO!=,-,)/+coutnumA+numBendl;if(strAO!=&strBO=-)+-coutnumA-numBendl;if(strAO=r-*&strBO!=-,)/-+coutnumB-numAendl;if(strAO=&strBLO=,)-cout0-(numA+numB)endl;)return 0;)已AC1.可以用sscanf把字符串转换为int,然后直接加就可以了2.#include 3.#include 4.#include 5.6.using namespace std;7.8.const int Maxn=50;9.int ma

4、in()10.11.12.13.14.15.16.17.18.19.20.21.22.23.24.25.26.27.28.29.30.31.1.2.3.4.5.6.7.char strlMaxn,str2Maxn;char tempMaxn;int a,b,i,r;while(s canf(H%s%s,st rl,str2)!=EOF)(int len=strlen(strl);memset(temp,0,sizeof(temp);r=0;for(i=0;ilen;i+)if(strli!=*,)tempr+=strli;sscanf(temp,%dmemset(temp,0,sizeof(t

5、emp);r=0;for(i=0;istrlen(str2);i+)if(str2i!=,*)tempr+=str2i;sscanf(temp,%d,&b);couta+bendl;return 0;#include#includeint sw(char*a)int i=0,c=0;while(ai)if(ai=,0&ai=9)c=c*10+ai-,0,;8i+；9.)10.if(a0=-)11.c=-c;12.return c;13.)14.int main()15.char a99,b99;16.int al?bl?c99i=0;17.while(scanf(%s%s”,a,b)!=EOF

6、)18.al=sw(a);19.bl=sw(b);20.21.ci=al+bl;22.i+;23.for(int j=0;ji;j+)24.printf(%drf，cj);25.return 0;26.复制代码A C 了二、ZOJ问题题目描述：对给定的字符串(只包含2,。力 三种字符)，判断他是否能AC。是否AC的规则如下：1.zoj 能 AC；2.若字符串形式为xzqjx,则也能A C,其中x可以是N个。或者为空;3.若azbjc能A C,则azbojac也能A C,其中a,b,c为N个o或者为空;输入:输入包含多组测试用例，每行有一个只包含z o力 三种字符的字符串，字符串长度小于等于lO

7、OOo输出：对于给定的字符串，如果能AC 则请输出字符串Accepted,否则请输出/zWrong Answer”。样例输入：z o jo z o j oo z o o j o oo o z o o j o o o oz o o jo z o j oo o o o z o j oz o j o o o o样例输出：Ac c e p t e dAc c e p t e dAc c e p t e dAc c e p t e dAc c e p t e dAc c e p t e dW r o n g An s w e rW r o n g An s w e r答案：下面代码AC过了，需要考虑的问

8、题很多，需要注意的地方我都加注释了1.#include2#include3#includeusing namespace std;5int main()6string ins;7while(cinins)11.8.size_t len=in s.s iz e()-l;9.size_t bz=in s.fin d _ first_ o f(z);10.size_t bj=in s.fin d _ first_ o f(j);16.12.if(bz=string:npos|bj=string:npos)/SW z,j-定错13.coutWrong Answernendl;14.continue;1

9、5.)17.bool flag=true;18.fo r(in t i=bz+l;i=len;i+)19.if(in s.a t(i)=z)20.flag=false;21.)22.fo r(in t i=bj+l;i=len;i+)23.if(in s.a t(i)=j)24.flag=false;25.)26.if(flag=fa lse)只能出现一个 z,一个 j27.coutWrong Answer,endl;28.continue;29.)30.if(b j b z)/z 在 j 前31.coutWrong Answerendl;32.continue;33.)34.35.36./*

10、z 前 o 个数为el,z j之间o 个数为e2,j 之后o 个数为e3+/37.size_t el=bz;38.size_t e2=bj-bz-1;39.i f (e2=0)/z,j 之间o 的个数至少一个40.coutWrong Answerendl;41.continue;42.)43.size_t e3=len-bj;44.int x=e2;45.if(el*x=e3)coutxAcceptecTendl;实际上题目的三个条件可以得出 el*e2=e346.else coutWrong Answerendl;47.)48.return 0;49.用 C+string类进行判别可以写出非

11、常简介的算法1.#include 2.#include 3.#include 4.using namespace std;5.int main(int argc,char*argv)6.7.ifstream cin(*input.txt);8.string s;9.while(cins)10.11.12.13.14.15.16.17.18.size_t p,q;p=s.find(z);q=s.find(j);while(int)(q-p)2)(s.erase(int)(q+l),(int)p);s.erase(int)(p+1),1);p=s.find(z);19.q=s.find(j);20

12、.)21.if(p=(s.size()-q-l)&(q-p)=2)22.coutAcceptedn;23.else24.coutWrong Answern;25)26.最简洁的：#include#includeint main()char strflOOO;int x=0,y=0,z=0;int length,i；while(gets(str)!=NULL)length=strlen(str);for(i=0;i0)printf(nAcceptedn);)elseprintf(HWrong Answernn);另:考虑y0的情况，比喻输入zj给出我的AC代码，用的纯C,条件二、三可合并到一个条

13、件里1.#include 2.#include 3.char s1001;4.int main()5.6.int ajb,c;7.char+p;8.while(scanf(%5,5)!=EOF)9.if(!strcmp(s,zoj)printf(HAcceptedn);continue;条件10.11.a=b=c=0;12.p=s;13.while(*p=,o)a+;p+;a 为 第 个 z 前 o 的个数14.if(*p=z)15.p+;16.while(*p=o)b+;p+;/b 为夹在 z 和 j 之间的 o 的个数17.if(*p=,j)18.p+;19.while(*p=o )c+;

14、p+;/c 为 j 之后的 o 的个数20.if(!(*p)&b0&c=a*b)printf(Acceptedn);continue;条件三21.)22 23.printf(Wrong Answern);24.25.return 0;26.三、奥运排序问题题目描述:按要求，给国家进行排名。输入：有多组数据。第一行给出国家数N,要求排名的国家数M,国家号从0到N-1。第二行开始的N行给定国家或地区的奥运金牌数，奖牌数，人 口 数（百万）。接下来一行给出M个国家号。输出：排序有4种方式：金牌总数奖牌总数金牌人口比例奖牌人口比例对每个国家给出最佳排名排名方式和最终排名格式为：排名:排名方式如果有相同

15、的最终排名，则输出排名方式最小的那种排名，对于排名方式，金牌总数 奖牌总数 金牌人口比例 奖牌人口比例如果有并列排名的情况，即如果出现金牌总数为1 0 0,9 0,9 0,8 0.则排名为L2,2,4.每组数据后加一个空行。样例输入：4 44 8 16 6 24 8 22 1 2 40 1 2 34 28 1 0 18 1 1 28 1 2 38 1 3 40 3样例输出：1:31:12:11:21:11:1答案:1.看中文题目都那么费力气，我草！2.需要特别注意的地方是，只在要求排名的国家里面排名，其他不需要排名的直接忽略,。3.当时我没仔细看到这点，wa 了 N次，暴怒到想砸电脑 4.注意

16、要用double,因为float精度是不够的，般涉及到浮点的，最好都用double5.还有注意处理重熨排名：6./if(Pj.God=Pj-1.God)rankj=rankj-1;7./else rankj=j+1;8.9.#include 10.#include 11.#include 12.#include 13.14.using namespace std;15.16.const int Maxn=100000;17.18.struct Con19.double God,Pri,Peo;20.double Godper,Peoper;21.int id;22.)PMaxnrpMaxn;2

17、3.int rankMaxn;24.int N,M;25.26.bool cmp(const Con a,const Con b)27.(28.return a.Peoperb.Peoper;29.30.31.bool cmpl(const Con a,const Con b)32.33.return a.Godperb.Godper;34.35.36.bool cmp2(const Con a,const Con b)37.38.return a.Prib.Pri;39)40.bool cmp3(const Con a,const Con b)41.42.return a.Godb.God;

18、43.)44.45.int main()46.47.int i,indexMaxn,j;48.int bet,way;49.while(scanf(%d%d“，&N,&M)!=EOF)50.51.for(i=0;irpi.Godrpi.Prirpi.Peo;54.rpi.Godper=rpi.God/rpi.Peo;55.rpi.Peoper=rpi.Pri/rpi.Peo;56.57.int r=0；58.for(i=0;iindexi;61.Pr=rpindexi;62.Pr+.id=indexi;63.64.65.for(i=0;iM;i+)66.67.68.69.70.71.72.73

19、.74.75.76.77.78.79.80.81.82.83.84.85.86.sort(P,P+M,cmp3);rank0=1;for(j=1;jM;j+)if(Pj.God=Pj-1.God)rankj=rankj-1;else rankj=j+1;for(j=0;jM;j+)if(Pj.id=indexi)bet=rankj;way=1;break;)sort(P,P+M,cmp2);rank0=1;for(j=1;jM;j+)if(Pj.Pri=Pj-1.Pri)rankj=rankj-1;else rankj=j+1;for(j=0;jM;j+)if(Pj.id=indexi)87.

20、if(rankjbet)88.89.bet=rankj;90.way=2;91.)92.break;93.)94.sort(Pj P+Mcmpl);95.rank0=1;96.for(j=1;jM;j+)97.if(Pj.Godper=Pj-1.Godper)rankjrankj-l;98.else rankj=j+1;99.for(j=0;jM;j+)100.if(Pj.id=indexi)101.102.if(rankjbet)103.104.bet=rankj;105.way=3;106.107.break;108.)109.sort(P,P+M,cmp);110.rank0=1;111

21、.for(j=1;jM;j+)112.if(Pj.Peoper=Pj-1.Peoper)rankjrankj-l;113.else rankj=j+1;114.for(j=0;jM;j+)115.if(Pj.id=indexi)116.117.if(rankjbet)118.119.bet=rankj;120.way=4;121.122.break;123.)124.p rin tf(%d:%dnbetway);125.126.p rin tfC X n);127.128.129.return 0;130.另：这题要注意两点：1、只对要求的m 个国家排序，未要求的国家不管。2、奖牌人口比例计算

22、机时精度问题。可以采用纯数学的方法，通过通分比较分子，就不会有精度问题了。#includeusing namespace std;struct nation int gold;int total;int popu;)；int main()(int n,m;while(cinn)(cinm;nation*records=new nationn;int(*ranks)5=new intm5;/read datafor(int i=0;in;i+)cinrecordsi.goldrecordsi.totalrecordsi.popu;for(int i=0;im;i+)cinranksiO;/ran

23、kingfor(int i=0;im;i+)(ranksil=ranksi2=ranksi3=ranksi4=l;for(int j=0;jrecords ranksi0.gold)ranksil+;if(records ranksj0.totalrecords ranksiO.total)ranksi2+;int numerator 1,numerator?;numeratorl=records ranksj0.gold*records ranksil(0.popu;numerator2=records ranksi0.gold*records ranksj0.popu;if(numerat

24、or 1 numerator2)ranksi3+;numerator 1 =records ranksj0.total*records ranksi0.popu;numerator2=records ranksi0.total*records ranksj0.popu;if(numeratorlnumerator2)ranksiJl4+;)/output the resultsfor(int i=0;im;i+)(int best=ranksliJll,method=1;for(intj=2;j5;j+)if(ranksijbest)(best=ranksijj;method=j;)coutb

25、est:m ethodendl;)coutendl;/one case is finished/loop terminatedreturn 0;)四、最短路径问题题目描述：给你n个点，m条无向边，每条边都有长度d和花费p,给你起点s终点t,要求输出起点到终点的最短距离及其花费，如果最短距离有多条路线，则输出花费最少的。输入：输入n,m,点的编号是ln,然后是m行，每行4个 数a,b,d,p,表示a和b之间有一条边，且其长度为d,花费为p。最后一行是两个数s,t;起点s,终点t。n和m为0时输入结束。(ln=1000,0m 100000,s!=t)输出：输出一行有两个数，最短距离及其花费。样例输

26、入：3 212 5 62 3 4 51 30 0样例输出：9 11答案：题目距离d和花费p没有给出取值范围，所以在初始化的时候表示最大距离和花费的无穷大用(-1)或者设置尽可能大的数。下面是代码，思想很简单就是邻接矩阵存储，然后在dijkstra算法上增加花费条件判断。1.#include 2.#define N 10013.#define MAX 1000000004.#define INF 10000000005.typedef struct(6.int dist;7.int expend;8.edge;9.edge arcsNN;10.int start,end,n,m;11.void

27、dijkstra()12.int sn;13.edge dn;14.int15.int min;16.v=start-1;17.for(i=0;i n;i+)18.di=arcsvi;19.)20.for(i=0;i n;i+)si=0;21.sv=1;dv.dist=0;dv.expend=0;22.for(i=0;i n-1;i+)23.min=INF;24.for(j=0;j=0)&(dj.dist min)26.min=dj.dist;27.k=j;28.29.sk=1;30.for(j=0;j dk.dist+arcskj.dist)32.dj.dist=dk.dist+arcskj

28、.dist;33.dj.expend=arcskj.expend+dk.expend;34.)35.else if(sj=0)&(dj.dist=dk.dist+arcskj.dist)36.if(dj.expend arcskj.expend+dk.expend)37.dj.expend=arcskj.expend+dk.expend;38.39 40.41.printf(%d%dn,?dend-1.dist,dfend-1.expend);42.)43.int main()44.int45.int i,j;46.while(scanf(%d%cT，&n,&m)!=EOF)47.if(n=0

29、&m=0)return 0;48.for(i0;i n；i+)49.for(j0；j n;j+)(50.arcsij.dist=MAX;51.arcsij.expend=MAX;52.53.)54.for(i=0;i&start,&end);62.dijkstra();63.64.return 0;65.邻 接 表+Dijstra+优先队列，效率应该比较可以，果断AC!1#include23456#include#include/#include#include#include7#include8#include9using namespace std;10.11.#define12.#def

30、ine13.#define14.15.typedef16.in t17.18.19.20.eid;stru ct Tab*next;Tab():构造函数e id(-1)?next(NULL)tab;INF(K O O)MAXM 100002MAXN 1002stru ct Tab21.22.in t uMAXM,vMAXM,dMAXM,pMAXM;23.in t n,m;24.in t s,t;25.26.typedef p a ir p ii;27.priority_queue pii?vector greater PQ;28.29.bool visMAXN;30.in t disMAXN;

31、31.in t valMAXN;32.33.in t main()34.35./fre o p e n(jd o j1008.i n r ,std in);36.while(scanf(%d%d&n,&m),n&m)37.38.tab firstM A X N;构造函数已经初始化了，不需要再次初始化39./read_graph40.fo r(in t e=l;eeid=e;46.q-next=fir s tu e .next;47.fir s tu e .next=q;74.49.q=(tab*)m alloc(sizeof(tab);50.q-eid=e;51.q-next=fir s tv

32、 e .next;52.fir s tv e .next=q;53.54.scanf(%d%d&s,&t);起始地点和终止地点55.memset(vis,0,sizeof v is);56.fo r(in t i=l;inext)69.70.in t e=eq-eid;71.in t ve=(ve!=x?ve:u e);72./p rin tf(%d%d-%d%d*n,ve,u e,v e,x);73.if(d is v e d isx+d e)75.disve=disx+de;更新距离76.valve=valx+pe;更新费用77.PQ.push(make_pair(dve,ve);加入优先

33、队列78.79.else if(disve=disx+de)距离相等的情况下，选费用小的80.81.if(valve valx+pe)82.83.valve=valx+pe;更新费用84.PQ.push(make_pair(dve,ve);加入优先队列85.86.87.88.89.printf(*%d%dn dist,valt);90./*for(int i=l;i%cT,q-eid);97.q=q-next;98.99.printf(unH);100.101.*/102./while(l);103.return 0;104.五、找出直系亲属题目描述：如果A,B是C的父母亲，则A,B是C的pa

34、rent,C是A,B的child,如果A,B 是 C 的(外)祖父，祖母，则 A,B 是 C 的 grandparent,C 是 A,B 的 grandchild,如果A,B是C的(外)曾 祖 父，曾祖母，则A,B是C的great-grandparent,C是A,B great-grandchild,之后再多一辈，则在关系上加一个great-。输入：输入包含多组测试用例，每组用例首先包含2个整数n(0=n=26)和m(0m 0 表明前者为父母，级差为 aint b=getRelation(s 1 -A,s0-A,);/b0 表明后者为父母,级差为 bint re=ab?a:b;if(re0)前者为父母)return 0;（不能假设只有一棵树）if(re=l)printf(nparentnn);else if(re=2)printf(grandparentn);else while(re!=2)re-;printf(great-n);printf(,grandparentn);)if(b0)后者为父母if(r e=i)printf(HchildnM);else if(re=2)printf(grandchildnn);else while(re!=2)re-;printf(great-u);)printf(ngrandchildnu);)