首页 > 代码库 > hdu1664 Different Digits
hdu1664 Different Digits
求出n的倍数m，要求m使用的不同数字最少，且最小。
一开始不知道怎么搜，因为不知道m由多少个不同的数字组成。
然后百度了一下，看到和数论有关。
m可能使用的数字的个数可能为一个或者两个
a,aa,aaa....n+1个a， 将这些数%n，那么肯定有两个余数相等，抽屉原理。那么这两个数相减，得到的数肯定是n的倍数，且这两个数由a和0组成。
所以就知道怎么搜了，先搜m由一个数组成的情况，如果不存在，那么就搜两个数组成的情况，要注意全部搜完，因为题目要求m最小。
1 #include <stdio.h> 2 #include <string.h> 3 #include <queue> 4 #include <iostream> 5 #include <string> 6 using namespace std; 7 struct node 8 { 9 int res; 10 string str; 11 }; 12 bool vis[66666];; 13 int digit; 14 int cnt; 15 string ans; 16 bool find_; 17 18 void bfs1(int n) 19 { 20 int res; 21 int k; 22 for(int i=1; i<=9; ++i) 23 { 24 k = 1; 25 res = i % n; 26 memset(vis,0,sizeof(vis)); 27 while(!vis[res] && res!=0) 28 { 29 vis[res] = true; 30 res = (res * 10 + i) % n; 31 k++; 32 } 33 if(res==0) 34 { 35 if(cnt==0) 36 { 37 cnt = k; 38 digit = i; 39 } 40 else if(cnt>k) 41 { 42 cnt = k; 43 digit = i; 44 } 45 } 46 } 47 } 48 void bfs2(int i, int j,int n) 49 { 50 memset(vis,0,sizeof(vis)); 51 queue<node> q; 52 node cur,tmp; 53 if(i!=0) 54 { 55 cur.res = i % n; 56 cur.str = (char)(i+‘0‘); 57 q.push(cur); 58 } 59 cur.res = j % n; 60 cur.str = (char)(j+‘0‘); 61 q.push(cur); 62 while(!q.empty()) 63 { 64 cur = q.front(); q.pop(); 65 if(cur.res ==0) 66 { 67 if(!find_) 68 { 69 ans = cur.str; 70 find_ = true; 71 } 72 else if(cur.str.size() < ans.size()) 73 ans = cur.str; 74 else if(cur.str.size()==ans.size() && cur.str < ans) 75 ans = cur.str; 76 return; 77 78 } 79 if(find_ && cur.str.size() >= ans.size()) 80 continue; 81 tmp.res = (cur.res * 10 + i) % n; 82 if(!vis[tmp.res]) 83 { 84 vis[tmp.res] = true; 85 tmp.str = cur.str + (char)(i+‘0‘); 86 87 q.push(tmp); 88 } 89 tmp.res = (cur.res * 10 + j) % n; 90 if(!vis[tmp.res]) 91 { 92 vis[tmp.res] = true; 93 tmp.str = cur.str + (char)(j+‘0‘); 94 q.push(tmp); 95 } 96 } 97 } 98 99 int main()100 {101 int n,i,j;102 while(scanf("%d",&n),n)103 { 104 find_ = false;105 cnt = 0;106 bfs1(n);107 if(cnt!=0)108 for(i=0; i<cnt; ++i)109 printf("%d",digit);110 else111 {112 for(i=0; i<=9; ++i)113 for(j=i+1; j<=9; ++j)114 {115 bfs2(i,j,n);116 }117 cout<<ans;118 }119 puts("");120 }121 }
hdu1664 Different Digits
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。