NYOJ 929 密码宝盒 || HDU 1226 超级密码

题目链接~~>

做题感悟：

              开始听了学长讲课后在杭电上做过这个题，之后又在比赛时遇见，当时有点不淡定 RE 了三次，开始以为数组开小了后来才发现没有考虑到 n = 0 ；的情况，以后即使遇到原题也应该认真读题。

题意：

         给你一个 n ，m个C进制的数。让你组合成最小的数字是 n 的倍数。

解题思路：

               这需要数学知识，r = k ( mod n ) 则 ( k * p + a ) ( mod c ) = ( r * p + a ) ( mod  n ) ；余数出现过如果再次出现就不用再次使用。

代码（本人）：

  

   

    

     

    
    

     

      #include<stdio.h>
     
    
   

    

     

    
    

     

      #include<string.h>
     
    
   

    

     

    
    

     

      #include<algorithm>
     
    
   

    

     

    
    

     

      #include<queue>
     
    
   

    

     

    
    

     

      using namespace std ;
     
    
   

    

     

    
    

     

      int n,m,c ;
     
    
   

    

     

    
    

     

      int g[20] ;
     
    
   

    

     

    
    

     

      bool vis[10000] ;
     
    
   

    

     

    
    

     

      struct zhang
     
    
   

    

     

    
    

     

      {
     
    
   

    

     

    
    

     
 int x,y[505],num,bu ;
     
    
   

    

     

    
    

     

      } ;
     
    
   

    

     

    
    

     

      bool bfs()
     
    
   

    

     

    
    

     

      {
     
    
   

    

     

    
    

     
 int i,j ;
     
    
   

    

     

    
    

     
 queue<zhang>q ;
     
    
   

    

     

    
    

     

       zhang cur,next ;
     
    
   

    

     

    
    

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

    

     

    
    

     

       cur.x=0 ;
     
    
   

    

     

    
    

     

       cur.num=0 ;
     
    
   

    

     

    
    

     

       cur.bu=0 ;
     
    
   

    

     

    
    

     

       q.push(cur) ;
     
    
   

    

     

    
    

     
 while(!q.empty())
     
    
   

    

     

    
    

     

       {
     
    
   

    

     

    
    

     

       cur=q.front() ;
     
    
   

    

     

    
    

     

       q.pop() ;
     
    
   

    

     

    
    

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

    

     

    
    

     

       {
     
    
   

    

     

    
    

     

       next.x=cur.x*c+g[i] ;
     
    
   

    

     

    
    

     
 if(!next.x) continue ; // 前缀不能是 0 
     
    
   

    

     

    
    

     

       next.bu=cur.bu+1 ;
     
    
   

    

     

    
    

     

       next.num=cur.num+1 ;
     
    
   

    

     

    
    

     

       next.x=next.x%m ;
     
    
   

    

     

    
    

     
 if(vis[next.x]||next.num>500) continue ; // 如果余数出现过或长度大于 500 不继续下去
     
    
   

    

     

    
    

     

       vis[next.x]=1 ;
     
    
   

    

     

    
    

     
 for(j=0 ;j<cur.num ;j++)
     
    
   

    

     

    
    

     

       next.y[j]=cur.y[j] ;
     
    
   

    

     

    
    

     

       next.y[cur.num]=g[i] ;
     
    
   

    

     

    
    

     
 if(!next.x) // 找到解输出
     
    
   

    

     

    
    

     

       {
     
    
   

    

     

    
    

     
 for(j=0 ;j<next.num ;j++)
     
    
   

    

     

    
    

     
 if(next.y[j]>9)
     
    
   

    

     

    
    

     
 printf("%c",next.y[j]+55) ;
     
    
   

    

     

    
    

     
 else printf("%d",next.y[j]) ;
     
    
   

    

     

    
    

     
 printf("\n") ;
     
    
   

    

     

    
    

     
 return true ;
     
    
   

    

     

    
    

     

       }
     
    
   

    

     

    
    

     

       q.push(next) ;
     
    
   

    

     

    
    

     

       }
     
    
   

    

     

    
    

     

       }
     
    
   

    

     

    
    

     
 return false ;
     
    
   

    

     

    
    

     

      }
     
    
   

    

     

    
    

     

      int main()
     
    
   

    

     

    
    

     

      {
     
    
   

    

     

    
    

     
 int T,i ;
     
    
   

    

     

    
    

     
 char ch ;
     
    
   

    

     

    
    

     
 scanf("%d",&T) ;
     
    
   

    

     

    
    

     
 while(T--)
     
    
   

    

     

    
    

     

       {
     
    
   

    

     

    
    

     
 scanf("%d%d%d",&m,&c,&n) ;
     
    
   

    

     

    
    

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

    

     

    
    

     

       {
     
    
   

    

     

    
    

     

       getchar() ;
     
    
   

    

     

    
    

     
 scanf("%c",&ch) ;
     
    
   

    

     

    
    

     
 if(ch>='A'&&ch<='F')
     
    
   

    

     

    
    

     

       g[i]=ch-55 ;
     
    
   

    

     

    
    

     
 else g[i]=ch-'0' ;
     
    
   

    

     

    
    

     

       }
     
    
   

    

     

    
    

     

       sort(g,g+n) ; // 排序让第一个找到的是最小的
     
    
   

    

     

    
    

     
 if(!m) // 0 需要特判一下
     
    
   

    

     

    
    

     

       {
     
    
   

    

     

    
    

     
 if(!g[0])
     
    
   

    

     

    
    

     
 printf("0\n") ;
     
    
   

    

     

    
    

     
 else
     
    
   

    

     

    
    

     
 printf("give me the bomb please\n") ;
     
    
   

    

     

    
    

     
 continue ;
     
    
   

    

     

    
    

     

       }
     
    
   

    

     

    
    

     
 if(!bfs())
     
    
   

    

     

    
    

     
 printf("give me the bomb please\n") ;
     
    
   

    

     

    
    

     

       }
     
    
   

    

     

    
    

     
 return 0 ;
     
    
   

    

     

    
    

     

      }
     
    
  
 

