[UVa 11549]Calculator Conundrum-白红宇

[UVa 11549]Calculator Conundrum

阅读量：4940 次

发布时间：2019-06-11

本文共 1160 字，大约阅读时间需要 3 分钟。

题解

显然按题意模拟会出现环，因为可能出现的数字数有限的，所以不可能无限的衍生下去。

那么我们就可以按题意模拟，遍历整个过程，统计最大值即可。

判环的环我们想到$hash$，也可以用$STL$中的$set$，但是复杂度高...

$Floyd$判圈。一步两步法，有环的话肯定会相遇，空间复杂度可以降到$O(1)$，时间也快不少。

1 //It is made by Awson on 2017.9.18 2 #include  3 #include 
      
        4 #include 
       
         5 #include 
        
          6 #include 
         
           7 #include 
          
            8 #include 
           
             9 #include 
            
             10 #include 
             
              11 #include 
              
               12 #include 
               
                13 #include 
                
                 14 #include 
                 
                  15 #define LL long long16 #define Max(a, b) ((a) > (b) ? (a) : (b))17 #define Min(a, b) ((a) < (b) ? (a) : (b))18 #define Abs(a) ((a) < 0 ? (-(a)) : (a))19 using namespace std;20 21 int n;22 LL lim, k;23 24 LL getnext(LL x) {25 x *= x;26 while (x/lim) x /= 10;27 return x;28 }29 30 int main() {31 int t;32 scanf("%d", &t);33 while (t--) {34 scanf("%d%lld", &n, &k);35 lim = 1;36 LL ans = k;37 for (int i = 1; i <= n; i++)38 lim *= 10;39 LL k1 = k, k2 = k;40 do {41 k1 = getnext(k1); ans = Max(ans, k1);42 k2 = getnext(k2); ans = Max(ans, k2);43 k2 = getnext(k2); ans = Max(ans, k2);44 }while (k2 != k1);45 printf("%lld\n", ans);46 }47 return 0;48 }