POJ 1426 Find The Multiple

举报
Linux猿 发表于 2021/08/04 23:16:32 2021/08/04
【摘要】 题目链接~~> 做题感悟:做了杭电上的两个题目,再做这个真是 so  easy !但是还要写一下的,用第二种方法很不熟练。。。 解题思路:还是用取余的思想,每次都将余数乘 10 再加 上相应的数,0 要特判一下。 代码1: #include<stdio.h>#include<iostream>#include<string...

题目链接~~>

做题感悟:做了杭电上的两个题目,再做这个真是 so  easy !但是还要写一下的,用第二种方法很不熟练。。。

解题思路:还是用取余的思想,每次都将余数乘 10 再加 上相应的数,0 要特判一下。

代码1:


      #include<stdio.h>
      #include<iostream>
      #include<string>
      #include<string.h>
      #include<queue>
      #include<algorithm>
      using namespace std ;
      int n ;
      bool vis[300] ; // 标记余数是否相同
      struct zhang
      {
      int x,num ;
      string str ; // 这个很好用
      } ;
      int bfs()
      {
      queue<zhang>q ;
       zhang curt,next ;
      memset(vis,false,sizeof(vis)) ;
       curt.x=0 ;
       curt.str="" ;
       curt.num=0 ;
       q.push(curt) ;
      while(!q.empty())
       {
       curt=q.front() ;
       q.pop() ;
      if(curt.num>100)  continue ;
      for(int i=0 ;i<2 ;i++)
       {
       next=curt ;
       next.num+=1 ;
       next.x=next.x*10+i ;
      if(!next.x) continue ;
      if(next.x%n==0)
       {
       next.str+=(48+i) ;
       next.str+='\0' ;
      cout<<next.str<<endl ;
      return true ;
       }
       next.x=next.x%n ;
      if(vis[next.x]) continue ;
       vis[next.x]=true ;
       next.str+=(48+i) ;
       q.push(next) ;
       }
       }
      return false ;
      }
      int main()
      {
      while(scanf("%d",&n)!=EOF)
       {
      if(!n)  break ;
       bfs() ;
       }
      return 0 ;
      }
  
 

代码2:


      #include<stdio.h>
      #include<string.h>
      #include<queue>
      #include<iostream>
      #define MX 5000
      using namespace std ;
      int n ;
      bool vis[300] ;
      struct zhang
      {
      int x,m,pre,num ;
      }q[MX];
      void print(int k) // 输出 不用string 存数
      {
      if(k==-1)
      return ;
       print(q[k].pre) ;
      printf("%d",q[k].x) ;
      }
      int bfs()
      {
       zhang curt,next ;
      int start=-1,head=0 ;
      memset(vis,false,sizeof(vis)) ;
       curt.x=1 ;
       curt.num=1 ;
       curt.pre=-1 ;
      if(n==1)
       {
      cout<<1<<endl ;
      return true ;
       }
       vis[1]=true ;
       curt.m=1 ;
       q[++start]=curt ;
      while(head<=start)
       {
      int h=head ;head++ ;
       curt=q[h] ;
      if(!curt.m)
       {
       print(h) ;
      printf("\n") ;
      return true ;
       }
      if(curt.num>100) continue ;
      for(int i=0 ;i<2 ;i++)
       {
       next=curt ;
       next.m=next.m*10+i ;
      if(!next.m) continue ;
       next.m=next.m%n ;
      if(vis[next.m]) continue ;
       vis[next.m]=true ;
       next.x=i ;
       next.num+=1 ;
       next.pre=h ;
       q[++start]=next ;
       }
       }
      return false ;
      }
      int main()
      {
      while(scanf("%d",&n)!=EOF)
       {
      if(!n)   break ;
       bfs() ;
       }
      return  0 ;
      }
  
 

 

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

原文链接:blog.csdn.net/nyist_zxp/article/details/17435837

【版权声明】本文为华为云社区用户转载文章,如果您发现本社区中有涉嫌抄袭的内容,欢迎发送邮件进行举报,并提供相关证据,一经查实,本社区将立刻删除涉嫌侵权内容,举报邮箱: cloudbbs@huaweicloud.com
  • 点赞
  • 收藏
  • 关注作者

评论(0

0/1000
抱歉,系统识别当前为高风险访问,暂不支持该操作

全部回复

上滑加载中

设置昵称

在此一键设置昵称,即可参与社区互动!

*长度不超过10个汉字或20个英文字符,设置后3个月内不可修改。

*长度不超过10个汉字或20个英文字符,设置后3个月内不可修改。