搜索小练#5

Posted on Edited on In

题目

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
#include <cstdio>
#include <iostream>
#define ull unsigned long long int 
using namespace std;

int n, k;

inline void dfs (ull ans, int n, int weishu) {
    if (k == 0) return;
    if (weishu == 20) return;
    if (ans%n == 0) {
        cout << ans << '\n';
        k = 0;
        return;
    }
    dfs (ans*10, n, weishu+1);
    dfs (ans*10+1, n, weishu+1);
}

int main () {
    while (scanf ("%d", &n)&& n != 0) {
        k = 1;
        dfs (1, n, 1);
    }
    return 0;
}

this is a easy topic

but I can not make it unless I can read the answer

To tell the truth, I was very terrible

Although the topic is easy but I don't know how to solve it

I will also try my best to welcome the NOIP2020.

PS:

1.we need the 'weishu == 20'

because the ull can held '19' so we much let the ull can search all

两年后再写

尝试用bfs写了一下，mle了

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
/*
 * By Youngore
 * Time: 22.10.15
 * */
#include <cstdio>
#include <queue>
#include <iostream>
#include <cstring>
#define ull unsigned long long
using namespace std;

int n;

inline int youngore()
{
	while (scanf ("%d", &n))
	{
		if (n == 0) return 0;
		queue<pair<ull, int> >q; q.push(make_pair(1, 1));
		while (q.size())
		{
			pair<ull, int> nows = q.front(); q.pop();
			if (nows.second == 20) continue;
			if (! (nows.first % n)) 
			{
				cout << nows.first << '\n';
				break;
			}
			q.push(make_pair(nows.first * 10, nows.second + 1));
			q.push(make_pair(nows.first * 10 + 1, nows.second + 1));
		}
	}
	return 0;
}

int search_ex = youngore();

signed main() {;}
/*
2
6
19
0
*/