设为首页 加入收藏

TOP

uva 11549计算器谜题（floyd判圈算法）
2015-11-21 01:01:34 来源: 作者: 【大 中 小】 浏览:1次
Tags：uva 11549 计算器 floyd 算法
?? 题意：有个老式计算器，每次只能记住一个数字的前n位。现在输入一个整数k，然后反复平方，一直做下去，能得到的最大数是多少。例如，n=1，k=6，那么一次显示：6,3,9,1...

思路：这个题一定会出现循环，所以一个个模拟，遇到相同的就再之前所有数中找最大的输出即可。

?

最容易想到的就是set判重，一开始k直接生算每次除十......超时

然后看了书，用string，ac，很方便但是时间达到了4s，果然string和stringstream好慢啊.........

又改成了记录k*k的每一位，时间为1s

最后用了floyd判圈算法，0.5s，空间复杂度为o（1）........果然神奇

?

先上set代码：

#include
  
     
#include
   
     #include
    
      #include
     
       #include
      
        #include
       
         #include
        
          #include
          #include
          
            #include
           
             #include
            
              #include
              #include
              
                #include
               
                 using namespace std; #define LL long long //const int maxn = ; const int INF = 1000000000; //freopen("input.txt", "r", stdin); int buf[100]; LL next(LL n, LL k) { stringstream ss; ss << k * k; string s = ss.str(); if(s.length() > n) s = s.substr(0, n); LL ans; stringstream ss2(s); ss2 >> ans; return ans; } int main() { int t; scanf("%d", &t); while(t--) { set
                
                  a; LL n, k; scanf("%lld%lld", &n, &k); LL ans = 0; while(!a.count(k)) { a.insert(k); ans = max(ans, k); k = next(n, k); } printf("%lld\n", ans); } return 0; }

?

?

然后是floyd判圈代码

?

#include
  
     
#include
   
     #include
    
      #include
     
       #include
      
        #include
       
         #include
        
          #include
          #include
          
            #include
           
             #include
            
              #include
              #include
              
                #include
               
                 using namespace std; #define LL long long //const int maxn = ; const int INF = 1000000000; //freopen("input.txt", "r", stdin); int buf[100]; LL next(LL n, LL k) { if(!k) return 0; LL k2 = (LL)k * k; int L = 0; while(k2 > 0) {buf[L++] = k2 % 10; k2 /= 10;} if(n > L) n = L; int ans = 0; for(int i = 1; i < n; i++) ans = ans * 10 +buf[--L]; return ans; } int main() { int t; scanf("%d", &t); while(t--) { int n, k; cin >> n >> k; int ans = k; int k1 = k, k2 = k; do { k1 = next(n, k1); k2 = next(n, k2); if(k2 > ans) ans = k2; k2 = next(n, k2); if(k2 > ans) ans = k2; } while(k1 != k2); cout << ans << endl; } return 0; }

?
【大 中 小】【打印】 【繁体】【投稿】【收藏】 【推荐】【举报】【评论】 【关闭】 【返回顶部】
分享到: 
上一篇：HDU 3125 slash 下一篇：HDU 3123 GCC

评论

帐　　号: 密码: (新用户注册)
验 证 码:
表　　情:
内　　容: