UVa11549:Calculator Conundrum

题目大意

有一个老旧的计算器只能显示前n个数字。现在给定一个数字k，每次给k平方，如果答案长度超过n则从最高位开始显示n个数字，丢弃其余数字。

要求：求出计算器能显示的最大数字。

Solution1(naive)

本题中得到的数列会出现循环，可以用一个set记录所有得到的数字，一旦出现重复数字停止循环，输出set中的最大值即可。

AC-Code(C++)

Time:540ms

#include <iostream>
#include <iomanip>
#include <algorithm>
#include <string>
#include <cstring>
#include <map>
#include <set>
#include <vector>
#include <cmath>
#include <climits>
#include <ctime>

using namespace std;
typedef long long ll;
const int INF = 0x3f3f3f3f;
const double PI = acos(-1.0);
const int maxn = 30000 + 10;

/*
 * 刘汝佳 训练指南 P42
 */

int n,k,mask;

int getNext(int x){
    ll temp = (ll)x * x;
    while(temp >= mask)
        temp /= 10;
    return (int)temp;
    
}

int main(int argc, const char * argv[]) {
    
//    freopen("input.txt", "r", stdin);
    
    int T;
    scanf("%d",&T);
    while(T--){
        scanf("%d %d",&n,&k);
        mask = 1;
        for(int i=0;i<n;i++)
            mask *= 10;
        
        set<int> s;
        int ans = k;
        while(s.count(k)==0){
            s.insert(k);
            k = getNext(k);
            ans = max(ans,k);
        }
        
        printf("%d
",ans);
        
    }
    
    
    return 0;
}

Solution2（floyd判圈法）

想象两个人赛跑，两人以不同的速度匀速运动。如果赛道是直线的，那么两个人以后再也不会相遇了，而如果两个人在一个环形赛道上跑步，那么速度快的那个人一定会在某一时刻从后面追上速度慢的那个人。

在这里循环的序列就是环形赛道，这种方法叫做floyd判圈法，这样做后因为不需要频繁的在set中查询元素是否存在，所以运行速度有了很大的提升，并且还将空间复杂度降为Ο(1)。

Note

在判圈的时候最开始我很顺的写出了如下代码，但这样会造成个别点没有取到就退出循环了，所以某些测试例子中的出的答案往往要比正确答案稍微小一点。

// wrong
do{
	k1 = getNext(k1);
	k2 = getNext(getNext(k2));
	ans = max(ans,max(k1,k2));
}while(k1 != k2);

AC-Code(C++)

Time:50ms

#include <iostream>
#include <iomanip>
#include <algorithm>
#include <string>
#include <cstring>
#include <map>
#include <set>
#include <vector>
#include <cmath>
#include <climits>
#include <ctime>

using namespace std;
typedef long long ll;
const int INF = 0x3f3f3f3f;
const double PI = acos(-1.0);
const int maxn = 30000 + 10;

int n,k,mask;

/*
 * 刘汝佳 训练指南 P42
 */

int getNext(int x){
    ll temp = (ll)x * x;
    while(temp >= mask)
        temp /= 10;
    return (int)temp;
    
}

int main(int argc, const char * argv[]) {
    
//    freopen("input.txt", "r", stdin);
    
    int T;
    scanf("%d",&T);
    while(T--){
        scanf("%d %d",&n,&k);
        mask = 1;
        for(int i=0;i<n;i++)
            mask *= 10;
        
        int k1 = k;
        int k2 = k;
        int ans = k;
        // wrong
//        do{
//            k1 = getNext(k1);
//            k2 = getNext(getNext(k2));
//            ans = max(ans,max(k1,k2));
//        }while(k1 != k2);
        // right
        do{
            k1 = getNext(k1);
            k2 = getNext(k2);
            ans = max(ans,k2);
            k2 = getNext(k2);
            ans = max(ans,k2);
        }while(k1 != k2);

        printf("%d
",ans);
        
    }
    

    return 0;
}