做题感悟:
这道题是在学长讲完取余的方法后才做的,开始用的以前用的方法,结果超内存,然后用了 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 ; }