POJ 1426 Find The Multiple (BFS)

题目链接:
POJ 1426 Find The Multiple (BFS)

题意分析:
给出一个数字n,查找一个只由0和1构成的数字,使得这个数字能够整除n。输出一个这样的数字。


解题思路:
首先第一个数肯定是1,然后不断得枚举添加0或者1,用BFS进行搜索即可。这里要注意两点:
1.长度很大的数字取余数可以使用从左到右解析的方式,所以每一次我们保留下解析后的余数即可,然后使用余数作为标记。
2.这就要求我们需要另开一个数组来存答案,所以BFS里面存的是结构体。

个人感受:
不知道POJ上面那些肯定long long能存的下的人结论是哪里来的。想到了余数计算就行,却没想到怎么标记,加油~

具体代码如下:
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
#include<algorithm>
#include<cctype>
#include<cmath>
#include<cstdio>
#include<cstring>
#include<iomanip>
#include<iostream>
#include<map>
#include<queue>
#include<set>
#include<sstream>
#include<stack>
#include<string>
#define lowbit(x) (x & (-x))
#define ll long long
#define pr(x) cout << #x << " = " << (x) << '\n';
using namespace std;
struct P {
char ans[111];
int cnt;
int mod;
};
bool vis[311];
int main()
{
int n;
while (~scanf("%d", &n) && n) {
queue<P> q;
memset(vis, 0, sizeof vis);
P st;
st.cnt = 1;
st.ans[0] = '1';
st.mod = 1 % n;
q.push(st);
while (q.size()) {
P cur = q.front(); q.pop();
if (cur.mod == 0) {
for (int i = 0; i < cur.cnt; ++i) printf("%c", cur.ans[i]);
putchar('\n');
break;
}
vis[cur.mod] = 1;
cur.cnt = cur.cnt + 1;
cur.ans[cur.cnt - 1] = '0';
cur.mod = (cur.mod * 10) % n;
if (!vis[cur.mod])
q.push(cur);
cur.ans[cur.cnt - 1] = '1';
cur.mod = (cur.mod + 1) % n;
if (!vis[cur.mod])
q.push(cur);
}
}
return 0;
}

广告时间

Java学习网站: how2j

VPS: VPS