首页 > 代码库 > UVA11549 计算机谜题(Floyd判圈算法)
UVA11549 计算机谜题(Floyd判圈算法)
1 #include<iostream> 2 #include<cstdio> 3 #include<cstring> 4 #include<cmath> 5 #include<algorithm> 6 #include<set> 7 #include<sstream> 8 using namespace std; 9 /*int next1(int n,int k) 10 { 11 stringstream ss; 12 ss<<(long long)k*k; 13 string s=ss.str(); 14 if(s.length()>n)s=s.substr(0,n);//结果太长,只取前n位 15 int ans; 16 stringstream ss2(s); 17 ss2>>ans; 18 return ans; 19 }*/ 20 int buf[100]; 21 int next2(int n,int k) 22 { 23 if(!k) return 0; 24 long long k2=(long long)k*k; 25 int L=0; 26 while(k2>0){ 27 buf[L++]=k2%10;k2/=10; 28 } 29 if(n>L)n=L; 30 int ans=0; 31 for(int i=0;i<n;i++) 32 ans=ans*10+buf[--L];//把前min{n,L}位重新组合 33 return ans; 34 } 35 /*int main() 36 { 37 int T; 38 cin>>T; 39 while(T--) 40 { 41 int n,k; 42 cin>>n>>k; 43 set<int>s; 44 int ans=k; 45 while(!s.count(k)) 46 { 47 s.insert(k); 48 if(k>ans)ans=k; 49 k=next1(n,k); 50 } 51 cout<<ans<<endl; 52 } 53 return 0; 54 } 55 */ 56 int main() 57 { 58 int T; 59 cin>>T; 60 while(T--) 61 { 62 int n,k; 63 cin>>n>>k; 64 int ans=k; 65 int k1=k;int k2=k; 66 do{ 67 k1=next2(n,k1); 68 k2=next2(n,k2);if(k2>ans)ans=k2; 69 k2=next2(n,k2);if(k2>ans)ans=k2; 70 }while(k1!=k2); 71 cout<<ans<<endl; 72 } 73 return 0; 74 }
假设有两个小孩在一个“可以无限向前跑”的环形跑道上赛跑,同时出发,但其中一个小孩的速度是另一个小孩的速度的2倍,那么跑的快的小孩将追上跑的慢的小孩,
注释掉的代码的时间要更长next1要4秒多,next2要1秒。
UVA11549 计算机谜题(Floyd判圈算法)
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。