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