按照lzx大牛推荐的分类，开始写搜索题，发现这道1426是个很典型的BFS，写完交上去，结果RE，原来是队列长度开的不够，于是加长了点，就
125ms过了，可是内存太大，用了8000多k，不知道大牛们是怎么用0ms，40多k过得。。。貌似还有DP的写法？好像还有什么构造法。。。我压根
就不知道什么是构造法。。。期待大牛解释。。。
Simbaforrest
2008.1.9
1 #include<iostream>
2 #include<cstring>
3 #include<cmath>
4 using namespace std;
5 int n;
6 const int maxn = 1100000;
7 __int64 q[maxn];
8
9 void BFS()
10 {
11 //init
12 int front,rear;
13 front=rear=0;
14 q[rear]=1;
15 rear++;
16 //sovle
17 __int64 top;
18 while(rear>front)
19 {
20 top = q[front];
21 if(top%n==0)
22 break;
23 top *= 10;
24 q[rear++]=top;
25 q[rear++]=top+1;
26 front++;
27 }
28 //output
29 cout<<top<<endl;
30 }
31
32 int main()
33 {
34 while(cin>>n&&n!=0)
35 {
36 BFS();
37 }
38 return 0;
39 }
40
posted on 2008-01-09 14:32
R2 阅读(422)
评论(0) 编辑 收藏 引用 所属分类:
Problem Solving