USACO2.1 Hamming Codes(hamming)

從0開始遞增遍歷所有自然數，直到取得n個滿足要求的數為止。使用C++標准程序庫bitset類型保存自然數a的二進制值，如果該二進制滿足題目要求，則將a與其二進制對象保存進map<int，bitset<8> >中，然後繼續遞增a值遍歷檢驗。感覺算法復雜度挺高，但是所有測試例都是0秒通過，稍稍驚喜。
 
 
01 /*
02 ID:jzzlee1
03 PROG:hamming
04 LANG:C++
05 */
06 #include<iostream>
07 #include<fstream>
08 #include<cmath>
09 #include<string>
10 #include<bitset>
11 #include<cstring>
12 #include<map>
13 using namespace std;
14 ifstream fin("hamming.in");
15 ofstream fout("hamming.out");
16 map<int,bitset<8> > map1;
17 map<int,bitset<8> >::iterator iter;
18 int n,b,d;
19 bool check(bitset<8> bt)      //檢驗該二進制對象是否滿足與之前所有二進制對象漢明碼距離至少為d
20 {
21     int k=0;
22     for(iter=map1.begin();iter!=map1.end();++iter)
23     {
24         k=0;
25         for(int index=0;index!=8;++index)
26         {
27             if((iter->second)[index]!=bt[index])
28                 ++k;
29         }
30         if(k<d)
31             return 0;
32     }
33     return 1;
34 }
35 int main()
36 {
37     //cin>>n>>b>>d;www.2cto.com
38     fin>>n>>b>>d;
39     int a;
40      
41     int count=0;
42     for(a=0,count=0;count!=n;++a)
43     {
44         bitset<8> bt(a);
45         if(check(bt))
46         {
47             map1.insert(make_pair(a,bt));
48             ++count;
49         }
50     }
51     int i;
52     for(i=1,iter=map1.begin();iter!=map1.end();++i,++iter)      //輸出
53     {
54         //注意輸出格式，容易格式錯
55         //cout<<iter->first;
56         fout<<iter->first;
57         if(i%10==0)
58             fout<<endl;
59             //cout<<endl;
60         else if(i!=n)
61             fout<<" ";
62             //cout<<" ";
63         if(i==n&&i%10!=0)
64             fout<<endl;
65             //cout<<endl;
66     }
67     return 0;
68 }