ACM常见题型题解

1、大部分题目都来源于周涵学弟，感谢他的成果，希望大家不断a 题，提升自己的能力，都能在校赛上取得好的成绩。这次比赛很多童鞋都做的很好，不过通过做题也能反映出一些问题。很多童鞋交了发现自己的数据爆值，很多时候是因为没有好好读题。int , long, long long 的范围应该都知道，如果只是因为没有好好读题而出错， 这是毫无意义的罚时，所以一定好好好读题，看清数据范围。第二，跟榜。在正式的比赛中题目的难度并不是按照 ABCD 来排列的，简单的题目可能在中 间，在最后，所以不要死一道题，而是看题目的通过人数，这是判断题目难度的 最好方法，就是跟榜。第三， 扩充自己的知识面。很多题目用你现有的知

2、识可能很难做出来， 但是用一些语言自带的函数或者容器 就能简单的做出来了。 这就需要不断学习， 多多接受一些新的东西并用到题目当 中，会有很好的收获的。还发现了一些同学有抄袭现象， 在正式比赛中所有的题目都是原创的， 并且不可 以上网寻求帮助， 只能带纸质材料。 所以还是珍惜每一次做题的机会， 认真的去 对待吧。A ：本道题目需要注意 1<=n<=1000, 而 1 既不是素数也不是合数， 2 是最小的素数13456T&510111?IS工性151617IS192021222324tincliidecscdic. h>Tilt main (Trai d)int fla

