uva11549Calculator Conundrum

题意：有一个老式计算器，只能保存最多n位数，如果结果超出n位，则保留前n位。现在输入一个n和一个k，k表示一个数字，然后不停的求k的平方并令k=k*k，发现会出现循环的结果，求所有结果种最大的一个。

分析：暴力模拟可以过的，但有更好的算法。暴力：用哈希、set都可以。高效算法：Floyd判圈算法，假设两个小孩在有环形的跑道上跑，一个速度为v，另一个速度为2*v，出发点相同，那么总会有相遇的时候，相遇的时候就是跑完一圈了，那么最大值一定跑过了~

代码：

View Code

 1 #include <stdio.h>
 2 #include <iostream>
 3 #define DEBUG
 4 using namespace std;
 5 int buf[10];
 6 int next(int n, int k){
 7     if(k==0) return 0;
 8     long long k2 = (long long)k*k;
 9     int len = 0;
10     while(k2>0){
11         buf[len++]=k2%10;
12         k2/=10;
13     }
14     if(n>len) n=len;            //k很小、n很大的情况
15     int ans=0;
16     for(int i=0; i<n; i++){
17         ans = ans*10 + buf[--len];
18     }
19     return ans;
20 }
21 int main(){
22 #ifndef DEBUG
23     freopen("in.txt", "r", stdin);
24 #endif
25     int cas;
26     scanf("%d", &cas);
27     while(cas--){
28         int n, k;
29         scanf("%d%d", &n, &k);
30         int k1=k, k2=k, ans=k;
31         while(true){
32             k1 = next(n, k1);
33             k2 = next(n, k2);
34             if(ans<k2) ans=k2;
35             k2 = next(n, k2);
36             if(ans<k2) ans=k2;
37
38             if(k1==k2) break;
39         }
40         printf("%d\n", ans);
41     }
42     return 0;
43 }

记录一下~只用了0.5s~