文章目录
bitset 使用 - 为了更快的暴力
写在前面：
bitset是c++是一个模板库，
bitset主要用于状态压缩，bitset可以用每一位0或者1来表示可达性，例如图上点与点的可达性，dp时可达性
bitset主要用于暴力枚举，如果bitset的长度是n,一次与运算的复杂度就是n/32
bitset主要用于合并集合，交并补运算显示不同的逻辑意义
1 bitset库
2 bitset 用法
2.1集合求交并的计数运算
2.1.1可达性统计
1 ASC28J
题意：给定一个有向图的邻接矩阵，求有多少个，三元环，即 A−>B−>C−>A
分析： n<=1500,必须用bitset运算， b[i][j]=1代表 有 i−>j的边， a[i][j]=1,代表有从j到i的边，我们枚举环的起点i，第二个点j，那么第三个点必定满足 b[j][k]&a[i][k]=1,这样子可以直接 (b[j]&a[i]).count()
LL cnt = 0;
rep(i,0,n)
rep(j,0,n)
if(b[i][j])
cnt += (b[j]&a[i]).count();
cout<<cnt/3<<endl;
2 2101 可达性统计
题意: 给定义一个有向无环图，求每一个点可达的点有多少个
分析：先求出拓扑序，从拓扑序下面往上推，即可
for(int i = N;i >= 1; --i){
for(auto c:G[topo[i]])
b[topo[i]] |= b[c];
}
for(int i = 1;i <= N; ++i)
printf("%d\n",(int)b[i].count());
升级版
hdu 5036 Explosion
n（1000）个房间，每个房间的门必须用其特定钥匙才能打开
每个房间有若干个 n把钥匙（编号1-n）
我们初始没有钥匙，当我们手中的钥匙再也无法开任何一扇门的时候，我们必须要爆破一个房间
问你我们最终进入所有房间的期望爆破数
需要先统计出打开某个房间取出的钥匙，能打开的房间都有哪些，这一题不同于上一题，不是一个无环图，不能通过拓扑序来求，用floyd传递闭包来做，但是floyd是n^3 的，我们不能暴力枚举，可以用bitset来优化
for(int k = 0;k <n; ++k)
for(int i = 0;i < n; ++i)
for(int j = 0;j < n; ++j)
a[i][k] |= a[k][j];
for(int k=0;k<n;k++)
for(int i=0;i<n;i++)
if(a[i][k])
a[i]|=a[k];
令 ki=∑i=0i=n−1[a[j][i]==1]
对于计算概率，我们计算某一个被暴力破开的概率，那就是 1/ki，为什么呢，如果暴力破开i,所有能打开i的都在i的前面被打开，这样的排列数是
ki!(ki−1)!=1/ki
2.1.2集合运算
3大厦 hdu 6496
题意:在N*M 的平面上有n个x+y = c 和m个x-y = c 的n+m条直线，c各不相同，求共有多少个完整的矩形 n,m<=1e3
分析: 四条边能组成的条件是相交的四个点都在平面内，于是我们枚举两条x+y = c的直线，枚举两条 x-y = c 的直线，很不幸超时了，但是算法思想是正确的，我们枚举可以用bitset来加速这个方法，我们预处理出于x+y = c 相交的x-y= c 的m条直线的交点是否在平面内，然后枚举两条x+y = c 的直线，用bitset求交集即可
LL cnt = 0;
for(int i = 0;i < n; ++i)
for(int j = i+1;j < n; ++j)
{
LL t = (b[i]&b[j]).count();
cnt += t*(t-1)/2,cnt %= mod;
}
printf("%lld\n",cnt);
2.2 bitset与动态规划
2.2.1 背包dp
题意: 给定一个二分图，n个点 n≤10000，m条边 m≤100000,求如果将其变成完全二分图，最多可以加多少条边？
分析：显然最优的是左边n条边，右边n-n/2 条边，但是题目给的情况可能不满足，我们需要有一个方案最优化，首先我们需要将这n个点变成若干个联通块，一个联通块是一个整体，对于每一个联通块，我们有 a,b a+b 是联通块的大小，a与b的颜色不同，求出联通块之后做背包dp，注意这还是个分组背包，代表是否可以dp[i] 代表是否可以构成i,n-i 这样的二分完全图
typedef pair<int,int> P;
const int maxn = 10010;
bool vis[maxn];
int a[maxn];
int Left,Right;
vector<int> G[maxn];
void dfs(int node,bool now){
if(vis[node]) return ;
vis[node] = 1;
a[now]++;
for(auto c: G[node]){
dfs(c,now^1);
}
}
int main(void)
{
int T;cin>>T;
while(T--){
int n,m;cin>>n>>m;
for(int i = 0;i <= n; ++i) G[i].clear();
me(vis);
rep(i,0,m){
int u,v;scanf("%d%d",&u,&v);
G[u].Pb(v);
G[v].Pb(u);
}
vector<P> vec;
for(int i = 1;i <= n; ++i)
if(!vis[i]){
a[0] = a[1] = 0;
dfs(i,1);
vec.push_back(P(a[0],a[1]));
}
bitset<maxn> b;
b.set(0);
for(auto p:vec){
int x = p.first;
int y = p.second;
b = b<<x|b<<y;
}
LL ans = 0;
for(int i = 1;i < n; ++i){
if(b[i]){
ans = max(ans,1ll*(n-i)*i-m);
}
}
cout<<ans<<endl;
}
return 0;
}
hdu5809 Eighty seven
题意：n个数(n <= 50) ，Q 次查询去掉三个(可以一样)，剩下的数能不能组成87
分析： 直接使用bitset优化背包即可 先预处理所有的i,j,k O(6n∗(n−1)∗(n−2)∗80/32) 还有其他更优的做法，不再展开
const int maxn = 50+10;
// bitset<8> b;
int a[maxn];
// bool del[maxn];
bitset<90> b[11];
bool vis[maxn][maxn][maxn];
int n;
bool judge(int da,int db,int dc){
for(int i = 0;i <= 10; ++i) b[i].reset();
b[0].set(0);
for(int i = 1;i <= n; ++i){
if(i == da || i == db ||i == dc) continue;
for(int j = 10;j > 0; --j)
b[j] |= b[j-1]<<a[i];
}
// cout<<b<<endl;
return b[10][87];
}
int main(void)
{
int t;cin>>t;
while(t--){
me(vis);
cin>>n;
for(int i = 1;i <= n; ++i)
cin>>a[i];
int q;cin>>q;
for(int i = 1;i <= n; ++i)
for(int j = i;j <= n; ++j)
for(int k = j;k <= n; ++k)
if(judge(i,j,k)){
vis[i][j][k] = vis[i][k][j] = 1;
vis[j][i][k] = vis[j][k][i] = 1;
vis[k][i][j] = vis[k][j][i] = 1;
}
while(q--){
int da,db,dc;//.cin>>da>>db>>dc;
scanf("%d%d%d",&da,&db,&dc);
if(vis[da][db][dc])
puts("Yes");
else
puts("No");
}
}
return 0;
}
codeforces 688E. The Values You Can Make
题意:n个物品，背包容量为k，求组成容量为k的背包的若干物品物品还可以组成哪些状态?
分析：非常有趣的背包问题，我想了很多假设都失败了，然后联想到之前所说，bitset就是用于集合合并的原理后恍然大悟，加入dp[j] 代表组成i时，还能组成元素的集合，对于第i个物品 dp[j]∣=dp[j−a[i]]∣(dp[j−a[i]]<<a[i]),代表组成 j−a[i] 的集合，合并进入dp[j]
const int maxn = 500+10;
bitset<maxn> b[maxn];// 以为到达j,时的子集和
int a[maxn];
int main(void)
{
int n,k;cin>>n>>k;
for(int i = 1;i <= n; ++i)
cin>>a[i];
b[0][0] = 1;
for(int i = 1;i <= n; ++i){
for(int j = k;j >= a[i]; --j){
b[j] |= (b[j-a[i]]<<a[i])|b[j-a[i]];
}
}
vector<int> vec;
for(int i = 0;i <= k; ++i)
if(b[k][i])
vec.push_back(i);
cout<<vec.size()<<endl;
for(auto c: vec)
cout<<c<<" ";
return 0;
}
2.3 bitset 与字符串匹配
- Substring Query 匹配串中各模板串出现次数(没法提交)
//[题意]
//字符串长度为 5e4，操作个数为 1e5
//询问有两种：
//1：p ch 修改 s[p]为 ch
//2：0 string 询问 string 在 s 中出现的次数
//[分析]
for (int i = 0; i < 26; ++i)
b[i].reset();
for (int i = 1; i <= l; ++i)
b[s[i] - 'a'].set(i); //依然是形成了一个 字符 -> 位置 的套路
while (q--) {
int op;
scanf("%d", &op);
//询问是即时完成的
if (op == 0) {
scanf("%s", ss + 1);
int ll = strlen(ss + 1);
//一开始得到了哪些位置可以是匹配 ss[1]的位置
bt = b[ss[1] - 'a'];
//然后我们把匹配位置 >> (i - 1) 与 1 对其，得到了其延展
for (int i = 2; i <= ll; ++i)
bt &= (b[ss[i] - 'a'] >> (i - 1));
printf("%d\n", bt.count());
}
//修改只需要对 bitset 做暴力修改
else {
char ch;
scanf(" %c", &ch);
b[s[op] - 'a'].reset(op);
b[ch - 'a'].set(op);
s[op] = ch;
}
}
- 14 HDU5745 La Vie en rose
目标串多少子串可以被原始串做相邻交换得到
- coderoces458F. Substrings in a String
题意：给定目标串，求模板串 [l,r] 有多少个给定串，还要支持单点修改
分析：加了要去[l,r] 只需要根据bruteforce匹配的原理修改即可
复杂度惊人 O(N2/32)，但是时限也高 ,吉老师在这场比赛中用了这种方法,点击暴力踩标算
const int maxn =100000+10;
char ar[maxn];
bitset<maxn> b[30];
char br[maxn];
bitset<maxn> ans,tmp;
int main(void)
{
cin>>ar;
int n = strlen(ar);
for(int i = 0;i < n; ++i){
b[ar[i]-'a'].set(i);tmp[i] = 1;
}
int q;cin>>q;
while(q--){
int op,x,y;scanf("%d",&op);
if(op == 1){
scanf("%d %s",&x,br);
x--;
b[ar[x]-'a'].reset(x);
b[br[0]-'a'].set(x);
ar[x] = br[0];
}
else{
scanf("%d%d %s",&x,&y,br);
int m = strlen(br);
x--,y--;
// cout<<((tmp>>x)<<x)<<endl;
ans = (tmp>>(n-max((y-x+1-m+1),0)))<<x;
// cout<<ans<<endl;
// cout<<ans<<endl;
for(int i = 0;i < m; ++i)
ans &= b[br[i]-'a']>>i;
// cout<<ans<<endl;
printf("%d\n",(int)ans.count());
}
}
return 0;
}
京公网安备 11010502036488号