Bitset优化

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
#include<bits/stdc++.h>
#define maxn 30050
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
#include<bits/stdc++.h>
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处的二进制位取反

文章目录
  1. 1. Bitset优化
    1. 1.1. hihocoder_147周
      1. 1.1.1. 题目要求
      2. 1.1.2. 参考AC代码
      3. 1.1.3. 思路
    2. 1.2. HDU 5890
      1. 1.2.1. 题目要求
      2. 1.2.2. 参考AC代码
      3. 1.2.3. 思路
    3. 1.3. 总结
|