HDU 1664 Different Digits

题目链接~~>

做题感悟：

               这道题是在学长讲完取余的方法后才做的，开始用的以前用的方法，结果超内存，然后用了 C++ 的 string 类后又超时，真无语！经过这一题，明显发现自己掌握的知识太少了。

题意：

         给你一个 n ，让你找它的倍数，要有最少的不同的数字，如果不同的数字一样，输出数小的那个。

解题思路：

              首先要用到超级密码那题的取余思想，其次还有一点，任何一个数都可以用两种不同的数字表示倍数（数论中的定理）。用 string 类时广搜到结果时要回溯的方法（具体看代码，提交用C++）。

代码：

  

   

    

     

    
    

     

      #include<stdio.h>
     
    
   

    

     

    
    

     

      #include<string.h>
     
    
   

    

     

    
    

     

      #include<iostream>
     
    
   

    

     

    
    

     

      #include<string>
     
    
   

    

     

    
    

     

      #include<queue>
     
    
   

    

     

    
    

     

      using namespace std ;
     
    
   

    

     

    
    

     

      #define MX 65536
     
    
   

    

     

    
    

     

      int n,num,mx ;
     
    
   

    

     

    
    

     

      int g[5] ;
     
    
   

    

     

    
    

     

      bool vis[MX],flag ;
     
    
   

    

     

    
    

     

      struct zhang
     
    
   

    

     

    
    

     

      {
     
    
   

    

     

    
    

     
 int x,m,cnt,pre ;// pre 记录父亲节点
     
    
   

    

     

    
    

     

      }q[MX] ;
     
    
   

    

     

    
    

     

      string str,key ;
     
    
   

    

     

    
    

     

      void gettemp(int k) // 回溯复制到 str ，如果不用会超时 
     
    
   

    

     

    
    

     

      {
     
    
   

    

     

    
    

     
 if(k==-1)
     
    
   

    

     

    
    

     
 return  ;
     
    
   

    

     

    
    

     

       gettemp(q[k].pre) ; // 找父亲
     
    
   

    

     

    
    

     

       str+=(q[k].x+'0') ;
     
    
   

    

     

    
    

     
 return ;
     
    
   

    

     

    
    

     

      }
     
    
   

    

     

    
    

     

      int bfs()
     
    
   

    

     

    
    

     

      {
     
    
   

    

     

    
    

     
 int head=0,tail=-1 ;
     
    
   

    

     

    
    

     
 memset(vis,false,sizeof(vis)) ;
     
    
   

    

     

    
    

     
 for(int i=0 ;i<num ;i++)
     
    
   

    

     

    
    

     

       {
     
    
   

    

     

    
    

     
 if(!g[i]) continue ;
     
    
   

    

     

    
    

     

       zhang current ;
     
    
   

    

     

    
    

     

       current.pre=-1 ;
     
    
   

    

     

    
    

     

       current.x=g[i] ; // 存放的数
     
    
   

    

     

    
    

     

       current.m=g[i]%n ;  // 存余数
     
    
   

    

     

    
    

     

       current.cnt=1 ; // 记录个数
     
    
   

    

     

    
    

     

       vis[current.m]=true ;
     
    
   

    

     

    
    

     

       q[++tail]=current ;
     
    
   

    

     

    
    

     

       }
     
    
   

    

     

    
    

     
 while(head<=tail)
     
    
   

    

     

    
    

     

       {
     
    
   

    

     

    
    

     
 int h=head ;head++ ;
     
    
   

    

     

    
    

     
 if(q[h].cnt>mx)  // 当大于最少个数时不进行下去
     
    
   

    

     

    
    

     
 continue ;
     
    
   

    

     

    
    

     
 if(!q[h].m) // 找到满足的解
     
    
   

    

     

    
    

     

       {
     
    
   

    

     

    
    

     

       str="" ;
     
    
   

    

     

    
    

     

       gettemp(h) ;
     
    
   

    

     

    
    

     
 if(q[h].cnt<mx)
     
    
   

    

     

    
    

     

       {
     
    
   

    

     

    
    

     

       key=str ;
     
    
   

    

     

    
    

     

       mx=q[h].cnt ;
     
    
   

    

     

    
    

     

       }
     
    
   

    

     

    
    

     
 else if(q[h].cnt==mx)
     
    
   

    

     

    
    

     

       {
     
    
   

    

     

    
    

     
 if(str<key)
     
    
   

    

     

    
    

     

       key=str ;
     
    
   

    

     

    
    

     

       }
     
    
   

    

     

    
    

     
 return true ;
     
    
   

    

     

    
    

     

       }
     
    
   

    

     

    
    

     
 for(int i=0 ;i<num ;i++)
     
    
   

    

     

    
    

     

       {
     
    
   

    

     

    
    

     
 int mod=(q[h].m*10+g[i])%n ;
     
    
   

    

     

    
    

     
 if(vis[mod])   continue ;
     
    
   

    

     

    
    

     

       vis[mod]=true ;
     
    
   

    

     

    
    

     

       zhang tep ;
     
    
   

    

     

    
    

     

       tep.m=mod ;   tep.cnt=q[h].cnt+1 ;
     
    
   

    

     

    
    

     

       tep.x=g[i] ;  tep.pre=h ; // 记录前一个值，为了不超时
     
    
   

    

     

    
    

     

       q[++tail]=tep ;
     
    
   

    

     

    
    

     

       }
     
    
   

    

     

    
    

     

       }
     
    
   

    

     

    
    

     
 return false ;
     
    
   

    

     

    
    

     

      }
     
    
   

    

     

    
    

     

      int main()
     
    
   

    

     

    
    

     

      {
     
    
   

    

     

    
    

     
 int i,j ;
     
    
   

    

     

    
    

     
 while(scanf("%d",&n)!=EOF)
     
    
   

    

     

    
    

     

       {
     
    
   

    

     

    
    

     
 if(!n)   break ;
     
    
   

    

     

    
    

     

       num=1 ;mx=9999999 ;flag=false ;
     
    
   

    

     

    
    

     

       key="" ;
     
    
   

    

     

    
    

     
 for(i=1 ;i<=9 ;i++)
     
    
   

    

     

    
    

     

       {
     
    
   

    

     

    
    

     

       g[0]=i ;
     
    
   

    

     

    
    

     
 if(bfs())
     
    
   

    

     

    
    

     

       flag=true ;
     
    
   

    

     

    
    

     

       }
     
    
   

    

     

    
    

     
 if(flag)
     
    
   

    

     

    
    

     

       {
     
    
   

    

     

    
    

     
 cout<<key<<endl ;
     
    
   

    

     

    
    

     
 continue ;
     
    
   

    

     

    
    

     

       }
     
    
   

    

     

    
    

     

       num=2 ;
     
    
   

    

     

    
    

     
 for(i=0 ;i<=9 ;i++)
     
    
   

    

     

    
    

     

       {
     
    
   

    

     

    
    

     

       g[0]=i ;
     
    
   

    

     

    
    

     
 for(j=i+1 ;j<=9 ;j++)
     
    
   

    

     

    
    

     

       {
     
    
   

    

     

    
    

     

       g[1]=j ;
     
    
   

    

     

    
    

     

       bfs() ;
     
    
   

    

     

    
    

     

       }
     
    
   

    

     

    
    

     

       }
     
    
   

    

     

    
    

     
 cout<<key<<endl ;
     
    
   

    

     

    
    

     

       }
     
    
   

    

     

    
    

     
 return 0 ;
     
    
   

    

     

    
    

     

      }
     
    
  
 

文章来源: blog.csdn.net，作者：Linux猿，版权归原作者所有，如需转载，请联系作者。

原文链接：blog.csdn.net/nyist_zxp/article/details/16951963