欢迎来到天天文库
浏览记录
ID：36107948
大小：403.50 KB
页数：139页
时间：2019-05-06
《acm算法经典例题》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。
1、--一、数论1:WolfandRabbit描述Thereisahillwithnholesaround.Theholesaresignedfrom0ton-1.Arabbitmusthideinoneoftheholes.Awolfsearchestherabbitinanticlockwiseorder.Thefirstholehegetintoistheonesignedwith0.Thenhewillgetintotheholeeverymholes.Forexample,m=2andn=6,thewolf
2、willgetintotheholeswhicharesigned0,2,4,0.Iftherabbithidesintheholewhichsigned1,3or5,shewillsurvive.Sowecalltheseholesthesafeholes.输入TheinputstartswithapositiveintegerPwhichindicatesthenumberoftestcases.ThenonthefollowingPlines,eachlineconsists2positiveinteger
3、mandn(04、据2个数m----n(05、解题关键：这题就转化成了判断两个数是否有公约数。代码：#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;i6、n>>m>>n; if(greatestCommonDivisor(m,n)==1)//公约数为1说明互斥，没有安全洞穴 cout<<"NO"; else cout<<"YES"; } return0;}2:a^b描述给定a和b，输出a^b的最后一个数字。输入输入数据有多组，每组数据占一行，每行为a和b的值（07、还会超出Int范围题目说只要最后一个数字，回想一下小学时学的乘法过程，貌似乘数最后一位和前面的无关我们大胆的尝试一下用a的个位代替a，然后我们发现循环b次还是会超时，这是我们要想办法减少循环的次数，试一下是不是有周期规律这时我们来列举一下2的n次方的个位：24862486----我们发现周期为4，我们在试试1-9的n次方，发现周期都是4，所以，我们可以用b%4代替b，需要注意的是，当b%4==0时，我们需要给他加上4，不然就不循环了。代码：#includeintmain(){inta,b,i,t8、;while(scanf("%d%d",&a,&b)!=EOF){b=b%4;if(b==0)b=4;a=a%10;t=1;for(i=0;i
4、据2个数m----n(05、解题关键：这题就转化成了判断两个数是否有公约数。代码：#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;i6、n>>m>>n; if(greatestCommonDivisor(m,n)==1)//公约数为1说明互斥，没有安全洞穴 cout<<"NO"; else cout<<"YES"; } return0;}2:a^b描述给定a和b，输出a^b的最后一个数字。输入输入数据有多组，每组数据占一行，每行为a和b的值（07、还会超出Int范围题目说只要最后一个数字，回想一下小学时学的乘法过程，貌似乘数最后一位和前面的无关我们大胆的尝试一下用a的个位代替a，然后我们发现循环b次还是会超时，这是我们要想办法减少循环的次数，试一下是不是有周期规律这时我们来列举一下2的n次方的个位：24862486----我们发现周期为4，我们在试试1-9的n次方，发现周期都是4，所以，我们可以用b%4代替b，需要注意的是，当b%4==0时，我们需要给他加上4，不然就不循环了。代码：#includeintmain(){inta,b,i,t8、;while(scanf("%d%d",&a,&b)!=EOF){b=b%4;if(b==0)b=4;a=a%10;t=1;for(i=0;i
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;i6、n>>m>>n; if(greatestCommonDivisor(m,n)==1)//公约数为1说明互斥，没有安全洞穴 cout<<"NO"; else cout<<"YES"; } return0;}2:a^b描述给定a和b，输出a^b的最后一个数字。输入输入数据有多组，每组数据占一行，每行为a和b的值（07、还会超出Int范围题目说只要最后一个数字，回想一下小学时学的乘法过程，貌似乘数最后一位和前面的无关我们大胆的尝试一下用a的个位代替a，然后我们发现循环b次还是会超时，这是我们要想办法减少循环的次数，试一下是不是有周期规律这时我们来列举一下2的n次方的个位：24862486----我们发现周期为4，我们在试试1-9的n次方，发现周期都是4，所以，我们可以用b%4代替b，需要注意的是，当b%4==0时，我们需要给他加上4，不然就不循环了。代码：#includeintmain(){inta,b,i,t8、;while(scanf("%d%d",&a,&b)!=EOF){b=b%4;if(b==0)b=4;a=a%10;t=1;for(i=0;i
6、n>>m>>n; if(greatestCommonDivisor(m,n)==1)//公约数为1说明互斥，没有安全洞穴 cout<<"NO"; else cout<<"YES"; } return0;}2:a^b描述给定a和b，输出a^b的最后一个数字。输入输入数据有多组，每组数据占一行，每行为a和b的值（07、还会超出Int范围题目说只要最后一个数字，回想一下小学时学的乘法过程，貌似乘数最后一位和前面的无关我们大胆的尝试一下用a的个位代替a，然后我们发现循环b次还是会超时，这是我们要想办法减少循环的次数，试一下是不是有周期规律这时我们来列举一下2的n次方的个位：24862486----我们发现周期为4，我们在试试1-9的n次方，发现周期都是4，所以，我们可以用b%4代替b，需要注意的是，当b%4==0时，我们需要给他加上4，不然就不循环了。代码：#includeintmain(){inta,b,i,t8、;while(scanf("%d%d",&a,&b)!=EOF){b=b%4;if(b==0)b=4;a=a%10;t=1;for(i=0;i
7、还会超出Int范围题目说只要最后一个数字，回想一下小学时学的乘法过程，貌似乘数最后一位和前面的无关我们大胆的尝试一下用a的个位代替a，然后我们发现循环b次还是会超时，这是我们要想办法减少循环的次数，试一下是不是有周期规律这时我们来列举一下2的n次方的个位：24862486----我们发现周期为4，我们在试试1-9的n次方，发现周期都是4，所以，我们可以用b%4代替b，需要注意的是，当b%4==0时，我们需要给他加上4，不然就不循环了。代码：#includeintmain(){inta,b,i,t
8、;while(scanf("%d%d",&a,&b)!=EOF){b=b%4;if(b==0)b=4;a=a%10;t=1;for(i=0;i
此文档下载收益归作者所有
