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运算，不能与数运算

另外找到两题相关的bitset题目，确实bitset用上之后能使代码量大大减少。

POJ2443：

思路：数最大10000，给每个数开个bitset<1000>存其是否属于相应位上的集合

　　之后ans即两个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 0x3f3f3f3f

using 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
");
        else
            printf("No
");
    }
    return 0;
}

View Code

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 0x3f3f3f3f

using 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
",C%3);
            }
    }
    return 0;
}

View Code

总结：

　　bitset确实是位运算一大神器，能够在各种状态压缩中起到神奇的作用，但速度方面并不十分突出，上两题测试的时间相对偏长，不过一旦用上了，想必你离成功不远了。哈哈！！

Bitset小结 （POJ2443 & HDU4920）

Bitset小结（POJ2443 & HDU4920）