uva 11549

 

题意：你拥有一个老式计算机，它只能显示n为数字，有一天你输入数字k，接着一直平方下去，在这个过程中如果数字长度大于n，那么截取前n个数形成一个新的数k，再用这个新的数k一直平方下去，那么这个过程中能显示的最大数字是多少。

思路：在这个过程如果出现了以前出现过的数，那么从第一个开始到这个数就是一个循环节，后面的也与这个节一模一样，因为都是针对一个数字执行同一种操作。

为了时间复杂度上的考虑，可以使用set判重，耗时2.279s

#include 
      
       #include 
       
        #include 
        
         #include 
         
          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
          
            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\n",ans);    }    return 0;}
          
         
        
       
      

以上程序的主要时间耗费在使用了sstream与循环体本身，空间耗费在set上，可以改成使用数组和floy判圈算法，时间耗费0.193s

#include 
      
       #include 
       
        #include 
        
         #include 
         
          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