精华内容
下载资源
问答
  • 题目链接: 条件 大致题意 QAQ 解题思路 Floyd 读完题目, 很明显是多源最短路的考察....考虑到优化: 用bitset优化, 复杂度为O(n3 / 32). ...而对于bitset优化的floyd, 我们取消掉第三层j循环, 如果g[i][k], 则g[i] |=

    题目链接: 条件

    大致题意

    QAQ

    解题思路

    Floyd

    读完题目, 很明显是多源最短路的考察. 而本题的数据范围为1E3, 我们是跑不下O(n3)的Floyd算法的.
    考虑到优化: 用bitset优化, 复杂度为O(n3 / 32).

    我们用g[N][N]数组表示两点是否可达.

    用k, i, j表示Floyd的三个循环变量, 通常的传递过程为g[i][j] |= g[i][k] and g[k][j].
    而对于bitset优化的floyd, 我们取消掉第三层j循环, 如果g[i][k], 则g[i] |= g[k].

    为什么我们可以直接这样做呢? 我们如果用bitset去优化, 则定义: bitset<N> g[N]

    其中 g[i] 用二进制的形式表示i这个点都能到那些点, 若能达, 则对应位上为1.
    g[i] |= g[k]的含义是, 对于某个点j而言, 若i能达, 或者k能达, 则g[i][j]可达.

    如果g[i][k]成立, 则i和k的可达点是相通的, 因此可以写成g[i] |= g[k].


    关于本题的数据处理方式: 我们用g1数组表示一定可达, g2数组表示可能可达.

    由于给出的m2条边是不可达边, 不可达不具有传递性, 我们要进行转换成可达情况.

    AC代码

    #include <bits/stdc++.h>
    #define rep(i, n) for (int i = 1; i <= (n); ++i)
    using namespace std;
    typedef long long ll;
    const int N = 1E3 + 10;
    bitset<N> g1[N], g2[N];
    bitset<N> vis[N];
    int main()
    {
    	int n, m1, m2, q; cin >> n >> m1 >> m2 >> q;
    	rep(i, n) g1[i][i] = 1; //这步不要忘了, 自身都是可达的.
    
    	rep(i, m1) {
    		int x, y; scanf("%d %d", &x, &y);
    		g1[x][y] = 1;
    	}
    	rep(i, m2) {
    		int x, y; scanf("%d %d", &x, &y);
    		vis[x][y] = 1;
    	}
    
    	rep(i, n) rep(j, n) if (!vis[i][j]) g2[i][j] = 1; //不是不可达, 就可能可达
    
    	rep(k, n) rep(i, n) {
    		if (g1[i][k]) g1[i] |= g1[k];
    		if (g2[i][k]) g2[i] |= g2[k];
    	}
    
    	while (q--) {
    		int x, y; scanf("%d %d", &x, &y);
    		printf("%s %s\n", g1[x][y] ? "Yes" : "No", g2[x][y] ? "Yes" : "No");
    	}
    	return 0;
    }
    

    END

    展开全文
  • 分析:利用 bitset 优化 floyed 传递闭包 (利用 bitset 优化计算个数的过程) 就是不需要用到三重循环,而是把一个节点的父亲节点的所有父亲节点累计在这个孙子 bitset 上。 (即如果一个点是另一个点的父亲,...

    好博客: https://www.cnblogs.com/cjjsb/p/9751384.html

    例题1:Newcoder 132C 简单瞎搞题

    题目链接:https://www.nowcoder.com/acm/contest/132/C

    题意:

     

    分析:核心就在于看作01背包的形式,枚举种类n,每个范围(L-R+1),以及所有的可能值 1~1e6,

    然后直接做的话又会超时,所以要用到 bitset 的位运算,将b[0][0]设置为1,每次向左移动 j*j 位,最后就可以得到经过所有组合后的可能取值。

    #include <cstdio>
    #include <bitset> 
    using namespace std;
    bitset<1000005>b[105];
    int n,l[105],r[105];
    int main()
    {
        scanf("%d",&n);
        int Min=0;
        for(int i=1;i<=n;i++) {scanf("%d%d",&l[i],&r[i]); Min+=l[i]*l[i];}
        b[0].set(0);
        //上面那句就等同于 -> b[0][0]=1;
        for(int i=1;i<=n;i++)
            for(int j=l[i];j<=r[i];j++)
                b[i]|=(b[i-1]<<(j*j));
        
        // int ans=0;
        // for(int i=Min; i<=1000005; i++){
        //     if(b[n][i]) ans++;
        // }
        // printf("%d\n", ans);
        printf("%d\n",b[n].count());
        return 0;
    }

     例题2:POJ-2443

    题目链接:https://vjudge.net/problem/POJ-2443

    题意:分析某两个元素是否存在于共同的集合。

    #include <cstdio>
    #include <cstring>
    #include <bitset>
    using namespace std;
    
    const int maxn = 1e5+3;
    bitset<1000> a[10000],t; 
    int main(){
        int q,n,m,k;
        scanf("%d",&n);
        for(int i=0; i<n; i++){
            scanf("%d",&m);
            for(int j=0; j<m; j++){
                scanf("%d",&k);
                a[k][i] = 1;
            }
        }
        scanf("%d",&q);
        int x,y;
        for(int i=0; i<q; i++){
            scanf("%d%d",&x,&y);
            t = a[x]&a[y];
            if( t.count() ){
                printf("Yes\n");
            }
            else{
                printf("No\n");
            }
        }
    }

    例题3:HDU 5036

    题意:一个人要打开或者用炸弹砸开所有的门,每个门里面有一些钥匙,一个钥匙对应一个门,有了一个门的钥匙就能打开相应的门,告诉每个门里面有哪些门的钥匙,问需要用的炸弹为多少。

    我们考虑对于每一扇们单独计算期望,根据期望的线性性质最后累加起来就是答案。

    分析:利用 bitset 优化 floyed 传递闭包 (利用 bitset 优化计算个数的过程)

    就是不需要用到三重循环,而是把一个节点的父亲节点的所有父亲节点累计在这个孙子 bitset 上。

    (即如果一个点是另一个点的父亲,那么父亲的父亲也都能够到达这个点,那就可以全部记录在这个孙子 bitset 上了 )

    #include <cstdio>
    #include <cstring>
    #include <bitset>
    using namespace std;
    
    const int maxn = 1e3+3;
    bitset<maxn> a[maxn];
    
    int main(){
        int T,kase=1;
        scanf("%d",&T);
        while(T--){
            int n,x,y;
            scanf("%d",&n);
            for(int i=1; i<=n; i++) a[i].reset();
            for(int i=1; i<=n; i++){
                a[i].set(i);
                scanf("%d",&x);
                for(int j=1; j<=x; j++){
                    scanf("%d",&y);
                    a[y].set(i);
                }
            }
            for(int i=1; i<=n; i++){
                for(int j=1; j<=n; j++){
                    if(a[j].test(i)){
                        a[j] |= a[i];
                    }
                }
            }
            double ans = 0;
            for(int i=1; i<=n; i++){
                ans += 1.0/(a[i].count());
                // printf("%d %lf\n", i,ans);
            }
            printf("Case #%d: %.5lf\n",kase++, ans);
        }
    }

     

    转载于:https://www.cnblogs.com/-Zzz-/p/11489494.html

    展开全文
  • bitset优化传递闭包

    2020-05-13 12:24:36
    这是在学 2−SAT2-SAT2−SAT 的时候突然看到的一个东西,就顺便学了一下。 先了解一下传递闭包的定义,来...由于这个东西只需要记录 0/10/10/1,所以可以用 bitsetbitsetbitset 来优化,原本一个 boolboolbool 占用一

    这是在学 2 − S A T 2-SAT 2SAT 的时候突然看到的一个东西,就顺便学了一下。

    先了解一下传递闭包的定义,来一张网上广泛用到的图:
    在这里插入图片描述
    说白了就是 c [ i ] [ j ] c[i][j] c[i][j] 表示 i i i 能不能到 j j j,能为 1 1 1,不能为 0 0 0

    显然可以用 f l o y d floyd floyd 来求这个东西,时间复杂度为 O ( n 3 ) O(n^3) O(n3)

    由于这个东西只需要记录 0 / 1 0/1 0/1,所以可以用 b i t s e t bitset bitset 来优化,原本一个 b o o l bool bool 占用一个 b y t e byte byte,而 b i t s e t bitset bitset 里面的一位只占用一个 b i t bit bit,不仅时间乘上了一个常数 1 64 \frac 1 {64} 641,空间也节省了。

    例题

    题目大意: 给出 m m m 组大小关系,问将这 n n n 个元素进行排序还需要几组大小关系。

    代码如下:

    #include <cstdio>
    #include <bitset>
    #include <algorithm>
    using namespace std;
    #define maxn 1010
    
    int n,m,ans=0;
    bitset<maxn>f[maxn];
    
    int main()
    {
    	scanf("%d %d",&n,&m);
    	for(int i=1,x,y;i<=m;i++)
    	scanf("%d %d",&x,&y),f[x][y]=1;
    	
    	for(int i=1;i<=n;i++)//floyd
    	for(int j=1;j<=n;j++)if(i!=j)
    	if(f[j][i])f[j]|=f[i];
    	
    	for(int i=1;i<=n;i++)
    	for(int j=i+1;j<=n;j++)
    	if(!f[i][j]&&!f[j][i])ans++;
    	printf("%d",ans);
    }
    
    展开全文
  • 请教了大佬bitset的优美用法——矩阵乘法 复杂度降低到(n^3/64约等于n^2) 以A*B=C(mod 3)的矩阵乘法为例: 方法:模拟了这样一个情况: bitset &lt;&gt;a[3][i][j],a[k][i][j]表示模为矩阵a[i][j]的...

    请教了大佬bitset的优美用法——矩阵乘法

    复杂度降低到(n^3/64约等于n^2)

    以A*B=C(mod 3)的矩阵乘法为例:

    方法:模拟了这样一个情况:

    bitset <>a[3][i][j],a[k][i][j]表示模为矩阵a[i][j]的状态是否为k,是为1,否为0,同理bitset<>b[3][i][j]

    比如A[1]={1,2,0,1},第1列B[1]={2,1,1,0}

    通过bitset存储状态后,可以得到:

    a[0][1][]={0,0,1,0}  

    a[1][1][]={1,0,0,1}

    a[2][1][]={0,1,0,0}

     

    b[0][1][]={0,0,0,1}

    b[1][1][]={0,1,1,0}

    b[2][1][]={1,0,0,0}

     

    c[i][j]=1*(模数1&1)+2*(模数1&2)+2*(模数2&1)+2*2*(模数2&2)

     

    上代码!:

    #include<cstdio>
    #include<math.h>
    #include<string.h>
    #include<vector>
    #include<algorithm>
    #include<queue>
    #include<bitset>
    #include<iostream>
    
    #define pi pair<int,int> 
    #define CLR(a,b) memset(a,b,sizeof(a))
    #define ll long long
    
    using namespace std;
    const int maxn=808;
    bitset<maxn>a[3][maxn],b[3][maxn];
    
    int main(){
    	int n;
    	while(~scanf("%d",&n)){
    		CLR(a,0);
    		CLR(b,0);
    
    		for(int i=0;i<n;i++){
    			for(int j=0;j<n;j++){
    				int m;
    				scanf("%d",&m);
    				if(m){
    					a[m%3][i][j]=1;
    				}
    			}
    		}
    
    		for(int i=0;i<n;i++){
    			for(int j=0;j<n;j++){
    				int m;
    				scanf("%d",&m);
    				if(m){
    					b[m%3][j][i]=1;
    				}
    			}
    		}
    
    		for(int i=0;i<n;i++){
    			for(int j=0;j<n;j++){
    				int ans=0;
    				ans+=(a[1][i]&b[1][j]).count();
    				ans+=2*((a[1][i]&b[2][j]).count ());
    				ans+=2*((a[2][i]&b[1][j]).count ());
    				ans+=(a[2][i]&b[2][j]).count ();
    				if(j)printf(" ");
    				printf("%d",ans%3);
    			}
    			printf("\n");
    		}
    	}
    }

     

    展开全文
  • bitset优化

    2017-05-14 20:31:09
    那么这里就用到了c++ STL里边的bitset,很是实用。 #include #define MAXN 30005 using namespace std; bitset<MAXN> bit[5][MAXN]; //bit[i][j]代表第i科第j名之前的人。 int N; int a[MAXN][5]; int ido[5]...
  • 题目大意: 给你一个01矩阵大小n∗mn*mn∗m.让你构造出一组非全零矩阵使得所有点它所相邻的...加上bitset优化即可.复杂度为:O((n∗m)364)O(\frac{(n*m)^3}{64})O(64(n∗m)3​).–其实都不用改什么地方,把数组改成bits
  • bitset优化的Floyd传递闭包 的方法,其复杂度为O(n^2) 注意和朴素的floyd方法相似,先枚举中间点,只不过这里的后继点利用bitset二进制状态表示。 #include #include #include #include #include...
  • 题目链接:A-Matrix Equation_第 45 届国际大学生程序设计竞赛(ICPC)亚洲区域赛(济南) (nowcoder.com) 题意:给我们两个个n行n列的矩阵A和矩阵B,让我们求出来满足A×C=B⊙C的矩阵C的个数。...
  • 之前大佬的题解里面用到了这个优化,还是比较实用的,特别是在大bool数组中用了这个省空间省时间(比如邻接矩阵用这个会快很多),具体的用法各种博客里面有很多,百度搜索bitset即可,在这里就不赘述,我就说一些我...
  • bitset优化Floyd求传递闭包

    千次阅读 2017-08-29 16:25:42
    思路:bitset优化Floyd 详情: http://blog.csdn.net/wzw1376124061/article/details/69870161 代码: /************************************************************************* > Author: ...
  • 表算还要用bitset优化三进制加法,尽管如此仍然跑的极慢,反正我用了一晚上卡常都没卡过去。 代码 # include typedef unsigned long long LL ; const int N = 65 ; int n , stack [ N ] ; ...
  • 优化到 O ( n 4 / w ) O(n^4/w) O ( n 4 / w ) 然后考虑这个在转移中,假设当前枚举到第 i i i 种物品,对于一个 f [ j ] f[j] f [ j ] ,能够转移来的 f [ k ] f[k] f [ k ] 间相隔的距离是相同的,是 v [ i ] v[i] ...
  • 大意:给定两组数,分别从两组数中取一个数,两个数异或后得到的数的二进制形式中的1的个数刚好...bitset优化:用bitset标记b是否出现,这样就不用每次在map中找了。 时间复杂度: Code #include <bits/stdc++.
  • 大意: n个人, 5门课, 给定每个...明显是个5维偏序问题, 题目有保证排名均不同, 可以用bitset优化为$O(\frac{n^2}{\omega})$ #include <iostream> #include <algorithm> #include <cstdio>...
  • 这样做的复杂度是n3,考虑到dp的状态只有01两种,我们可以用bitset优化。把第二层循环压成bitset,复杂度变成n3/64。 bitset内部实现: 内部维护了一个long数组,初始只有一个long,所以BitSet最小的size是64,...
  • #include <bitset> using namespace std; typedef long long ll; const int N = 2010; bitset<N> mp[N]; int n; char s[N]; //不知道为什么用string输入会RE void floyd() { for(int k = 0; k ; ++k) { for(int...
  • 题目描述 传送门 题解 刚开始想的有问题,因为很多子集...ai)2)'>O((∑ai)2)O((∑ai)2)O((\sum a_i)^2)的,考虑怎么优化 很显然最终的答案只与f的奇偶有关,那么让f(i)表示和为i的子集的个数%2的值 转移就变成了
  • 考虑先判断是否有奇环,后面再使用bitset优化图的遍历就可以了,时间复杂度 O(m+n364)O(m+\frac{n^3}{64})O(m+64n3​) #include using namespace std; const int N=1010; int first[N],len,n,m; int op[N],qs[N]; ...
  • hdu 5506 bitset 优化

    2017-08-09 19:57:00
    思路:L比较小,直接暴力每个数组是在哪个集合里,大约30^5 同时用bitset维护某种集合是否合法,总时间复杂度30^5*300/64 看上去非常的大,其实加上合法性剪纸跑的还是飞快的。。。甚至0ms 。。。黑人问号??? ...
  • AC自动机的经典问题,但是在这个题目中匹配串的个数过于多,所以并不能这样做,因为匹配串的长度比较短,所以可以预处理出一个可行数组用来记录哪个位置可以放置哪个数字,这样就能将时间复杂度优化为 n * m 暴力...
  • Bitset优化Dp 题目链接 一般DP做法 显然后面的数是与前面的数字相关的,所以我们有dp数组,dp[i][j]dp[i][j]dp[i][j]选取了jjj个数,iii是否可以被创造出来,如果可以其值为1,否则为0。 所以我们显然有如下的状态...
  • bitset优化FLOYD HDU 3275

    2019-09-24 20:30:37
    <bitset> #include using namespace std; typedef long long LL; #define MAXN 1009 #define N 100 #define INF 0x3f3f3f3f /* 传递闭包关系 如果排序好的数字 它们之间已经知道的关系数目肯定是C...
  • 矩阵乘法分配律+bitset优化——hdu4920

    千次阅读 2019-07-13 21:36:00
    因为是模3,所以把原矩阵拆成两个01矩阵,然后按分配律拆开分别进行矩阵乘法,行列用bitset来存进行优化即可 注意 int bitset<int>::count() 函数可以统计bitset里有多少1 int bitset<int>::any()...
  • 我们可以用bitset来进行优化一下,。 最后,求其中“1”的个数就可以了,别忘了要给dp[0].set(0)。 #include #include #include #include #include #include #include #include #include #include #include #...
  • bitset优化dp Music Problem

    2020-04-15 11:16:54
    题意:就是给定n<=1e5n<=1e5n<=1e5个数,从中选取k个数,要求和是3600的倍数,T<=60组数据T<...可以用bitset优化,每次更新不用3600,而是直接移位(<<),然后在取个模(>>)...
  • 题目链接 有两个大小为N *N的矩阵,我们现在想知道它们的乘积是多少。... 然后,就是优化了,我们现在看一下0、1、2两两相乘有什么特殊的情况: const short int dir[3][3] = { 0, 0, 0, 0, 1, 2, ...
  • 高斯消元法是将矩阵化为上三角矩阵 高斯—若尔当消元法是 选定主元后,将主元化为1,枚举除主元之外的...bitset<N>a[N]; int n; void Gauss() { int now=0; for(int i=0;i<n;++i) { in...
  • CodeForces - 577B Modulo Sum(dp+bitset优化)

    千次阅读 2020-12-18 16:05:42
    题目大意:给出一个长度为 n 的数列,现在问能否...不过时空复杂度都是 n * m 级别的,因为是 01 背包,所以可以将空间复杂度优化掉一维,到此为止分支出了两种做法: 因为 dp 数组只有 0 或 1 两种状态,所以不难想
  • 每次问删掉第i,j,k个数后,是否存在一种选10个数和为87的方案,只需要输出 ’Yes’ 或者 ’No’ 解题报告: 直接可行性背包,然后bitset优化一下就可以了。 AC代码: #include #include #include #include #include ...
  • 题干: 给你一个二维字符矩阵,... 考虑最暴力的方法,开个二维数组来存每两个顶点之间的邻接关系,但是N^3肯定是会TLE的,考虑bitset压位优化。(神奇) AC代码: #include&lt;bits/stdc++.h&gt; u...

空空如也

空空如也

1 2 3 4 5 ... 20
收藏数 10,536
精华内容 4,214
关键字:

bitset优化