8.21

你鸽鸽过生

算法竞赛进阶指南笔记

P2114 [NOI2014]起床困难综合症

  • bitset
  • 二进制状态压缩 LYD P8
#include<bits/stdc++.h>
using namespace std;

bitset<30>a,b((1<<30)-1),c;
int n,m,r;
char s[5];
int main(){
    scanf("%d%d",&n,&m);
    for(int i=1;i<=n;i++){
        scanf("%s%d",s,&r);
        if(s[0]=='A')a&=r,b&=r;
        if(s[0]=='O')a|=r,b|=r;
        if(s[0]=='X')a^=r,b^=r;
    }
    for(int i=0;i<30;++i){
        if(a[i]|(b[i] && c.to_ulong()<m))
            c[i]=1;
    }
    printf("%d",c.to_ulong());
}

关于bitset

bitset用来存储二进制数位。像一个bool类型的数组一样,bitset每个元素只有0或1两个数值。
但是有空间优化——bitset中的一个元素一般只占1 bit。
bitset中的每个元素都能单独被访问,例如下面的代码:

输出格式

printf("%d\n",x.to_ulong());

cout<<x<<endl;

bitset<15>a,b(string("101")); //定义bitset,15是指有15位

a[10]=1; //将第10位定义为1

输出a;

输出b;

a=101; //赋值a

输出a;

输出:
1024

000010000000000

5

000000000000101

101

000000001100101

可以看出,a[10]=1相当于+2^10。
而下面直接输出bitset就很玄妙。
另外,字符串可以直接转到bitset中。
有意思的是,bitset可以直接赋值!
当然也可以bitset<15>c(101)来赋值!

then

bitset<4> a ( string("1001"));
bitset<4> b ( string("0011"));

cout << (a^=b) << endl; // 1010
cout << (a&=b) << endl; // 0010
cout << (a|=b) << endl; // 0011

cout << endl << a << endl; // 0011
cout << b << endl << endl; // 0011

cout << (a<<=2) << endl; // 1100
cout << (a>>=1) << endl; // 0110

cout << (~b) << endl; // 1100
cout << (b<<1) << endl; // 0110
cout << (b>>1) << endl; // 0001

cout << (a==b) << endl; // false (0110==0011)
cout << (a!=b) << endl; // true (0110!=0011)

cout << (a&b) << endl; // 0010
cout << (a|b) << endl; // 0111
cout << (a^b) << endl; // 0101

看完这些,估计您已经对bitset有个深刻的了解,它资瓷位运算!

then

对于一个叫做a的bitset:
a.size() 返回大小(位数)

a.count() 返回1的个数

a.any() 返回是否有1

a.none() 返回是否没有1

a.set() 全都变成1

a.set(p) 将第p+1位变成1

a.set(p, x) 将第p+1位变成x

a.reset() 全都变成0

a.reset(p) 将第p+1位变成0

a.flip() 全都取反

a.flip(p) 将第p+1位取反

a.to_ulong() 返回它转换为unsigned long的结果,如果超出范围则报错

a.to_ullong() 返回它转换为unsigned long long的结果,如果超出范围则报错

a.to_string() 返回它转换为string的结果

如何不把八数码问题中的占位符‘0’读进去?

int ok=0,x;
        rep(i,1,n*n){
            rd(x);
            if(x==0)ok=1;
            else a[i-ok]=x;
        }
上一篇:Codeforces 1097F. Alex and a TV Show


下一篇:c – 可变大小的bitset