UVa 11549 计算器谜题（Floyd判圈算法）

题意：

有一个老式计算器，只能显示n位数字，输入一个整数k，然后反复平方，如果溢出的话，计算器会显示结果的最高n位。如果一直这样做下去，能得到的最大数是多少？

思路：

这个肯定是会循环的。

比较普通的做法就是用set来判断是否出现过来终止循环。

另一个高效算法：Floyd判圈算法！！

想象一下，假设有两个小孩子在一个“可以无限向前跑”的跑道上赛跑，同时出发，但其中一个孩子的速度是另一个两倍。如果跑到是直的，跑得快的小孩永远在前面，但如果跑道有环，则跑得快的小孩将“追上”跑得慢的小孩。

 #include<iostream>

 #include<algorithm>

 #include<cstring>

 #include<cstdio>

 #include<vector>

 #include<stack>

 #include<queue>

 #include<cmath>

 #include<map>

 using namespace std;

 int n,k;

 int next(int n,int k)

 {

     int buf[];

     if(!k)  return ;

     int cnt=;

     long long k2=(long long)k*k;

     while(k2)   {buf[cnt++]=k2%;k2/=;}

     if(n>cnt)   n=cnt;

     int ans=;

     for(int i=;i<n;i++)

         ans=ans*+buf[--cnt];

     return ans;

 }

 int main()

 {

     //freopen("D:\\input.txt","r",stdin);

     int T;

     scanf("%d",&T);

     while(T--)

     {

         scanf("%d%d",&n,&k);

         int ans=k;

         int k1=k,k2=k;

         do

         {

             k1=next(n,k1);  ans=max(ans,k1);

             k2=next(n,k2);  ans=max(ans,k2);   //小孩2，第一步

             k2=next(n,k2);  ans=max(ans,k2);   //小孩2，第二步

         }while(k1!=k2);  //追上以后才停止

         printf("%d\n",ans);

     }

     return ;

 }

巴特西

UVa 11549 计算器谜题（Floyd判圈算法）

最新文章

热门文章