uva 11549

题面见lrj蓝书。

这题学习了三个东西。

1.stringstream

http://www.cnblogs.com/yohanlong/p/7700281.html

2.STL太慢。

3.Floyd判圈算法。

大意是让两个跑步速度不同的小孩往前跑，如果路径有环，那么跑得快的一定会追上跑得慢的。

如此便可使跑得快的刚好跑快一步。

#include <cstdio>
#include <set>
#include <sstream>
#include <cstring>
#include <string>

using namespace std;

int n, k;

int buf[100];
int next(int n, int k)
{
    long long k2 = (long long) k * k;
    int L = 0;
    while (k2 > 0)
    {
        buf[L++] = k2 % 10; k2 /= 10;        
    } 
    n = min(n, L);
    int ans = 0;
    for (int i = 0; i < n; i++)
        ans = ans * 10 + buf[--L];
    return ans;
}

void solve()
{
    scanf("%d%d", &n, &k);
    int ans = k;
    int k1 = k, k2 = k;
    do
    {
        k1 = next(n, k1);//慢一点的小孩
        k2 = next(n, k2); if (k2 > ans) ans = k2;//快一点的小孩，跑两步。
        k2 = next(n, k2); if (k2 > ans) ans = k2;
    } while (k1 != k2);
    printf("%d
", ans);
}

int main()
{
    int t;
    scanf("%d", &t);
    while (t--) solve();
    return 0;
} 

速度比较：

Floyd判圈：160ms

手动模拟stringstream： 580ms

裸stringstream：1690ms

可见如果实在不会写，上STL也是能骗很多分的。

所以STL要多掌握一些奇技淫巧。