uva 11549
题意：你拥有一个老式计算机，它只能显示n为数字，有一天你输入数字k，接着一直平方下去，在这个过程中如果数字长度大于n，那么截取前n个数形成一个新的数k，再用这个新的数k一直平方下去，那么这个过程中能显示的最大数字是多少。
思路：在这个过程如果出现了以前出现过的数，那么从第一个开始到这个数就是一个循环节，后面的也与这个节一模一样，因为都是针对一个数字执行同一种操作。
为了时间复杂度上的考虑，可以使用set判重，耗时2.279s
#include <iostream> #include <cstdio> #include <sstream> #include <set> using namespace std; int next(int n,int k) { stringstream ss; ss<< (long long)k*k; string c; c=ss.str(); string cc=c.substr(0,n); stringstream s(cc); int ans; s>>ans; return ans; } int main() { int T; scanf("%d",&T); while(T--) { set<int> dic; int n,k; scanf("%d%d",&n,&k); int ans=k; while(!dic.count(k)) { dic.insert(k); ans=max(ans,k); k=next(n,k); } printf("%d ",ans); } return 0; }
以上程序的主要时间耗费在使用了sstream与循环体本身，空间耗费在set上，可以改成使用数组和floy判圈算法，时间耗费0.193s
#include <iostream> #include <cstdio> #include <sstream> #include <set> using namespace std; int a[100]; int next(int n,int k) { long long k2=(long long) k*k; int l=0; while(k2) { a[l++]=k2%10; k2/=10; } if(l<n) n=l; l--; int ans=0; int c=1; for(int i=0;i<n;i++) { ans=ans*10+a[l--]; } return ans; } int main() { int T; scanf("%d",&T); while(T--) { int n,k; scanf("%d%d",&n,&k); int ans=k; int 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 ",ans); } return 0; }