代码：

  

   

    

     

    
    

     
 
     
    
   

    

     

    
    

     

      #include<stdio.h>
     
    
   

    

     

    
    

     

      #include<string.h>
     
    
   

    

     

    
    

     

      #include<queue>
     
    
   

    

     

    
    

     

      #include<algorithm>
     
    
   

    

     

    
    

     

      #include<iostream>
     
    
   

    

     

    
    

     

      #define MX 50005
     
    
   

    

     

    
    

     

      using namespace std ;
     
    
   

    

     

    
    

     

      int n,c,m ;
     
    
   

    

     

    
    

     

      int g[18] ;
     
    
   

    

     

    
    

     

      bool vis[MX] ;
     
    
   

    

     

    
    

     

      struct zhang
     
    
   

    

     

    
    

     

      {
     
    
   

    

     

    
    

     
 int x,m,pre,cnt ;
     
    
   

    

     

    
    

     

      }q[MX] ;
     
    
   

    

     

    
    

     

      void gettep(int k)
     
    
   

    

     

    
    

     

      {
     
    
   

    

     

    
    

     
 if(k==-1)
     
    
   

    

     

    
    

     
 return ;
     
    
   

    

     

    
    

     

       gettep(q[k].pre) ;
     
    
   

    

     

    
    

     
 if(q[k].x>=10)
     
    
   

    

     

    
    

     
 printf("%c",q[k].x+55) ;
     
    
   

    

     

    
    

     
 else printf("%c",q[k].x+'0') ;
     
    
   

    

     

    
    

     
 return ;
     
    
   

    

     

    
    

     

      }
     
    
   

    

     

    
    

     

      int bfs()
     
    
   

    

     

    
    

     

      {
     
    
   

    

     

    
    

     
 int head=0,tail=-1 ;
     
    
   

    

     

    
    

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

    

     

    
    

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

    

     

    
    

     

       {
     
    
   

    

     

    
    

     
 if(!g[i]) continue ;
     
    
   

    

     

    
    

     

       zhang next ;
     
    
   

    

     

    
    

     

       next.pre=-1 ;
     
    
   

    

     

    
    

     

       next.x=g[i] ;
     
    
   

    

     

    
    

     

       next.m=g[i]%n ;
     
    
   

    

     

    
    

     

       vis[next.m]=true ;
     
    
   

    

     

    
    

     

       next.cnt=1 ;
     
    
   

    

     

    
    

     

       q[++tail]=next ;
     
    
   

    

     

    
    

     

       }
     
    
   

    

     

    
    

     
 while(head<=tail)
     
    
   

    

     

    
    

     

       {
     
    
   

    

     

    
    

     
 int h=head ;head++ ;
     
    
   

    

     

    
    

     
 if(q[h].cnt>500) continue  ;
     
    
   

    

     

    
    

     
 if(!q[h].m)
     
    
   

    

     

    
    

     

       {
     
    
   

    

     

    
    

     

       gettep(h) ;
     
    
   

    

     

    
    

     
 return true  ;
     
    
   

    

     

    
    

     

       }
     
    
   

    

     

    
    

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

    

     

    
    

     

       {
     
    
   

    

     

    
    

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

    

     

    
    

     
 if(vis[key]) continue ;
     
    
   

    

     

    
    

     

       vis[key]=true ;
     
    
   

    

     

    
    

     

       zhang tep ;
     
    
   

    

     

    
    

     

       tep.m=key ;   tep.x=g[i] ;
     
    
   

    

     

    
    

     

       tep.pre=h ;   tep.cnt=q[h].cnt+1 ;
     
    
   

    

     

    
    

     

       q[++tail]=tep ;
     
    
   

    

     

    
    

     

       }
     
    
   

    

     

    
    

     

       }
     
    
   

    

     

    
    

     
 return false ;
     
    
   

    

     

    
    

     

      }
     
    
   

    

     

    
    

     

      int main()
     
    
   

    

     

    
    

     

      {
     
    
   

    

     

    
    

     
 int T,i ;
     
    
   

    

     

    
    

     
 char ch ;
     
    
   

    

     

    
    

     
 scanf("%d",&T) ;
     
    
   

    

     

    
    

     
 while(T--)
     
    
   

    

     

    
    

     

       {
     
    
   

    

     

    
    

     
 scanf("%d%d%d",&n,&c,&m) ;
     
    
   

    

     

    
    

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

    

     

    
    

     

       {
     
    
   

    

     

    
    

     
 cin>>ch ;
     
    
   

    

     

    
    

     
 if(ch>='A'&&ch<='F')
     
    
   

    

     

    
    

     

       g[i]=ch-55 ;
     
    
   

    

     

    
    

     
 else   g[i]=ch-'0' ;
     
    
   

    

     

    
    

     

       }
     
    
   

    

     

    
    

     

       sort(g,g+m) ;
     
    
   

    

     

    
    

     
 if(!n)
     
    
   

    

     

    
    

     

       {
     
    
   

    

     

    
    

     
 if(!g[0]) printf("0") ;
     
    
   

    

     

    
    

     
 else printf("So Sorry.") ;
     
    
   

    

     

    
    

     
 puts("") ;
     
    
   

    

     

    
    

     
 continue ;
     
    
   

    

     

    
    

     

       }
     
    
   

    

     

    
    

     
 if(!bfs())
     
    
   

    

     

    
    

     
 printf("So Sorry.") ;
     
    
   

    

     

    
    

     
 puts("") ;
     
    
   

    

     

    
    

     

       }
     
    
   

    

     

    
    

     
 return 0 ;
     
    
   

    

     

    
    

     

      }
     
    
  
 

