UVa 11549 Calculator Conundrum / floyd判圈算法

题意是输入n k

然后只能显示k的前n位 然后k等于前n位的平方如此反复 求最大出现的数字

可以用map 或者set

新学了一个floyd判圈算法

就是比如2个赛跑 第二个比第一个速度快1倍 圆形跑道可以追上第一个人

这里就另k1做一次next  k2做2次next 如果k1 == k2 就break

 说明出现循环了

代码是书上的

 

#include <cstdio>
#include <iostream>
#include <set>
#include <algorithm>
using namespace std;
int buf[100];
int next(int n, int k)
{
	if(!k)
		return 0;
	long long kk = (long long)k * k;
	int l = 0;
	while(kk)
	{
		buf[l++] = kk % 10;
		kk /= 10;
	}
	int ans = 0;
	for(int i = 0; i < n; i++)
	{
		ans *= 10;
		ans += buf[--l];
	}
	return ans;
}

int main()
{
	int T;
	int n, k;
	scanf("%d", &T);
	while(T--)
	{
		scanf("%d %d", &n, &k);
		int ans = k;
		int k1 = k, k2 = k;
		do
		{
			k1 = next(n, k1);
			ans = max(ans, 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;
}


UVa 11549 Calculator Conundrum / floyd判圈算法

上一篇:带你读《机器学习即服务 将Python机器学习创意快速转变为 云端Web应用程序》之二:在Azure上进行共享单车 回归模型智能预测


下一篇:单链表的归并1