首页 > 代码库 > UVa 11549 Calculator Conundrum

UVa 11549 Calculator Conundrum

2024-07-15 11:24:30   214人阅读

大白书里面的题感觉就是没有什么固定的思路，只能认真理解学习汝佳大大的代码。

这里用的Floyd判圈法，就像插图里面的一样，两个小孩，一个快一个慢，如果实在一个环形跑道，那么快的那个最终一定会“追上”慢的那个。

明显这里还是有重复计算的部分，但相对其他算法来说还是比较高效的吧，我猜。。

6s的题居然只用了0.5s，Orz

 

 1 //#define LOCAL 2 #include <iostream> 3 #include <cstdio> 4 #include <cstring> 5 using namespace std; 6  7 int buf[100]; 8  9 int next(int n, int k)10 {11     if(k == 0)12         return 0;13     long long k2 = (long long)k * k;14     int L = 0;15     while(k2 > 0)16     {17         buf[L++] = k2 % 10;18         k2 /= 10;19     }20     if(L < n)21         n = L;22     int ans = 0;23     for(int i = 0; i < n; ++i)24         ans = ans * 10 + buf[--L];25     return ans;26 }27 28 int main(void)29 {30     #ifdef LOCAL31         freopen("11549in.txt", "r", stdin);32     #endif33 34     int T;35     scanf("%d", &T);36     while(T--)37     {38         int n, k;39         scanf("%d%d", &n, &k);40         int ans = k;41         int k1, k2;42         k1 = k2 = k;43         do44         {45             k1 = next(n, k1);46             k2 = next(n, k2);47             if(k2 > ans)48                 ans = k2;49             k2 = next(n, k2);50             if(k2 > ans)51                 ans = k2;52         }while(k2 != k1);53         printf("%d\n", ans);54     }55     return 0;56 }
代码君

 


联系
我们