UVA 11549 Calculator Conundrum (Floyd判圈算法)

题意：有个老式计算器，每次只能记住一个数字的前n位。现在输入一个整数k，然后反复平方，一直做下去，能得到的最大数是多少。例如，n=1，k=6，那么一次显示：6,3,9,1...

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

怎么判断遇到相同的呢？如果装在数组里一一比较显然很慢，如果用v[k]判断k是否出现过，k范围太大空间不够用。

第一种方法是使用STL里的set来判重。

#include<cstdio>

#include<set>

using namespace std;

int T,n,k;

int next(int x)//寻找x的后继

{

	if(!k) return 0;

	int buf[20],i=0;

	long long t=(long long)x*x;

	while(t)

	{

		buf[i++]=t%10;

		t/=10;

	}

	int ans=0;

	for(int j=1;j<=min(n,i);++j) ans=ans*10+buf[i-j];

	return ans;

}

int main()

{

	scanf("%d",&T);

	while(T--)

	{

		scanf("%d%d",&n,&k);

		set<int> S;

		while(!S.count(k))

		{

			S.insert(k);

			k=next(k);

		}

		printf("%d\n",*(--S.end()));

	}

	return 0;

}

这个方法还是不够快的，第二种方法是用神奇的Floyd判圈算法。

如果两个小孩在直线跑道上跑同时出发，第二个小孩的速度是第一个小孩的两倍，那第二个小孩永远在前面。但如果在环形跑道上的话，第二个小孩将会“追上”第一个小孩。

#include<cstdio>

#include<set>

using namespace std;

int T,n,k;

int next(int x)

{

    if(!k) return 0;

    int buf[20],i=0;

    long long t=(long long)x*x;

    while(t)

    {

        buf[i++]=t%10;

        t/=10;

    }

    int ans=0;

    for(int j=1;j<=min(n,i);++j) ans=ans*10+buf[i-j];

    return ans;

}

int main()

{

    freopen("in.txt","r",stdin);

    scanf("%d",&T);

    while(T--)

    {

        scanf("%d%d",&n,&k);

        int ans=max(k,next(k)),k1=k,k2=next(k);//k1是第一个小孩，k2是第二个小孩

        while(k1!=k2)

        {

            k1=next(k1);

            k2=next(k2); if(k2>ans) ans=k2; //小孩跑第一次

            k2=next(k2); if(k2>ans) ans=k2; //小孩跑第二次

        }

        printf("%d\n",ans);

    }

    return 0;

}