【UVALive 11549】

题目链接： http://acm.hust.edu.cn:8080/judge/problem/viewProblem.action?id=28547

题目大意：给你两个整数n，k，让k不停平方，每次平方完取出前n位数，让你找到最大的前n位数。

解题思路：自己列几项就可以看出一定是一个循环。当发现有重复的出现时循环就结束。

本题解法好多。

解法1，用sstream流和set函数，4494ms。

View Code

 1 #include <iostream>
 2 #include <cstdio>
 3 #include <set>
 4 #include <cstring>
 5 #include <algorithm>
 6 #include <sstream>
 7 using namespace std;
 8 
 9 int next(int n, int k)
10 {
11     stringstream ss;  /// streamstring通常用来做数据转换的，可将int，char，long long， double 和string相互转换
12     ss << (long long)k*k;  /// 向ss中插入k*k
13     string s=ss.str();    /// 拷贝流缓冲到一个string对象s中
14     if(s.length()>n)  s=s.substr(0,n);
15     stringstream ss2(s);  ///再将s转换成流ss2
16     int ans;
17     ss2 >> ans;  ///抽取ss2中的数据传递给ans，实现转换
18     return ans;
19 }
20 
21 int main()
22 {
23     int n, k, T;
24     cin >> T;
25     while(T--)
26     {
27         cin >> n >> k;
28         set<int>s;
29         int ans=k;
30         while(!s.count(k))
31         {
32             s.insert(k);
33             if(ans<k)  ans=k;
34             k=next(n,k);
35         }
36             printf("%d\n",ans);
37     }
38     return 0;
39 }

解法2，因为stream流耗费太多时间，改成数组存储，1140ms。

View Code

 1 #include <iostream>
 2 #include <cstdio>
 3 #include <set>
 4 #include <cstring>
 5 #include <algorithm>
 6 #include <sstream>
 7 using namespace std;
 8 
 9 
10 int next(int n, int k)
11 {
12     if(!k) return 0;
13     int a[30], ans=0;
14     long long  t=(long long)k*k;
15     int num=0;
16     while(t)
17     {
18         a[num++]=t%10;
19         t/=10;
20     }
21     if(num<n) n=num;;
22     for(int i=num-1; i>=num-n; i--)
23     {
24         ans=ans*10+a[i];
25     }
26     return ans;
27 }
28 
29 
30 int main()
31 {
32     int n, k, T;
33     cin >> T;
34     while(T--)
35     {
36         cin >> n >> k;
37         set<int>s;
38         int ans=k;
39         while(!s.count(k))
40         {
41             s.insert(k);
42             if(ans<k)  ans=k;
43             k=next(n,k);
44         }
45         printf("%d\n",ans);
46     }
47     return 0;
48 }

解法3，刚刚已经提到了这是一个循环，我们可以假设两个小孩在这个循环跑到里跑，孩子2跑得快，孩子1跑得慢，当孩子2追上孩子1时循环结束。这就是floyd判圈算法，500ms。

View Code

 1 #include <iostream>
 2 #include <cstdio>
 3 #include <set>
 4 #include <cstring>
 5 #include <algorithm>
 6 #include <sstream>
 7 using namespace std;
 8 
 9 
10 int next(int n, int k)
11 {
12     if(!k) return 0;
13     int a[30], ans=0;
14     long long  t=(long long)k*k;
15     int num=0;
16     while(t)
17     {
18         a[num++]=t%10;
19         t/=10;
20     }
21     if(num<n) n=num;;
22     for(int i=num-1; i>=num-n; i--)
23     {
24         ans=ans*10+a[i];
25     }
26     return ans;
27 }
28 
29 int main()
30 {
31     int n, k, T;
32     cin >> T;
33     while(T--)
34     {
35         cin >> n >> k;
36         int k1= k, k2=k, ans=k;
37         do
38         {
39                    k1=next(n,k1);
40                    k2=next(n,k2);  ans=max(ans,k2);
41                    k2=next(n,k2);  ans=max(ans,k2);
42                  }  
43                 while(k1!=k2);
44         printf("%d\n",ans);
45     }
46     return 0;
47 }