Posted on 2009-11-07 21:18
rikisand 阅读(83)
评论(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 的数据