hdu 4294 Multiple 搜索

假设a，aa，aaa……一直下去，对n取模，一定会出现循环，也就是会有aaaa…aaa和aaa…aa对n取模相同，那么把他们相减得到aaaa…0000，则只出现了2个数字得到了n的倍数。这种方法虽然不是最优，但保证了不同的数不会超过2种，所以可以直接搜索。

枚举所有组合（首先枚举只出现1种数字，再枚举出现2种的），然后搜索就够了，判重时用余数判重。

注意得到答案后要进行字典序比较。

此题不用把字符串保存在队列中，直接维护父亲节点的路径和信息，然后最后一次递归取出。

#include
  
   
#include
   
     #include
    
      #include
     
       #include
      
        #include
       
         #include
        
          #include
         
           using namespace std; #define INF 0x3f3f3f3f #define M 10001 int fa[M],pa[M],vis[M]; char s[M]; int top; int anstop; char ans[M]; char tmp[M]; int n,m; void print(int k) { if(k==0) return; print(fa[k]); s[top++]=pa[k]; } void cmp() { if(anstop
          
           top) { for(int i=0;i
           
            s[i]) { for(int j=i;j
            
              Q; bool bfs(int k1,int k2) { top=0; if(k1+k2==0) return false; while(!Q.empty()) Q.pop(); memset(vis,0,sizeof(vis)); fa[0]=-1; Q.push(0); while(!Q.empty()) { int t=Q.front();Q.pop(); if(t||k1){ int f=(t*m+k1)%n; if(!vis[f]) { vis[f]=1; fa[f]=t; pa[f]=k1+'0'; if(f==0) { print(fa[f]); s[top++]=pa[f]; if(anstop==0) {anstop=top;for(int i=0;i