首页 > 代码库 > Bitset小结 （POJ2443 & HDU4920）
Bitset小结 （POJ2443 & HDU4920）
学了下bitset用法，从网上找的一些bitset用法，并从中调出一些常用的用法。
构造函数
bitset<n> b;
b有n位，每位都为0.参数n可以为一个表达式.
如bitset<5> b0;则"b0"为"00000";
bitset<n> b(unsigned long u);
b有n位,并用u赋值;如果u超过n位,则顶端被截除
如:bitset<5>b0(5);则"b0"为"00101";
bitset<n> b(string s);
b是string对象s中含有的位串的副本
string bitval ( "10011" );
bitset<5> b0 ( bitval4 );
则"b0"为"10011";
bitset<n> b(s, pos, num);
b是s中从位置pos开始的num个位的副本,如果num<n,则前面的空位自动填充0;
string bitval ("11110011011");
bitset<6> b0 ( bitval5, 3, 6 );
则"b0" 为 "100110";
os << b
把b中的位集输出到os流
os >>b
输入到b中,如"cin>>b",如果输入的不是0或1的字符,只取该字符前面的二进制位.
bool any( )
是否存在置为1的二进制位？和none()相反
bool none( )
是否不存在置为1的二进制位,即全部为0？和any()相反.
size_t count( )
二进制位为1的个数.
size_t size( )
二进制位的个数flip()
把所有二进制位逐位取反
flip(size_t pos)
把在pos处的二进制位取反
bool operator[]( size_type Pos )
获取在pos处的二进制位
set()
把所有二进制位都置为1
set(pos)
把在pos处的二进制位置为1
reset()
把所有二进制位都置为0
reset(pos)
把在pos处的二进制位置为0
注意：bitset只能与bitset运算，不能与数运算
#include <cstdio>#include <cstring>#include <iostream>#include <algorithm>#include <cmath>#include <vector>#include <utility>#include <stack>#include <queue>#include <map>#include <deque>#include <bitset>#define max(x,y) ((x)>(y)?(x):(y))#define min(x,y) ((x)<(y)?(x):(y))#define INF 0x3f3f3f3fusing namespace std;bitset<1005> bit[10005];int N,M,T,a,b;int main(){ scanf("%d",&N); for(int i=0; i<N; i++) { scanf("%d",&M); for(int j=0; j<M; j++) { scanf("%d",&a); bit[a].set(i); } } scanf("%d",&T); for(int i=0; i<T; i++) { scanf("%d%d",&a,&b); if((bit[a]&bit[b]).any()) printf("Yes\n"); else printf("No\n"); } return 0;}
HDU4920：
思路：矩阵化为0,1,2为值的矩阵，bitset存储0,1,2在矩阵上位置。
则可通过count快速算出1*1,1*2,2*1,2*2的个数，容易得到答案。
注：此题其余优化思路是将B矩阵转置，据说是加快数组访问速度，即转置后每次访问+1而非+n，其神奇的效果不言而喻。当然仅限于这种常数级优化！
#include <cstdio>#include <cstring>#include <iostream>#include <algorithm>#include <cmath>#include <vector>#include <utility>#include <stack>#include <queue>#include <map>#include <deque>#include <bitset>#define max(x,y) ((x)>(y)?(x):(y))#define min(x,y) ((x)<(y)?(x):(y))#define INF 0x3f3f3f3fusing namespace std;bitset<805> A[805][3],B[805][3];int N,k,C;int main(){ while(scanf("%d",&N)!=EOF && N) { for(int i=0; i<N; i++) for(int j=0; j<3; j++) { A[i][j].reset(); B[i][j].reset(); } for(int i=0; i<N; i++) for(int j=0; j<N; j++) { scanf("%d",&k); A[i][k%3].set(j); } for(int i=0; i<N; i++) for(int j=0; j<N; j++) { scanf("%d",&k); B[j][k%3].set(i); } for(int i=0; i<N; i++) for(int j=0; j<N; j++) { C=(A[i][1]&B[j][1]).count()+ (A[i][1]&B[j][2]).count()*2+(A[i][2]&B[j][1]).count()*2+ (A[i][2]&B[j][2]).count()*4; if(j==N-1) printf("%d",C%3); else printf("%d\n",C%3); } } return 0;}
总结：
bitset确实是位运算一大神器，能够在各种状态压缩中起到神奇的作用，但速度方面并不十分突出，上两题测试的时间相对偏长，不过一旦用上了，想必你离成功不远了。哈哈！！