UVa11549 Calculator Conundrum

　　k太大，hash数组开不下，用了map判圈。

View Code 1000+ms

 1 #include <stdio.h>
 2 #include <string.h>
 3 #include <map>
 4 using namespace std;
 5 
 6 typedef long long LL;
 7 
 8 LL cal(int n, LL &v, LL &ans)
 9 {
10     v = v * v;
11     int L = 0;
12     LL tmp = v;
13     while(tmp)
14     {
15         L ++;
16         tmp /= 10;
17     }
18     LL t = 1;
19     if(n < L)
20     {
21         for(int i = 0; i < L - n; i ++)
22             t *= 10;
23     }
24     v /= t;
25     if(v > ans) 
26         ans = v;
27     return v;
28 }
29 int main()
30 {
31     int t, n, k;
32     map<LL, int> mp;
33     LL ans, v;
34     scanf("%d", &t);
35     while(t --)
36     {
37         mp.clear();
38         scanf("%d%d", &n, &k);
39         v = ans = (LL)k;
40         while(mp[v] == 0)
41         {
42             mp[v] ++;
43             cal(n, v, ans);
44         }
45         printf("%lld\n", ans);
46     }
47     return 0;
48 }

　　后来知道了“Floyd判圈算法”这么个东西。这个算法也比较形象的表达为“龟兔算法”，可以解决单链表成环问题。这个算法简要描述是这样的：

　　乌龟每秒跑的距离是原来的一倍，兔子每秒跑的距离是原来的两倍，那么，如果在某个时刻，兔子追上乌龟并到达同一点，那么说明出现了圈（环）。可以结合下图看看：

　　从上图可以看出，乌龟也是要跑的，这样才能确保乌龟也进入圈中。而由于兔子每秒跑是原来两倍的距离，减去乌龟的距离就得到圈周长（进而也可以求周期了）。

View Code 500+ms

 1 #include <stdio.h>
 2 #include <string.h>
 3 #include <map>
 4 using namespace std;
 5 
 6 typedef long long LL;
 7 
 8 int buf[10];
 9 int next(int n, int k)
10 {
11     if(!k) return 0;
12     LL k2 = (LL)k * k;
13     int L = 0;
14     while(k2 > 0)
15     {
16         buf[L++] = k2 % 10;
17         k2 /= 10;
18     }
19     if(n > L)
20         n = L;
21     int ans = 0;
22     for(int i = 0; i < n; i ++)    
23         ans = ans * 10 + buf[--L];
24     return ans;
25 }
26 
27 int main()
28 {
29     int t, n, k;
30     scanf("%d", &t);
31     while(t --)
32     {
33         scanf("%d%d", &n, &k);
34         int ans = k;
35         int k1 = k, k2 = k;
36         do
37         {
38             k1 = next(n, k1);
39             k2 = next(n, k2); if(k2 > ans) ans = k2;
40             k2 = next(n, k2); if(k2 > ans) ans = k2;
41         }while(k1 != k2);
42         printf("%d\n", ans);
43     }
44     return 0;
45 }