3、gy 1; long n*while (scanf 5 "Sn) i=EOFi f Eln- = 1 JIelse if Hii=2>pxintf("Yes'n)； elaelfor i=;i<rL； i亠亠 j iif0令i=o)toreak;if 3.=njpTintfI"Y&m'n");elseTirintf 1 "Na、：!"：return 0;B:方法采用辗转相除法求的最大公约数，最小公倍数采用：给定的两数之积除以最大公约数。include <5tdio.h »int ma

4、 in(void)int Xj y,tempi,tempi,numl.r112;int rj,讪ik齿“nFr蒯 Scl4rdml,!-E<?F)rnumnuml;templ=numlitern p3=riLim2;whilc(r! =&i)iriLjm2=numl$ numlr; r=nuiii256numl;printf( "%d 霜d'rTjnuinljlUmpl/tmpXMrujni：)；return 0：C:字符串比较大小问题，在C语言中可以调用头文件<string.h>中的strcmp函数直接进行比较。字符串的取缔符号为 %s。inclu

5、destdio.h > #incLude-istring . h> int ma in(void)chgr sl21>s2E21; while<scanfC"aes Ses£l,s3) 3 =EOF)if tstrciiip(slj52j<& prirrtf r卷為5口"严.垃)7 else if(strcnp(sl|s2 J=0) prin-tf(-%s=Ssn"slj52)； elsep Kntf('-Xs>%5r '£l,s2);return 0;D:此题为排序题，可以采用冒泡排

6、序法，在C+直接有sort排序函数，可以直接调用。#inclLidef5tdi<j.h> S：include<io stream *tirclude<algo ri thTi? using namespace int mainvoid)int5canfC'%dscarif L%d"/盘日i); sor t f a ,aHn);i -)printf("Kd prir,-tf("9td，na6);return 0；E:学一下结构体排序的方法，顺便自学一波stirng类型#xnclude<stdio.h> #include&l

7、t;algcirithm> # irLclTide<icis t-ream> #include<string> using- nJiespies strue L Strstd.;iiit iLuirL/ 5tring ss;str105;bool Gmp(Sti A,Str B1 f (A. numre Lurt'j A* ss < B,ss; retur口 A. nunL < S.numJin; main ()ill n.; scanfin);:(Int i = 0Fi<n7i+4)cxn>>shr i . ss>&g

8、t;stj： Fi 1 . nunL/sort(str, str+n, for (int icmp;< nF i +Gou±«si; r i ss«" '«stri -nujn<<endl;rectum 0;* 1F:斐波那契数列采用递归计算法，应题目要求进行取余（因为在计算过程中可能为出现溢 出）#inciude< stdi口.h > ini main(voidint ai;a«l;if fnz0ifiri=2)Z；an;x-t+fl ；M=)dSlW9©0th97iG:矩阵采用二位数

9、组输入模式，根据二位数组索引值，得出计算规律。需要注意的是：可 能出现10的10次方，所以不要用int。4inclijde< stdio . h >int main(void!)'intlong long sunl, 5Uin2jfor(i-ai<rji+) for(j=6;j<n;+)<5uinJ=I; suni2-l; “0； for(x-05x<njx+)5u(nl*«ax sc; fory=ri-l jy>=0;y- *)suin2*=a2+ y ; printf(%lldmumN); returnH:对于每一个点遍历一遍这个

10、点周围的点，然后开一个数组记录下来就好了，搜索的基本运3闿怎7S号1011丄二13141£171£1辛2021inhere x *«mptYl.cpp xti'nclud&<bits/5rdc+. h>ns i ng naBejipac e std;char G100S 1005;int re31005J 1301 ;Int m, n;int dir : = 10,1,1,0,-1, 0,-1, -I,-1,1,1,-1,!,11 ；日txjoi c-hecL(int- a, int y) i. f (x<0 I I jf、I y

11、<01 | y，=m re turn false;re tura tEe;void 3ove(1nt k, int y)( tf(G!cl y- 'U resxty)=-± retnrn ;£o-r iat x"0;i<：S;i十+)(int nexXx=xdirIj 0；int nexxv=ydxri1;if (check (nextx.f nsxty) if Gn5tC3£l *e)tcy'* *|j| resK yl-H+;Z311 Start here X | *emptylxpp x if checIc (nextz

12、, nexLy)IT G ；Bextx nextyj = '|I" x y:232425"627-Q253.0313233343536373.e3540弓二理二43一 iAintgin() fsc inf t龟G", £11, ini)；loT (int i=0;i5；i4 + ) jcAtif f "%Gi): fCT ( int i=C” ； i弋n; i亠亠) foTHint 3=0;jm;3 ) serve (i, j);for (irt i='y；i<Ti；i + )(for (i nt j心；j5；j+)t t

13、xeslijFiintfre3i j);elsep工niTLt L"):I:此题重点在于格式和源码中的if语句。自己列数字理解。12459 le 11 1213141516 17 le 19 2令 21 耳23242526 27 2e#incluclc<5tdia, hInt main(void)i(it Ojij, n3jscar+C'Sd %d&n, &n2)j un;a=n2;for(;c<=aiC-H-)* printfC-5ed=-,t)i forCL*2ji<»t;if+)<lf(-t95i=a) printt(&

14、quot;-3C<l*'i)j t=t/i；else break;prirtfC'-a5dn''t)jreturn 9;J:简单的数学问题。牛 includefstTioJhA int malnfvoid)int h,(ii,s;Jong tj £canf("3eid"At)i h=t/56&0;ri=Ct-h* 3660)/66;5=t-h*3ee©-in*e0； printf("%d;Scl;%dh,ii,5); returni QjK :直接模拟就可以了，不过要注意分情况讨论。料 i me l

15、uHe < i© st rsHf 1 > ttjc bjdicolsritPW' uting nsmajpsca std;Int Min(>int v1, 7?y t, 5, 111J 17 t1, 1?； cjn>>71>>v2>>t>>5>>litl = t2 = 11 - 12 = 0juhll«(lL < 1 && 12 < i)ifCll - 12 >=t2 +- 5；11 = vl *11 = j2 * tit H<24 q n - ul

16、 *17 = v7 *iff11 = 12ccMjT<< 'n'c<endl; cout<<t2;Else kf11 > 12>ccMjt<<*R"<<snd;al£dcaut<< caut<< l/v5;L:分礼物，自己列数字发现规律，最后能够得出杨辉三角数字规律。4include<3Tdlo .?i> int rLfiin (void)int ch 30 20 r Jlf i jrrF：scsrii ("号d.E, n)；while in-)/

17、3can± ( "-id 总且"，*处” iy);for(i-0;i<x;i+)for(j=0;j<=i;j+*)if (i=J 门=切chim；elsech ； i j ； =ch.(i-i ( j-1) -ci( t-l)| j i :printf 9."电, ch x- L J (y-ij );return u:N :画图计算，找一找规律就出来了。int n, m, fcterapl,temp2,sun： 5Cflnf ( "SSdVn while(K-)scanf 1( "d %d 妝T/gnSm, &k); ifCnSk!=03elset4nipl-<n/k) i£l£eternp3=(m/k:);5 uin=te m