UVA 11549 Calculator Conundrum——flody判圈算法

UVA 11549 Calculator Conundrum——flody判圈算法

非常有意思的一个题目，暴力枚举的思路很好想，但是时间空间复杂度都很高，这时候就可以同时开启两条线路，增长率分别为1和2，当线路1和线路2再次相等时敲好走过了一个周期，在走这个周期的过程中维护最大值ans就可以了

#include #include #include #include using namespace std;const int maxn = 100;int T, N, K, a[maxn];int Next(int n, int k) { if (!k) return 0; long long kk = (long long)k * k; int cnt = 0; while (kk) { a[cnt++] = kk % 10; kk /= 10; } n = min(n, cnt); int ans = 0; for (int i = 0; i < n; i++) ans = ans * 10 + a[--cnt]; return ans;}int main() { scanf("%d", &T); while (T--) { scanf("%d %d", &N, &K); int ans = K, k1 = K, k2 = K; do { k1 = Next(N, k1); k2 = Next(N, k2); ans = max(ans, k2); k2 = Next(N, k2); ans = max(ans, k2); } while (k1 != k2); printf("%d\n", ans); } return 0;}

版权声明：本文内容由网络用户投稿，版权归原作者所有，本站不拥有其著作权，亦不承担相应法律责任。如果您发现本站中有涉嫌抄袭或描述失实的内容，请联系我们jiasou666@gmail.com 处理，核实后本网站将在24小时内删除侵权内容。