acm算法经典例题.doc

《acm算法经典例题.doc》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、一、数论1:WolfandRabbit描述Thereisahillwithnholesaround.Theholesaresignedfrom0ton-1.Arabbitmusthideinoneoftheholes.Awolfsearchestherabbitinanticlockwiseorder.Thefirstholehegetintoistheonesignedwith0.Thenhewillgetintotheholeeverymholes.Forexample,m=2andn=6,thewolfwillg

2、etintotheholeswhicharesigned0,2,4,0.Iftherabbithidesintheholewhichsigned1,3or5,shewillsurvive.Sowecalltheseholesthesafeholes.输入TheinputstartswithapositiveintegerPwhichindicatesthenumberoftestcases.ThenonthefollowingPlines,eachlineconsists2positiveintegermandn(0<

3、m,n<2147483648).输出Foreachinputmn,ifsafeholesexist,youshouldoutput"YES",elseoutput"NO"inasingleline.样例输入21222样例输出NOYES翻译：描述一座山有n个洞，洞被标记为从0到n-1。兔子必须藏在一个洞中。狼会逆时针方向搜索兔子。狼一开始在洞0，然后他会每m个洞进去一次。例如：m=2，n=6，狼就会依次进入洞0240。如果兔子藏在135就安全。输入第一行一个数字p，表示下面有p组测试数据，每组测试数据2个数mn(0

4、n<2147483648)输出每组数据输出一行，如果存在安全洞穴，输出"YES"，否则输出"NO"思路/方法：你是不是觉得总是无法通过，看看下面的解析假设有n=6个洞012345当m=4时，狼进的洞是0420，也就是形成了一个循环，永远也到不了其他洞穴当m=5时，狼进的洞是0543210，这时所有的洞都遍历了一遍。思考：当m=4和m=5时，到底有什么区别？当n和m有公约数(非1)时，就会形成一个数字个数小于n的循环当n和m无公约数时，就会形成一个数字个数为n的循环，此时没有安全洞穴。解题关键：这题就转化成了判断两个数是

5、否有公约数。代码：#includeusingnamespacestd;longlonggreatestCommonDivisor(longlonga,longlongb)//最大公约数{  longlongt;  while(b)  {    t=a%b;    a=b;    b=t;  }  returna;}intmain(){  inti,p;  longlongm,n;  cin>>p;  for(i=0;i>m>>n;    if(greatestCo

6、mmonDivisor(m,n)==1)//公约数为1说明互斥，没有安全洞穴      cout<<"NO";    else      cout<<"YES";  }  return0;}2:a^b描述给定a和b，输出a^b的最后一个数字。输入输入数据有多组，每组数据占一行，每行为a和b的值（0

7、学的乘法过程，貌似乘数最后一位和前面的无关我们大胆的尝试一下用a的个位代替a，然后我们发现循环b次还是会超时，这是我们要想办法减少循环的次数，试一下是不是有周期规律这时我们来列举一下2的n次方的个位：24862486我们发现周期为4，我们在试试1-9的n次方，发现周期都是4，所以，我们可以用b%4代替b，需要注意的是，当b%4==0时，我们需要给他加上4，不然就不循环了。代码：#includeintmain(){inta,b,i,t;while(scanf("%d%d",&a,&b)!=EOF){b=

8、b%4;if(b==0)b=4;a=a%10;t=1;for(i=0;i