首页 > 代码库 > 51nod1109(bfs)

51nod1109(bfs)

题目链接:http://www.51nod.com/onlineJudge/questionCode.html#!problemId=1109

 

题意:中文题诶~

 

思路:可以用二叉树构建,根节点为 1,左儿子为 0,右儿子为 1.然后直接bfs一遍就好了;

注意:直接用十进制记录可能会tle或mle.可以用二进制形式记录,再存储到十进制数里,输出时再还原成二进制形式就好了;

 

代码:

技术分享
 1 #include <iostream>
 2 #include <queue>
 3 #define ll long long
 4 using namespace std;
 5 
 6 int n;
 7 ll ans;
 8 string res;
 9 
10 void bfs(void){
11     queue<pair<int,int> > q;
12     q.push({1, 1});
13     ll cnt, cnt1, cnt2;
14     while(!q.empty()){
15         cnt = q.front().first;
16         int x = q.front().second;
17         q.pop();
18         cnt1 = cnt * 2;
19         cnt2 = cnt * 2 + 1;
20         if((x * 10) % n == 0){
21             ans = cnt1;
22             break;
23         }
24         if((x * 10 + 1) % n == 0){
25             ans = cnt2;
26             break;
27         }
28         q.push({cnt1, (x * 10) % n});
29         q.push({cnt2, (x * 10 + 1) % n });
30     }
31     while(ans){
32         res += (ans % 2 + 0);
33         ans /= 2;
34     }
35     for(int i = res.size()-1; i >= 0; i--){
36         cout << res[i];
37     }
38     cout << endl;
39 }
40 
41 int main(void){
42         cin >> n;
43         bfs();
44 }
View Code

 

51nod1109(bfs)