Bitset优化
hihocoder_147周
题目要求
问题可以一般化为:有一些五维坐标系里的点 对于每一个点 求出五个纬度均比该点小的点个数
参考AC代码
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31
| using namespace std; int a[maxn][5],b[5][maxn]; bitset<maxn>s[5][maxn],t; //s[i][j]:第i门课排在j-1之前的编号情况 int main(){ // freopen("input.txt","r",stdin); int n; scanf("%d",&n); for(int i=1;i<=n;i++){ for(int j=0;j<=4;j++){ scanf("%d",&a[i][j]); b[j][a[i][j]]=i; //第j门课排第a[i][j]名的是编号为i的人 } } for(int j=0;j<=4;j++){ s[j][1]=0; for(int i=2;i<=n;i++){ s[j][i]=s[j][i-1]; s[j][i].set(b[j][i-1]); } } for(int i=1;i<=n;i++){ t=s[0][a[i][0]]; for(int j=1;j<=4;j++){ t&=s[j][a[i][j]]; } printf("%d\n",t.count()); } return 0; }
|
思路
用hash的思想求出每门课排名1-n的学生编号。
s[i][j]表示第i门课排名1-j-1的学生编号情况(该位置为1表示存在该学生编号 0表示没有)
s的预处理可以用递推的方式 由于每个集合都是建立在上一个集合的基础上 所以每次s先初始化为上一个集合
内的情况 再把该排名的学生编号的位置置为1即可
对于每个学生 可以把每门课的情况看作一个集合 分别求与操作后 剩下位置剩余的1的个数就是每门课都比
该学生好的个数
HDU 5890
题目要求
有一些数字和一些询问
每次询问包括三个数字ijk 表示ijk三个位置的数字不能用
能否从剩余的数字中取10个使他们的和为87
参考AC代码
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42
| using namespace std; bitset<99>s[15]; int dp[55][55][55]; int num[55]; int n; void pre_solve(int x,int y,int z){ for(int i=0;i<=11;i++) s[i].reset(); s[0][0]=1; for(int i=1;i<=n;i++){ if(i==x||i==y||i==z||num[i]>87) continue; for(int j=10;j>=1;j--){ s[j]|=s[j-1]<<num[i]; } } if(s[10][87]==1) dp[x][y][z]=1; else dp[x][y][z]=0; } int main(){ // freopen("input.txt","r",stdin); int t; scanf("%d",&t); while(t--){ scanf("%d",&n); for(int i=1;i<=n;i++) scanf("%d",&num[i]); for(int i=1;i<=n;i++) for(int j=i;j<=n;j++) for(int k=j;k<=n;k++){ pre_solve(i,j,k); } int q; scanf("%d",&q); while(q--){ int x[3]; scanf("%d%d%d",&x[0],&x[1],&x[2]); sort(x,x+3); if(dp[x[0]][x[1]][x[2]]==1) printf("Yes\n"); else printf("No\n"); } } return 0; }
|
思路
s[i][j]表示取到i个数字和为j的情况
首先预处理所有数字的情况 由于数字是升序 所以询问的三个数字需要升序排列
判断dp值是否为1即可
总结
bitset多用于表示多维状态的“有”或者“没有” 对01串进行操作
简单背包:多个数字或者用给定个数的数字相加后的情况 能否等于一个数还是所有的情况
b.any()
b中是否存在置为1的二进制位?
b.none()
b中不存在置为1的二进制位吗?
b.count()
b中置为1的二进制位的个数
b.size()
b中二进制位的个数
b[pos]
访问b中在pos处的二进制位
b.test(pos)
b中在pos处的二进制位是否为1?
b.set()
把b中所有二进制位都置为1
b.set(pos)
把b中在pos处的二进制位置为1
b.reset()
把b中所有二进制位都置为0
b.reset(pos)
把b中在pos处的二进制位置为0
b.flip()
把b中所有二进制位逐位取反
b.flip(pos)
把b中在pos处的二进制位取反