精华内容
下载资源
问答
  • 二进制分割 用JavaScript编写的简单二进制拆分算法。
  • 【BZOJ1192】二进制拆分

    千次阅读 2019-06-06 13:29:28
    昨天刚听过Claris的二进制拆分背包,我试一下吧。 ?竟然过了??? 分析: 瞎猜一波原理吧。 用二进制拆分一定是可以表示出所有数字的,这个很好理解。 但是为什么二进制拆分是最好的呢? 为什么不...

    题目意思很简单,在这里

    题意:
    最少将n拆分成多少个数,可以凑出1到n的所有数字。

    做题前:
    这题是不是假题啊?
    我用1 2 3 4 5 …这样凑吧

    好像不太对啊。

    是dp吗
    我想想

    这状态怎么表示啊?

    昨天刚听过Claris的二进制拆分背包,我试一下吧。

    ?竟然过了???

    分析:
    瞎猜一波原理吧。
    用二进制拆分一定是可以表示出所有数字的,这个很好理解。
    但是为什么二进制拆分是最好的呢?
    为什么不是三进制拆分或者更高进制的拆分呢?
    举个例子吧

    三进制拆分
    1 3 9 27…
    这个根本凑不出1到n的所有数字,因为他们之间的差距实在是太大了。

    更高进制的拆分就更不行了。

    试着猜想,应该只有二进制拆分才可以保证左右的数字都可以被组合出来。

    遂做完。

    #include <bits/stdc++.h>
    #define sc(n) scanf("%d",&n)
    #define pt(n) printf("%d\n",n)
    #define rep(i,a,b) for(int i=a;i<=b;i++)
    #define vi vector<int>
    #define vl vector<long long>
    #define pb push_back
    using namespace std;
    int main()
    {
    	int m;
    	sc(m);
    	cout<<ceil(log2(m))<<endl;
    	return 0;
    }
    
    

    代码还没头文件长

    展开全文
  • 分析:判断dp[ V/2 ] ==V/2 即可,但过程如果用普通做法会超时,即多重背包当成01背包做效率很低,这时候要用二进制拆分优化,将复杂度变为 二进制拆分原理: 这里是指一个大数11101111 ,只要每一位上的1我们都...

    题意:有权值分别为1,2,3,4,5,6的大理石,每种都有若干块,能否把它们分成权值相等的2份。大理石的总数量不超过20000。(多重背包)

    分析:判断dp[ V/2 ] ==V/2 即可,但过程如果用普通做法会超时,即多重背包当成01背包做效率很低,这时候要用二进制拆分优化,将复杂度变为 image.png

    二进制拆分原理:image.png

    image.png

    这里是指一个大数11101111 ,只要每一位上的1我们都有一个数,就可以表示出来这个大数   也就是用1 2 4 8 (1 10 100 1000..)  可以表示出任意的数 ,那么任意一个数都可以经过处理变为2进制的数,为了方便每个二进制的数只有一个,这个处理可以看作把13 分为 1、2、4、6 (最后一个6是为了处理方便避免重复) 。

     

    二进制拆分:

    for(int i=1;i<=n;i++)
    {
        for(int j=1;j<=num[i];j<<=1)
        //二进制每一位枚举.
        //注意要从小到大拆分
        {
            num[i]-=j;//减去拆分出来的
            new_c[++tot]=j*c[i];//合成一个大的物品的体积
            new_w[tot]=j*w[i];//合成一个大的物品的价值
        }
        if(num[i])//判断是否会有余下的部分.
        //就好像我们某一件物品为13,显然拆成二进制为1,2,4.
        //我们余出来的部分为6,所以需要再来一份.
        {
            new_c[++tot]=num[i]*c[i];
            new_w[tot]=num[i]*w[i];
            num[i]=0;
        }
    }
    View Code

    Code:

    #include<cstdio>
    #include<cstring>
    #include<iostream>
    #include<algorithm>
    #define INF 0x3f3f3f3f
    using namespace std;
    
    const int maxn=120012;
    int n,V;
    int dp[maxn];
    int a[7];
    int v[maxn],w[maxn];
    int main(){
        int kase=1;
        while(scanf("%d %d %d %d %d %d",&a[1],&a[2],&a[3],&a[4],&a[5],&a[6])!=EOF){
            if(a[1]==0&&a[2]==0&&a[3]==0&&a[4]==0&&a[5]==0&&a[6]==0) break;
            memset(dp,0,sizeof(dp));
            printf("Collection #%d:\n",kase++);
            V=n=0;
            for(int i=1;i<=6;i++){
                V+=a[i]*i;
            }
            if(V&1){
                printf("Can't be divided.\n\n");
                continue;
            }
            else{            
                int tot=0;
                for(int i=1;i<=6;i++){
                    for(int j=1;j<=a[i];j<<=1){
                        a[i]-=j;
    //                    printf("a[i]=%d j=%d\n",a[i],j);
                        w[tot]=j*i;
                        v[tot++]=j*i;
                    }
                    if(a[i]!=0){
                        v[tot]=a[i]*i;
                        w[tot++]=a[i]*i;
                    }
                }
    //            printf("tot=%d\n",tot);
                for(int i=0;i<tot;i++){
                    for(int j=V/2;j>=w[i];j--){
                        dp[j]=max(dp[j],dp[j-w[i]]+v[i]);
                    }
                }
    //            for(int i=6;i>=1;i--){
    //                for(int k=v/2;k>=i;k--){
    //                    for(int j=1;j<=a[i];j++){
    //                        if(k-i*j>=0)
    //                            dp[k]=max(dp[k],dp[k-i*j]+i*j);
    //                        
    ////                        printf("dp[k]=%d\n",dp[k]);
    //                    }
    //                }
    //            }    
                if(dp[V/2]==V/2)
                    printf("Can be divided.\n\n");
                else
                    printf("Can't be divided.\n\n");
            }
        }
        return 0;
    }
    View Code

     

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

    展开全文
  • 01背包 - 二进制拆分

    2018-01-25 22:44:44
    二进制拆分原理:任何一个整数都可以转换成一个若干个2k" role="presentation" style="position: relative;">2k2k2^k数相加的形式(因为可以转化成二进制数)。 k个物品,我们可以选择的是取 0~e 件,代价和大小...

    二进制拆分原理:任何一个整数都可以转换成一个若干个2k2k数相加的形式(因为可以转化成二进制数)。

    k个物品,我们可以选择的是取 0~e 件,代价和大小分别是取的件数 p,p*Ti 和 p*Ci。假设我们取 p 件得到的就是最优解,当我们把 e 件物品{Ti,Ci}变成若干件{Ti,Ci},{2Ti,2Ci},{4Ti,4Ci},{8Ti,8Ci}……{2k2kTi,2k2kCi},{(e-2k2k)Ti,(e-2k2k)Ci},其中2k2k≤k且2k+12k+1>e。这若干件物品可以想象成把好几件物品 i 捆绑在一起,而且通过这若干件物品肯定能组合出和取 p 件物品 i 等价的情况。

    因为 p 也可以拆成若干2k2k数相加的形式,就是我们拆分出来的。很明显,每个2k2k数,拆出一个就够了。之后为什么多了一个不是2k2k的数呢?因为 k 不一定刚好被分完。如果ki=12i∑i=1k2i还小于 e 怎么办(比如 e=5)?这就是为什么我们把它们的差值作为一个新物品!这样使得总和正好为 e,同时可以真正组合出0 到 p 每个数字。

    此时每件捆绑后的物品最多只能取一次,所以物品 i 的复杂度应该是logk2×allvlog2k×allv(allv表示背包总空间,实际比这个小一些),N 件物品的复杂度为这个的 N 倍,原复杂度(假设都是 k 件)应为N×k×allvN×k×allv,显然时间已经被优化了。

    展开全文
  • 前言:一直以为背包中的二进制拆分很NB而且很难的样子,知道我今天学到了之后,发现??? 题目背景 《爱与愁的故事第四弹·plant》第一章。 题目描述 爱与愁大神后院里种了n棵樱花树,每棵都有美学值Ci。爱与愁大神...

    正解:二进制拆分

    前言:一直以为背包中的二进制拆分很NB而且很难的样子,知道我今天学到了之后,发现???

    题目背景
    《爱与愁的故事第四弹·plant》第一章。

    题目描述
    爱与愁大神后院里种了n棵樱花树,每棵都有美学值Ci。爱与愁大神在每天上学前都会来赏花。爱与愁大神可是生物学霸,他懂得如何欣赏樱花:一种樱花树看一遍过,一种樱花树最多看Ai遍,一种樱花树可以看无数遍。但是看每棵樱花树都有一定的时间Ti。爱与愁大神离去上学的时间只剩下一小会儿了。求解看哪几棵樱花树能使美学值最高且爱与愁大神能准时(或提早)去上学。

    输入格式
    共n+1行:

    第1行:三个数:现在时间Ts(几点:几分),去上学的时间Te(几点:几分),爱与愁大神院子里有几棵樱花树n。

    第2行~第n+1行:每行三个数:看完第i棵树的耗费时间Ti,第i棵树的美学值Ci,看第i棵树的次数Pi(Pi=0表示无数次,Pi是其他数字表示最多可看的次数Pi)。

    输出格式
    只有一个整数,表示最大美学值。

    输入输出样例
    输入 #1
    6:50 7:00 3
    2 1 0
    3 3 1
    4 5 4
    输出 #1
    11
    说明/提示
    100%数据:Te-Ts ≤ 1000,n ≤ 10000

    样例解释:赏第一棵樱花树一次,赏第三棵樱花树2次

    正解:二进制拆分

    • 我们很快就可以得到一个正常思路,每次动态规划到一种樱花,如果能看的次数为无限次,那么我们就用完全背包来对待,否则我们就用多重背包来对待

    预估得分:100pts
    实际得分:90pts
    最后一个数据1.03s

    考虑优化:加个快读(我唯一想出的优化

    预估得分:100pts
    实际得分:90pts
    最后一个数据1.05s
    比前面还慢,说好的超级无敌屌炸天快读呢梗出处

    二进制拆分

    做法:把每一个物品根据2的多少次方拆分,因为任何数都可以转化为二进制数
    核心思想:把每一个物品拆成很多个,分别计算价值和所需时间,再转化为01背包求解
    最后一点:完全背包可以把他的空间记为999999,不要太大,一般百万就足够了

    AC代码

    #include<cstdio>
    #include<algorithm>
    #define re register int
    using namespace std;
    int nx,ny,ex,ey,n,f[1010];
    int a[10005],b[10005],c[10005];
    int tp,co[1000005],v[1000005];//尽可能开大,不要把空间开爆了
    inline void pre() {
    	for(re i=1;i<=n;i++) {
    		int t=1;
    		while(c[i]) {
    			co[++tp]=t*a[i];
    			v[tp]=t*b[i];
    			c[i]-=t; t*=2;
    			if(c[i]<t) {//如果剩下的不能再拆,就直接放在一起
    				co[++tp]=a[i]*c[i];
    				v[tp]=b[i]*c[i];
    				break;
    			}
    		}
    	}
    }
    int main() {
    	scanf("%d:%d%d:%d%d",&nx,&ny,&ex,&ey,&n);
    	int t=(ex*60+ey)-(nx*60+ny);
    	for(re i=1;i<=n;i++) {
    		scanf("%d%d%d",&a[i],&b[i],&c[i]);
    		if(!c[i]) c[i]=999999;
    	}
    	pre();//二进制拆分
    	for(re i=1;i<=tp;i++) {//考虑每个拆出来的物品
    		for(re j=t;j>=co[i];j--)//01背包板子
    			f[j]=max(f[j],f[j-co[i]]+v[i]);
    	}
    	printf("%d",f[t]);
    	return 0;
    } 
    
    展开全文
  • 一个二进制拆分工具,可帮助进行反编译和修改项目 当前,仅支持.z64格式的N64 rom。 有关用法示例,请参见 Makefile setup目标使用包含配置文件的splat调用,您可以将其用作参考。 更多文档即将发布。 要求 可以...
  • 在多重背包的直接拆分法中,个数为$c[i]$的物体被拆成$c[i]$种不同的物体 这样就使得物体的种类增加了很多,使得算法效率很低。 上述方法把$c[i]$拆成$c[i]$个1,于是任意选择可以表示出...于是就有了二进制拆分法...
  • 多重背包二进制拆分【模板】

    千次阅读 2018-07-24 16:10:53
    把多重背包用二进制拆分,拆分后的能表示它所能表示的任意数字. 比如:7 = 1 + 2 + 4, 13 = 1 + 4 + 8; 然后把价值和空间对应也更新,更新后用01背包直接写就行,复杂度:n∗log(num)/log2n∗log(num)/log2n * ...
  • A.... ...Your friend recently gave you some ...我们发现最后的数列很类似于二进制拆分数列。 如果这个数二进制,从小到大(0bas)第i位是1,那么我们的答案就有i+1 【时间复杂度&&优化】 O(logn) */
  • 二进制拆分然后用一个数组单独存一下当前答案即可。 Code: #include <iostream> #include <cstdio> #include <cstring> #include <algorithm> #define N 10...
  • 于是就用二进制拆分把宝物拆分成几个宝物,以空间换时间,然后就变成了01背包。 代码 #include<iostream> #include<cstdio> using namespace std; int n,W,v[1000010],w[1000010],s[1000010],f[1000010]...
  • 题解:本题主要考查贪心+二进制拆分。 简要题意:给n个位运算(AND,OR,XOR)和m,要求从0—m中取一个数依次进行这n中操作,求最大值。 1.贪心+二进制拆分:因为二进制位运算每个位是独立的,所以我们就可以用一个...
  • 【多重背包】二进制拆分【模板】

    千次阅读 2018-08-09 16:48:26
    把多重背包用二进制拆分,拆分后的能表示它所能表示的任意数字.  比如:7 = 1 + 2 + 4, 13 = 1 + 4 + 8;  然后把价值和空间对应也更新,然后用01背包直接写就行,复杂度:n∗m∗log(num)n∗m∗log(num). #...
  • 【题解】Coins(二进制拆分+bitset) 【vj】 俗话说得好,bitset大法吼啊 这道题要不是他多组数据卡死了我复杂度算出来等于九千多万的选手我还不会想这种好办法233 考虑转移的实质是怎样的,就是对于一个\(dp\)数组表...
  • 题意:有n(n )枚硬币面值为A1...思路:不能暴力,对于Ai * Ci >= m的情况,直接完全背包。剩下的二进制拆分Ci,将Ci 拆分为 20+21+…+2k-1+(Ci-2k+1+1)。对于每一项进行零一背包即可。 http://acm.hdu.edu.cn/showproble
  • 多重背包的二进制拆分难度题意数据范围思路核心代码【普通多重背包】核心代码【二进制拆分】 宝物筛选 | 洛谷 P1776 难度 绿题绿题绿题 题意 一个 普通 的多重背包 物品数 NNN 背包容积 VVV 每个物品有重量 wiw_iwi...
  • 这篇文章主要证明一下多重背包的二进制拆分的可行性与正确性: 类似于二进制的原理:一定可以表达一系列连续的正数,下面用例子证明 把22进行二进制拆分: 成为1,2,4,8,7;由1,2,4,8可以组成1--15之间所有的数...
  • 二进制拆分,无话可说 题目描述 终于,破解了千年的难题。小FF找到了王室的宝物室,里面堆满了无数价值连城的宝物……这下小FF可发财了,嘎嘎。但是这里的宝物实在是太多了,小FF的采集车似乎装不下那么多宝物。看来...
  • 意识流的记一个结论就好了 将K二进制拆分什么的 不难想 注意特判0 安利:http://hzwer.com/5491.html #include #include #include using namespace std; typedef long long ll; inline char nc(){ static char ...
  • DP的二进制拆分优化

    2020-07-16 02:16:02
    经典例题:多重背包 ...输入: 第一行是整数 n 和 W,分别表示物品种数和背包的最大容量。 接下来 n 行,每行三个整数 vi​、wi​、mi​,分别表示第i个物品的价值、体积、数量。...根据二进制的计算原
  • 多重背包问题描述:   有NNN种物品,第iii种物品的体积是cic_ici​,价值是...  将第iii类物品的nin_ini​个物品拆分,得Σni\Sigma{n_i}Σni​个物品,即将原问题转换为了01背包问题,时间复杂度为O(V×Σn)O(...
  • 【多重背包二进制拆分法】ACM-ICPC 2018 焦作赛区网络预赛 K. Transport Ship https://nanti.jisuanke.com/t/31720 1. 题意 有n艘货船,第i艘穿可以装载V[i]重量装载物品数量必须是2C[i]−12^{C[i]}-12C[i]−1,要...
  • 这题可以用二进制拆分/单调队列优化(感觉二进制好写)。 所谓二进制优化,就是把1~c[i]拆分成20,21,...2t,c[i]−2t+1+120,21,...2t,c[i]−2t+1+1的组合。 这样物品总个数就变成了∑log(c[i])∑log(c[i]) 于是...
  • 什么是二进制拆分?  一个数n拆成小于它的所有二的次方的和(指数递增的)加上剩下一个数。   举个例子:13可以拆成 2^0 、 2^1 、 2^2、和 6(6是剩下的那个数),也就是拆分成 1 2 4 6,那么通过这4个数就可以表示...
  • 在这之前,我空间好像转过一个背包九讲,现在我就只对 01背包和多重背包有点印象了 先说下 01 背包,有n 种不同的物品,每个物品有两个属性 size 体积,value ...以后可以用二进制拆分来组成任意一个子数哟。
  • 文章目录题意题解 题目链接 题意 定义f(a,b)f(a,b)f(a,b)为定义域为正整数对,值域为正整数的任意函数,并且自变量相同的时候保证函数值相同. 给一个长度为nnn的序列aaa,一开始a[i]=ia[i]=ia[i]=i....

空空如也

空空如也

1 2 3 4 5 ... 20
收藏数 62,686
精华内容 25,074
关键字:

二进制拆分