优代码：

  

   

    

     

    
    

     

      #include <queue>
     
    
   

    

     

    
    

     

      #include <string>
     
    
   

    

     

    
    

     

      #include <stdio.h>
     
    
   

    

     

    
    

     

      #include <string.h>
     
    
   

    

     

    
    

     

      #include <algorithm>
     
    
   

    

     

    
    

     

      using namespace std;
     
    
   

    

     

    
    

     

      const int N = 5005;
     
    
   

    

     

    
    

     

      bool vis[N];
     
    
   

    

     

    
    

     

      string ans;
     
    
   

    

     

    
    

     

      int a[17],pre[N],ansAt[N],n,m,c;
     
    
   

    

     

    
    

     

      int ctoi(char c)
     
    
   

    

     

    
    

     

      {
     
    
   

    

     

    
    

     
 return c >= '0' && c <= '9' ? c - '0' : c - 'A' + 10;
     
    
   

    

     

    
    

     

      }
     
    
   

    

     

    
    

     

      char itoc(int i)
     
    
   

    

     

    
    

     

      {
     
    
   

    

     

    
    

     
 return i <= 9 ? i + '0' : i + 'A' - 10;
     
    
   

    

     

    
    

     

      }
     
    
   

    

     

    
    

     

      bool bfs()
     
    
   

    

     

    
    

     

      {
     
    
   

    

     

    
    

     
 queue<int> q;
     
    
   

    

     

    
    

     

       q.push(0);
     
    
   

    

     

    
    

     
 while(!q.empty())
     
    
   

    

     

    
    

     

       {
     
    
   

    

     

    
    

     
 int cur = q.front();q.pop();
     
    
   

    

     

    
    

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

    

     

    
    

     

       {
     
    
   

    

     

    
    

     
 int nxt = (cur * c + a[i]) % n;
     
    
   

    

     

    
    

     
 if(cur == 0 && a[i] == 0 || vis[nxt])
     
    
   

    

     

    
    

     
 continue;
     
    
   

    

     

    
    

     

       vis[nxt] = true;
     
    
   

    

     

    
    

     

       ansAt[nxt] = a[i];
     
    
   

    

     

    
    

     

       pre[nxt] = cur;
     
    
   

    

     

    
    

     
 if(nxt == 0)
     
    
   

    

     

    
    

     
 return true;
     
    
   

    

     

    
    

     

       q.push(nxt);
     
    
   

    

     

    
    

     

       }
     
    
   

    

     

    
    

     

       }
     
    
   

    

     

    
    

     
 return false;
     
    
   

    

     

    
    

     

      }
     
    
   

    

     

    
    

     
 
     
    
   

    

     

    
    

     

      bool check()
     
    
   

    

     

    
    

     

      {
     
    
   

    

     

    
    

     

       ans = "";
     
    
   

    

     

    
    

     
 int p = 0;
     
    
   

    

     

    
    

     
 do
     
    
   

    

     

    
    

     

       {
     
    
   

    

     

    
    

     

       ans += itoc(ansAt[p]);
     
    
   

    

     

    
    

     

       p = pre[p];
     
    
   

    

     

    
    

     

       }while(p);
     
    
   

    

     

    
    

     
 return (int)ans.size() <= 500;
     
    
   

    

     

    
    

     

      }
     
    
   

    

     

    
    

     
 
     
    
   

    

     

    
    

     

      int main()
     
    
   

    

     

    
    

     

      {
     
    
   

    

     

    
    

     
 int T;
     
    
   

    

     

    
    

     
 scanf("%d",&T);
     
    
   

    

     

    
    

     
 while(T--)
     
    
   

    

     

    
    

     

       {
     
    
   

    

     

    
    

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

    

     

    
    

     
 scanf("%d%d%d",&n,&c,&m);
     
    
   

    

     

    
    

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

    

     

    
    

     

       {
     
    
   

    

     

    
    

     
 char num[3];
     
    
   

    

     

    
    

     
 scanf("%s",num);
     
    
   

    

     

    
    

     

       a[i] = ctoi(num[0]);
     
    
   

    

     

    
    

     

       }
     
    
   

    

     

    
    

     

       sort(a,a+m);
     
    
   

    

     

    
    

     
 if(n == 0)
     
    
   

    

     

    
    

     

       {
     
    
   

    

     

    
    

     
 puts(a[0] == 0 ? "0" : "So Sorry.");
     
    
   

    

     

    
    

     
 continue;
     
    
   

    

     

    
    

     

       }
     
    
   

    

     

    
    

     
 if(bfs() && check())
     
    
   

    

     

    
    

     

       {
     
    
   

    

     

    
    

     
 for(int i=(int)ans.size()-1;i>=0;i--)
     
    
   

    

     

    
    

     
 putchar(ans[i]);
     
    
   

    

     

    
    

     
 puts("");
     
    
   

    

     

    
    

     

       }
     
    
   

    

     

    
    

     
 else
     
    
   

    

     

    
    

     
 puts("So Sorry.");
     
    
   

    

     

    
    

     

       }
     
    
   

    

     

    
    

     
	return 0;
     
    
   

    

     

    
    

     

      }
     
    
   

    

     

    
    

     
 
     
    
   

    

     

    
    

     

       
     
    
  
 

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

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