Posted on 2009-11-07 21:18
rikisand 閱讀(104)
評論(0) 編輯 收藏 引用 所屬分類:
工作記錄~~everyday
恩 ，做完了就要寫下來 省的之后忘了
昨天看的misof的教程 關于數~ 今天做了其中的提到的例題：
BorelSe:
simple的題~第一次沒搞對，搞完后發現還是寫麻煩了。題目中明確說明，也顯而易見的是空集和全集一定是B集里的 ，我還費心去處理空集。。。
其次，重復的數字不用處理，因為用的是或操作。
剩下的就是用一個數組和一個set不斷循環了，其實用隊列效果很好的，恩···
試試看~tc.BorelSe
1 int howMany(int size, vector <string> sub)
2 {
3 set<int> q;q.clear();string str;
4 int mask=(1<<size)-1;
5 VI C;
6 REPV(sub,i){
7 if(sub[i]=="")C.push_back(0),q.insert(0);
8 else{
9 set<int> vec;
10 stringstream ss(sub[i]);str="";
11 while(ss>>str) {
12 if(str=="")vec.insert(0);
13 else vec.insert(atoi(str.c_str())-1);
14 }
15
16 int now=0;
17 for(set<int>::iterator it=vec.begin();it!=vec.end();it++){
18 now|=(1<<(*it));
19 }
20 if(q.count(now)==0) C.push_back(now),q.insert(now);
21 }
22 }
23 int last=q.size();
24 while(true){
25 REPV(C,i)
26 {
27 int s=C[i]^mask;if(q.count(s)==0)C.push_back(s),q.insert(s);
28 REP(j,i)
29 {
30 int k= C[i]|C[j];
31 if(q.count(k)==0)C.push_back(k),q.insert(k);
32 }
33 }
34 if(last==q.size())return last;
35 else last=q.size();
36 }
37 }關于數字：
2的n次方 換算成 10的次方 大概是 n/3 數量級的 也就是說 取 n/3+1 大小就可以了
這個是double 的數據