按照lzx大牛推薦的分類，開始寫搜索題，發(fā)現(xiàn)這道1426是個很典型的BFS，寫完交上去，結(jié)果RE，原來是隊列長度開的不夠，于是加長了點，就
125ms過了，可是內(nèi)存太大，用了8000多k，不知道大牛們是怎么用0ms，40多k過得。。。貌似還有DP的寫法？好像還有什么構(gòu)造法。。。我壓根
就不知道什么是構(gòu)造法。。。期待大牛解釋。。。
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 閱讀(1073)
評論(0) 編輯 收藏 引用 所屬分類:
Problem Solving