精华内容
下载资源
问答
  • HDU 5890 Eighty seven——bitset优化01背包
    2018-08-15 00:27:54
    #include <cstdio>
    #include <cstring>
    #include <iostream>
    #include <algorithm>
    #include <bitset>
    using namespace std;
    inline void input(int &x) {
        char c;
        x = 0;
        while ((c = getchar()) < '0' || c > '9');
        while ('0' <= c && c <= '9') x = x * 10 + (c - '0'), c = getchar();
    }
    int n, a[55];
    bool ans[55][55][55];
    bitset<100> dp[15];
    void init(int x, int y, int z) {
        for (int i = 0; i <= 10; i++) dp[i].reset();
        dp[0][0] = 1;
        for (int i = 1; i <= n; i++) {
            if (i == x || i == y || i == z || a[i] > 87) continue;
            for (int j = 10; j >= 1; j--) dp[j] |= dp[j-1]<<a[i];
        }
        if (dp[10][87] == 1) ans[x][y][z] = 1;
        else ans[x][y][z] = 0;
    }
    int main() {
        int T;
        input(T);
        while (T--) {
            input(n);
            for (int i = 1; i <= n; i++) input(a[i]);
            for (int i = 1; i <= n; i++) {
                for (int j = i; j <= n; j++) {
                    for (int k = j; k <= n; k++) {
                        init(i, j, k);
                    }
                }
            }
            int Q, t[3];
            input(Q);
            while (Q--) {
                input(t[0]); input(t[1]); input(t[2]);
                sort(t, t + 3);
                if (ans[t[0]][t[1]][t[2]]) puts("Yes");
                else puts("No");
            }
        }
        return 0;
    }
    

     

    更多相关内容
  • 好博客:... 例题1:Newcoder 132C 简单瞎搞题 ... 题意: ...分析:核心就在于看作01背包的形式,枚举种类n,每个范围(L-R+1),以及所有的可能值 1~1e6, 然后直接做的话...

    好博客: 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

    展开全文
  • 01背包问题: 题目链接 题意:n个物品一个m容量的背包,n个物品有need[i]的体积消耗,以及权值value[i] ,问m容量装n个物品能得到的最大权值是多少。 做法:01背包介绍:博客 代码: #include<bits/stdc++...

    01背包问题:

    题目链接

    题意:n个物品一个m容量的背包,n个物品有need[i]的体积消耗,以及权值value[i] ,问m容量装n个物品能得到的最大权值是多少。

    做法:01背包介绍:博客

    代码:

    #include<bits/stdc++.h>
    using namespace std;
    typedef long long ll;
    inline ll read()
    {
    	ll x=0,w=1; char c=getchar();
    	while(c<'0'||c>'9') {if(c=='-') w=-1; c=getchar();}
    	while(c<='9'&&c>='0') {x=(x<<1)+(x<<3)+c-'0'; c=getchar();}
    	return w==1?x:-x;
    }
    const int N=5e2+10,M=1e5+10;
    int n,m,dp[M],need[N],value[N];
    int main()
    {
        n=read(),m=read();
        for(int i=1;i<=n;++i){
            need[i]=read(),value[i]=read();
        }
    
        for(int i=1;i<=n;++i){
            for(int j=m;j>=need[i];--j){
                dp[j]=max(dp[j],dp[j-need[i]]+value[i]);
            }
        }
        printf("%d\n",dp[m]);
    }
    

    Bitset优化01背包

    需要更正一个地方是,这里的bitset优化的不是朴素的01背包,而是只有01状态的多重背包。

    之前的博客:[博客C回到过去]  [题目链接 C回到过去]

    #include<bits/stdc++.h>
    using namespace std;
    typedef long long ll;
    const int N = 100010;
    bitset<N>f[451],g[451];
    
    
    int a[N],cnt[N],ans[N],anss;
    int main() {
    
        int n,m;
        scanf("%d%d",&n,&m);
        for(int i = 1;i <= n;++i) scanf("%d",&a[i]);
    
        sort(a + 1,a + n + 1);
    
    
        int tot = 0;
        for(int i = 1;i <= n;++i) {
            if(a[i] != a[i - 1])  a[++tot] = a[i];
            cnt[tot]++;
        }
    
        n = tot;
    
        f[0][0] = 1;
        g[n + 1][0] = 1;
    
        for(int i = 1;i <= n;++i) {
            int k = a[i],tmp = cnt[i];//f[i]|=f[i]<<a[i]代表f[i]取一个a[i]时的状态转移
    
            f[i] = f[i - 1];
    
            for(int j = 1;j <= tmp;tmp -= j,j <<= 1,k <<= 1) f[i] |= f[i] << k;
            // 运用倍增(二进制)的思想,节约时间 并且能够覆盖所有的状态
            //比如现在有5个1
            //j=1 1一个1  可以 得到 bitset状态:000011(从后往前数从低位到高位,低位从0开始)
            //j=2 那么倍增一下,两个1 :之前的状态00011移两位得  001100
            //或上之前得000011  得    001111   是不是得到0,1,2,3,都是1的情况
            //需要注意的是现在我们应该是消耗了三个1了 j目前还是2。那么tmp就不是一成不变的,所以tmp-=j
            //接着j继续乘2  j =4  由于5个1消耗了3  剩余两个,小于j   跳出for循环
             //因为有剩余的部分,就继续组合一下
            f[i] |= f[i] << (a[i] * tmp);
        }
    
        for(int i = n;i >= 1;--i) {
            int k = a[i],tmp = cnt[i];
    
            g[i] = g[i + 1];
    
            for(int j = 1;j <= tmp;tmp -= j,j <<= 1,k <<= 1) g[i] |= g[i] << k;
    
            g[i] |= g[i] << (a[i] * tmp);
        }
    
        for(int i = 1;i <= n;++i) {
            int flag = 0;
            for(int j = 0;j <= m;++j) {
                if(f[i - 1][j] & g[i + 1][m - j]) {
                    flag = 1;break;
                }
            }
            if(!flag) ans[++anss] = a[i];
        }
    
    //  for(int i = 1;i <= n;++i) printf("%d %d\n",a[i],cnt[i]);
    
        printf("%d\n",anss);
        for(int i = 1;i <= anss;++i) printf("%d ",ans[i]);
        return 0;
    }
    

    多重背包

    来一道例题:题目链接

    题意:n经费,m种类的大米,每种大米有 金额p[i] 重量h[i] 以及最多的袋数c[i]   问在n经费内 时能得到的最大重量是多少?

    做法:朴素的多重背包

    #include<bits/stdc++.h>
    using namespace std;
    
    typedef long long ll;
    const int N=1e2+10;
    int n,m,p[N],h[N],c[N],dp[N];
    inline ll read()
    {
    	ll x=0,w=1; char c=getchar();
    	while(c<'0'||c>'9') {if(c=='-') w=-1; c=getchar();}
    	while(c<='9'&&c>='0') {x=(x<<1)+(x<<3)+c-'0'; c=getchar();}
    	return w==1?x:-x;
    }
    
    int main()
    {
        int _=read();while(_--)
        {
            n=read(),m=read();
            for(int i=1;i<=m;++i) p[i]=read(),h[i]=read(),c[i]=read();
    
            for(int i=0;i<=n;++i) dp[i]=0;
    
            for(int i=1;i<=m;++i){//枚举种类
                for(int j=1;j<=c[i];++j){//c[i]次的01背包
                    for(int k=n;k>=p[i];--k){
                        dp[k]=max(dp[k],dp[k-p[i]]+h[i]);
                    }
                }
            }
            printf("%d\n",dp[n]);
        }
    }
    

    二进制优化多重背包

    题目链接:牛客E题

    这部分做法参考来自:wiki

    #include<bits/stdc++.h>
    using namespace std;
    typedef long long ll;
    #define IO ios::sync_with_stdio(false)
    #define pb push_back
    #define mk make_pair
    const int N = 1e5+10;
    const int mod = 1e9+7;
    
    int n;
    int t[N], q[N], s[N];
    int dp[2000];
    
    int main(){
        int h1, m1, h2, m2;
        scanf("%d:%d %d:%d %d", &h1, &m1, &h2, &m2, &n);
        if(m1 > m2){
            m2 += 60; h2--;
        }
        int sumt = (h2-h1)*60 + m2 - m1;
        for(int i = 0; i <= sumt; i++){
            dp[i] = 0;
        }
        for(int i = 1; i <= n; i++){
            scanf("%d%d%d", t+i, q+i, s+i);
        }
        int index = 0;
        for(int i = 1; i <= n; i++){
            int c = 1;
            if(s[i] == 0 || s[i] >= sumt/t[i]) {
                for(int j = t[i]; j <= sumt; j++){//普通的完全背包
                    dp[j] = max(dp[j], dp[j-t[i]] + q[i]);
                }
            }
            else{
                while(s[i] - c > 0){//多重背包的二进制优化 
                    s[i] -= c;
                    for(int j = sumt; j >= c*t[i]; j--){
                        dp[j] = max(dp[j], dp[j-c*t[i]] + c*q[i]);
                    }
                    c *= 2;
                }
                if(s[i]){
                    for(int j = sumt; j >= s[i]*t[i]; j--){
                        dp[j] = max(dp[j], dp[j-s[i]*t[i]] + s[i]*q[i]);
                    }
                }
            }
        }
        printf("%d\n", dp[sumt]);
        return 0;
    }
    

     

    展开全文
  • 做法:利用bitset预处理,bitset是什么玩意?和set一样,都可以看作是集合,只不过里面的值只有0/1,这里面bitset定义为数组,ss[已经用的数字个数][凑出来的和],那么ss[j]|=ss[j-1][i];的意思就是在添加了第i个数...

    Eighty seven

    Time Limit: 3000/1000 MS (Java/Others)    Memory Limit: 102400/102400 K (Java/Others)
    Total Submission(s): 583    Accepted Submission(s): 208


    Problem Description
    Mr. Fib is a mathematics teacher of a primary school. In the next lesson, he is planning to teach children how to add numbers up. Before the class, he will prepare N cards with numbers. The number on the i -th card is ai . In class, each turn he will remove no more than 3 cards and let students choose any ten cards, the sum of the numbers on which is 87 . After each turn the removed cards will be put back to their position. Now, he wants to know if there is at least one solution of each turn. Can you help him?
     

    Input
    The first line of input contains an integer t (t5) , the number of test cases. t test cases follow.
    For each test case, the first line consists an integer N(N50) .
    The second line contains N non-negative integers a1,a2,...,aN . The i -th number represents the number on the i -th card. The third line consists an integer Q(Q100000) . Each line of the next Q lines contains three integers i,j,k , representing Mr.Fib will remove the i -th, j -th, and k -th cards in this turn. A question may degenerate while i=j , i=k or j=k .
     

    Output
    For each turn of each case, output 'Yes' if there exists at least one solution, otherwise output 'No'.
     

    Sample Input
      
    1 12 1 2 3 4 5 6 7 8 9 42 21 22 10 1 2 3 3 4 5 2 3 2 10 10 10 10 11 11 10 1 1 1 2 10 1 11 12 1 10 10 11 11 12
     

    Sample Output
      
    No No No Yes No Yes No No Yes Yes
     

    Source
     

    题意:给你n个数,m次询问,每次询问给你三个数,问在给出的数里面存不存在任意取10个(不包含这三个数)的数的和==87。

    做法:利用bitset预处理,bitset是什么玩意?和set一样,都可以看作是集合,只不过里面的值只有0/1,这里面bitset定义为数组,ss[已经用的数字个数][凑出来的和],那么ss[j]|=ss[j-1]<<num[i];的意思就是在添加了第i个数的时候可以在原有的基础上改变。这样到最后就可以判断出[10][87]是否可达。

    #include <iostream>
    #include<cstdio>
    #include<bitset>
    #include<algorithm>
    using namespace std;
    bitset<90>ss[20];
    int n,num[100];
    bool dp[55][55][55];
    void make(int x,int y,int z)
    {
        for(int i=0;i<=11;i++)ss[i].reset();
        ss[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--)
                ss[j]|=ss[j-1]<<num[i];
        }
        if(ss[10][87]==1)dp[x][y][z]=1;
        else dp[x][y][z]=0;
    }
    int main()
    {
        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++)
                        make(i,j,k);
            int m;
            scanf("%d",&m);
            while(m--)
            {
                int xx[3];
                scanf("%d%d%d",&xx[0],&xx[1],&xx[2]);
                sort(xx,xx+3);
                if(dp[xx[0]][xx[1]][xx[2]])puts("Yes");
                else puts("No");
            }
        }
        return 0;
    }
    


    展开全文
  • /*首先考虑如何计算一个点的可能凑出的值,这就是一个01可行性背包问题那么再拓展到一段...每个位置(区间)维护一个bitset,每次加入a都进行一次01背包 用线段树来维护区间的bitset,表示一段区间能组成的值 但是...
  • } 接着了解一下bitset优化01背包 对应题型:对于这类 种类不同,又有数量的 >=1 由于 种类间的数量之和 是 1e5 状态也是 1e5 普通的 01 背包肯定超时。 bitset优化呢,采取了 二进制的特性,同种类型的...
  • bitset优化:biset优化01背包学习博客 #include #include #include #include #include #include #include #include #include #include using namespace std; typedef long long ll; const int N =1e6+10; bitsetf...
  • 有一种操作是用bitset优化01背包 假设有5件物品,重量为  1 1 2 3 3 那么他们组合能得到的重量种类为 1 2 3 4 5 6 7 9 10 用bitset表示就是 1101111111 那么对于每一个物品,我们做左移操作...
  • 然后就发现01背包肯定T了啊,那我就bitset优化一下吧.第一次写bitset,没办法 xjb搞搞吧,然后就一直T. 这里bitset优化的时间复杂度大致是n*k/64 或者/32 吧 这个不太清楚. 如果这个是个搜索我肯定就想到了这种剪枝......
  • void dfs(int l,int r,int rt,bitset<maxn>y) { bitset<maxn>t=y; for(int i=0;i[rt].size();i++) t|=(t[rt][i]); int mid=(l+r)>>1; if(l==r)ans|=t; else dfs(l,mid,rt,t),dfs(mid+1,r,rt|1,t); } int main...
  • 思路: 背包来做,由于n 比较小,所以我可以预先处理出所有的情况,然后用bitset 搞一搞。 另附一句 bitset 真的强。  推荐题集:  大神大神 代码: #include using namespace std; const int N =...
  • 那么,我们似乎可以维护一下这个数中有哪几个数被选择了,于是我们只用知道被选择的数的个数,就可以知道答案了,于是,可以用一个bitset来进行维护,我们想知道1~N中,有多少个平方和,用一个背包的思想。...
  • #include <bitset> #include using namespace std; const int M=55; int a[M],n; bool check[M][M][M];//打表 //超时 int dp[M][11][100];//dp[i][j][k]前i个数的取j个之和和能否达到k j bitset<100> b[12];//b[i]...
  • bitset优化背包问题

    2018-05-23 00:13:13
    https://blog.csdn.net/HowardEmily/article/details/77340566 留坑待填
  • bitset优化背包

    2018-01-28 16:41:00
    回忆下一题,是零一背包,主要的做法就是凑出最接近sum/2的价值,然后发现现在的背包的容量是2000*2000,物品数量是2000,那么如果你用正常的 数组背包的做法的话,8*10^9的复杂度是会超时的,代码如下: int n;...
  • bitset优化背包...

    千次阅读 2016-07-19 15:24:57
    题目: ...这题可以转化成背包。 L,R什么的可以无视,因为替换他们不用时间。 将竖直方向和左右方向分成两个数组。 分别求出他们的和sum1,sum2。将其转化成背包,看成sum1的背包最多可以选多少个(长度和*2),
  • 1.题目链接。题目大意,给出n个数据,从中删除1-3个,在剩下...然后想背包,想到了三维dp[i][j][k]:前i个数据里面选j个和是k。这样似乎有门,最后看了一下询问,发现询问是远比答案的数量大的,所以先预处理好,询...
  • 口胡一种别的解法: 三重退背包,g1[j]k]表示不选x的选了j件物品,体积为k的方案数,g[0][0] = 1 , g1[j][k]=dp[j][k]-g1[j-1][k-a[x...如果直接枚举删掉的数,然后用可行性二维01背包做 复杂度是O(50*50*50)*O(n*...
  • 示例1 输入 3 3 2000 1000 3000 3 2000 3000 1600 ...题意:给你n个数,问你是否能选出若干个数使得数字的和为3600的倍数(至少选一个)。...所以我简单学习了一下bitset优化背包的做法。bitset上面每个数...
  • 好像可以直接上01背包DP。但是会TLE。 其实记录的只是每个体积的状态的奇偶,所以方程可以写成dp[i]=dp[i]⊕dp[i−x]dp[i]=dp[i]⊕dp[i−x]dp[i]=dp[i]\oplus dp[i-x],然后发现每一个点都是异或上前面一定距离的数...
  • Eighty seven HDU - 5890 题目大意:给出n个数,删掉任意三个数之后问剩下的数取10个加起来能否等于87。 q次询问,每次给三个数,表示删掉的数...考虑的用bitset优化 //dp[i][j]=dp[i-1][j]; //dp[i][j]=dp[i...
  • 每次问删掉第i,j,k个数后,是否存在一种选10个数和为87的方案,只需要输出 ’Yes’ 或者 ’No’ 解题报告: 直接可行性背包,然后bitset优化一下就可以了。 AC代码: #include #include #include #include #include ...
  • 优化到 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] ...
  • 这里写目录标题C++标准库bitset对象的初始化及操作bitset上场 C++标准库bitset对象的初始化及操作 // bit当作数组,下标0对应的是最右边的元素 bitset<10> bit; bit[0]=1;//0000000001 cout<<bit&...
  • $bitset $ 优化: 这个是我最先想到的,因为这道题只牵扯到了能不能买,就是一个“是”和“否”的问题,也就是说这个背包并没有什么权值(只有“可以”和“不可以”)然后就是单纯的状态转移。而...
  • AtCoder C - Median Sum //bitset 01背包优化 C - Median Sum Time limit: 2sec /Memory limit: 512MB Score :700points Problem Statement You are givenNintegersA1,A2, ...,AN. Consider the sums ...
  • 题解就是这么暴力,点分治甚至就是个工具 因为最后答案的连通块一定必经某一个重心, 所以就用点分治统计每个重心能产生出来的答案 bitsetsum[i]表示必取i时的连通块哪些和是能凑出来的, 考虑到正常做背包的时候...
  • HDU 5313 bitset优化背包

    2015-08-17 14:02:00
    题目大意: 添加尽可能少的边,最后使图形成二分图 一开始将图区分成一个个联通...跟着题解说的bitset,学了一下,果然总共10000个点不到,那么只要用bitset上的某一位代表取到的值即可- -,好神奇。。这里用的...
  • bitset优化呢,原来是n*m,10*87的时间复杂度 在第二维的时候优化成了n*n,10 *10 具体bitset怎么实现的呢。。看代码看注释 #include #include #include #include #include #include #include #include #...

空空如也

空空如也

1 2 3 4 5 ... 20
收藏数 935
精华内容 374
关键字:

bitset优化01背包