精华内容
下载资源
问答
  • 最大连续子序列的

    2014-04-01 17:26:58
    求最大连续子序列的的方法很多,有的算法复杂度达到n的三方,而有的额题目可能超时,在这儿,我们用分治法来求该题,所谓分治法,就是将个大问题,不断的划分个小问题,用递归的方法来解题,算法如下: ...

           求最大连续子序列的和的方法很多,有的算法复杂度达到n的三次方,而有的额题目可能超时,在这儿,我们用分治法来求该题,所谓分治法,就是将一个大问题,不断的划分为一个小问题,用递归的方法来解题,算法如下:

          基本思路:

    将一个长为n个数的数组,划分为平分,得到两个数组,(1~n/2)和(n/2+1~n)两个数组,此时,有三种情况,第一,最长连续和在(1~n/2)中,第二,在(n/2+1~n)中,还有就是两边各有一部分。前两种情况就用递归的方法继续求解,最后的情况就分别从中间位置学学向两端查找,得到最大值,然后 相加就是在两部分的最大值,然后让该最大值和用递归求得的两个值比较,得到最大值,最后得到最大值。

    #include<iostream>
    using namespace std;
    int func(int *a,int n,int k);
    int main()
    {
    int a[200],i,n;
    cin>>n;
    for(i=1;i<=n;i++)
    cin>>a[i];
    cout<<func(a,n,1)<<endl;
    }
    int func(int *a,int n,int k)
    {
    int i,m=n,max=a[1];
    if(m==k)
    return max;           //m==n时,此时有两种情况,一是只有一个数,二是通过递归调用,使得m==n;返回的值就是最大连续和的值

    else
    {
    int max1=a[(m+k)/2],max2=a[(m+k)/2+1];
    int maxl=0;
    for(i=(m+k)/2;i>0;i--)                                      //从左端开始累加,此时是在求最大值分布在两端的情况,max1为左端的最大值,
    {
    maxl+=a[i];
    if(max1<maxl)
    max1=maxl;
    }
    maxl=0;
    for(i=(m+k)/2+1;i<=n;i++)                            //从右端开始累加,此时是在求最大值在分布在两端的情况,max2为右端的最大值
    {
    maxl+=a[i];
    if(max2<maxl)
    max2=maxl;
    }
    max=max1+max2;                                    //相加得到最大值
    int maxm,maxn;
    maxn=func(a,(m+k)/2,1);                            //递归调用
    maxm=func(a,n,(m+k)/2+1);                    //递归调用
    maxn=maxn>maxm?maxn:maxm;
    max=max>maxn?max:maxn;
    }
    }

    展开全文
  • 题意: 对于从1到N (1 <= N <= 39) 的连续整数集合,能划分成两个子集合,且保证每个集合的数字和是相等的。举个例子,如果N=3, ...分析:每个数字只用到一次,每种情况的存在数可以由之前的存...

    题意: 对于从1到N (1 <= N <= 39) 的连续整数集合,能划分成两个子集合,且保证每个集合的数字和是相等的。举个例子,如果N=3,

             对于{1,2,3}能划分成两个子集合,每个子集合的所有数字和是相等的:{3} 和 {1,2}

             给出一个 N 值,问最多能划分成多少种等值的集合。

    分析:每个数字只用到一次,每种情况的存在数可以由之前的存在的数来递推得到,01背包的变形。

    #include<stdio.h>
    #include<string.h>
    #define clr(x)memset(x,0,sizeof(x))
    long long f[50000];
    int main()
    {
        long long n,i,j,v;
        while(scanf("%lld",&n)!=EOF)
        {
            if(n==0)
            break;
            v=n*(n+1)/2;
            if(v%2==1)
            {
                printf("0\n");
                continue;
            }
            clr(f);
            f[0]=1;
            v/=2;
            for(i=1;i<=n;i++)
                for(j=v;j>=i;j--)
                    f[j]+=f[j-i];
            printf("%lld\n",f[v]/2);
        }
        return 0;
    }

     

    转载于:https://www.cnblogs.com/dream-wind/archive/2012/08/20/2648109.html

    展开全文
  • 题目大意是对给定的很多矩形,求出面积,重叠的部分只能算一次 可以对xy坐标进行离散化,然后对面积进行划分划分成四部分,左上,右上,左下,右下 与之前的线段式线段树不同的是,每次对宽高进行等分的时...

    题目大意是对给定的很多矩形,求出面积和,重叠的部分只能算一次

    可以对x和y坐标进行离散化,然后对面积进行划分,划分成四部分,左上,右上,左下,右下

    与之前的线段式线段树不同的是,每次对宽和高进行等分的时侯,xmid和ymid在各部分出现的时候不用+1,因为这里算的是面积,面积是连续的

    注意浮点数的判断大小

    对于x,y是否相等,只有在x+0.000001 > y && x - 0.000001 < y时成立

    对于x<y,只有在x+ 0.000001 < y时成立

    对于x<=y,只有在x-0.000001 <y时成立


    我的代码

    #include<stdio.h>
    
    struct Node
    {
    	int left;
    	int right;
    	int up;
    	int down;
    	double area;
    	int flag;
    }node[1000001];
    
    double x[201], y[201];
    int xnum, ynum;
    
    double area[101][4];
    
    int n;
    
    double Max(double a, double b)
    {
    	return a > b ? a : b;
    }
    
    double Min(double a, double b)
    {
    	return a < b ? a : b;
    }
    
    bool smaller(double a, double b)
    {
    	if(a - 0.000001 < b)
    		return 1;
    	return 0;
    }
    
    bool biger(double a, double b)
    {
    	if(a + 0.000001 > b)
    		return 1;
    	return 0;
    }
    
    int equal(double a, double b)
    {
    	if(a + 0.000001 >= b && a - 0.000001 <= b)
    		return 1;
    	return 0;
    }
    
    int sort(double *array, int& num)
    {
    	int i, j;
    	for(i = 1; i < num; i ++)
    	{
    		for(j = i + 1; j <= num; j ++)
    		{
    			if(equal(array[i], array[j]))
    			{
    				array[j] = array[num];
    				num --;
    				j --;
    			}
    		}
    	}
    
    	for(i = 1; i < num; i ++)
    		for(j = i + 1; j <= num; j ++)
    		{
    			if(array[i] > array[j])
    			{
    				array[i] += array[j];
    				array[j] = array[i] - array[j];
    				array[i] = array[i] - array[j];
    			}
    		}
    		return 0;
    }
    
    int build(int xleft, int xright, int yup, int ydown, int pre)
    {
    
    	node[pre].left = xleft;
    	node[pre].right = xright;
    	node[pre].up = yup;
    	node[pre].down = ydown;
    	node[pre].area = 0;
    	node[pre].flag = 0;
    
    	if((xleft + 1 == xright || xleft == xright) && (ydown + 1 == yup || ydown == yup))
    		return 1;
    
    	int xmid = (xleft + xright) / 2, ymid = (yup + ydown) / 2;
    	build(xleft, xmid, yup, ymid, pre * 4);
    	build(xmid, xright, yup, ymid, pre * 4 + 1);
    	build(xleft, xmid, ymid, ydown, pre * 4 + 2);
    	build(xmid, xright, ymid, ydown, pre * 4 + 3);
    	return 0;
    }
    
    int overlay(double l, double r, double u, double d, double l1, double r1, double u1, double d1, double *over)
    {
    	if(smaller(r, l1) || biger(l, r1) || smaller(u, d1) || biger(d, u1))
    	{
    		return 0;
    	}
    	over[0] = Max(l, l1);
    	over[1] = Min(r, r1);
    	over[2] = Min(u, u1);
    	over[3] = Max(d, d1);
    	if(smaller(over[1], over[0]))
    		return 0;
    	if(smaller(over[2], over[3]))
    		return 0;
    	return 1;
    }
    
    int insert(double l, double r, double u, double d, int pre)
    {
    	double over[4];
    	if(equal(l, x[node[pre].left]) && equal(r, x[node[pre].right]) && equal(u, y[node[pre].up]) && equal(d, y[node[pre].down]))
    	{
    		node[pre].area = (u - d) * (r - l);
    		node[pre].flag = 1;
    		return 0;
    	}
    	if(!node[pre * 4].flag && overlay(l, r, u, d, x[node[pre * 4].left], x[node[pre * 4].right], y[node[pre * 4]. up], y[node[pre * 4].down], over))
    	{
    		insert(over[0], over[1], over[2], over[3], pre * 4);
    	}
    	if(!node[pre * 4 + 1].flag && overlay(l, r, u, d, x[node[pre * 4 + 1].left], x[node[pre * 4 + 1].right], y[node[pre * 4 + 1]. up], y[node[pre * 4 + 1].down], over))
    	{
    		insert(over[0], over[1], over[2], over[3], pre * 4 + 1);
    	}
    	if(!node[pre * 4 + 2].flag && overlay(l, r, u, d, x[node[pre * 4 + 2].left], x[node[pre * 4 + 2].right], y[node[pre * 4 + 2]. up], y[node[pre * 4 + 2].down], over))
    	{
    		insert(over[0], over[1], over[2], over[3], pre * 4 + 2);
    	}
    	if(!node[pre * 4 + 3].flag && overlay(l, r, u, d, x[node[pre * 4 + 3].left], x[node[pre * 4 + 3].right], y[node[pre * 4 + 3]. up], y[node[pre * 4 + 3].down], over))
    	{
    		insert(over[0], over[1], over[2], over[3], pre * 4 + 3);
    	}
    
    	node[pre].area = node[pre * 4].area + node[pre * 4 + 1].area + node[pre * 4 + 2].area + node[pre * 4 + 3].area;
    	return 0;
    
    }
    
    int main()
    {
    	int i, ca = 0;
    	while(scanf("%d", &n) != EOF && n != 0)
    	{
    		xnum = 0;
    		ynum = 0;
    		for(i = 1; i <= n; i ++)
    		{
    			scanf("%lf%lf%lf%lf", &area[i][0], &area[i][1], &area[i][2], &area[i][3]);
    			x[++ xnum] = area[i][0];
    			x[++ xnum] = area[i][2];
    
    			y[++ ynum] = area[i][1];
    			y[++ ynum] = area[i][3];
    		}
    		sort(x, xnum);
    		sort(y, ynum);
    
    		build(1, xnum, ynum, 1, 1);
    		for(i = 1; i <= n; i ++)
    		{
    			insert(area[i][0], area[i][2], area[i][3], area[i][1], 1);
    		}
    		printf("Test case #%d\nTotal explored area: %.2lf\n\n", ++ ca, node[1].area);
    	}
    	return 0;
    }
    
    


    展开全文
  • 要求出长度为l~r的前k大连续,可以转化为k求第i大连续,这与划分树的作用有关  先把前缀预处理出来。连续和为 S(j)-S(i),固定i之后为 S(i+len)-S(i-1) (i为起点,len为长度,len∈[l,r]) 这里面...

    【题解】

    (划分树做法)

    要求出长度为l~r的前k大连续和,可以转化为k次求第i大连续和,这与划分树的作用有关 

    先把前缀和预处理出来。一段连续和为 S(j)-S(i),固定i之后为 S(i+len)-S(i-1) (i为起点,len为长度,len∈[l,r])
    这里面,若i一定,len就在固定区间内变动,连续和的k大值对应S(i+len)的k大值,问题就转化为"求给定区间的k大值",就可以用划分树了 
    但是起点有多个,而题目中"k次求第i大连续和"没办法真的快速做到一次求一个 
    可以先求出对于每个起点的区间内最大连续和来预备着,把它们存到堆里,每次询问时取出堆顶并放入这个起点对应的次大和即可 

    因此题目转化为:求 S(i+l-1)-s(i-1),S(i+l)-s(i-1),…,S(i+r-1)-s(i-1) (i∈[1,n-l+1])中前k大的值 
    Ⅰ首先,建一个大根堆。对于每个i,求出max{ S(i+l-1),S(i+l),…,S(i+r-1) }-s(i-1)加入堆中 
    Ⅱ然后,对于k次询问,每次取出堆顶,看这个堆顶是由哪个i得到的,再把这个i对应的{S(i+l-1),S(i+l),…,S(i+r-1)}-s(i-1)的次大值加入堆 

    时间复杂度:划分树预处理_O( n*log(n) ) +Ⅰ_O( n*log(n) ) +Ⅱ_O( k*log(n) )


    【代码】

    #include<stdio.h>
    #include<stdlib.h>
    typedef long long LL;
    struct node
    {
        int v[500005],num[500005];
    };
    node T[20];
    int s[500005]={0},p[500005]={0},heap[500005]={0},pos[500005]={0};
    int ph=0;
    int min(int a,int b)
    {
        if(a<b) return a;
        return b;
    }
    void jh(int* a,int* b)
    {
        int t=*a;
        *a=*b;
        *b=t;
    }
    void jh_heap(int a,int b)
    {
        jh(&heap[a],&heap[b]);
        jh(&pos[a],&pos[b]);
    }
    void kp(int low,int high)
    {
        int i=low,j=high,mid=s[(i+j)/2];
        while(i<j)
        {
            while(s[i]<mid) i++;
            while(s[j]>mid) j--;
            if(i<=j)
            {
                jh(&s[i],&s[j]);
                i++;
                j--;
            }
        }
        if(j>low) kp(low,j);
        if(i<high) kp(i,high);
    }
    void build(int left,int right,int deep)
    {
        int mid=(left+right)/2,ln=left,rn=mid+1,isame=mid-left+1,same=0,i;
        if(left==right) return;
        for(i=left;i<=right;i++)
            if(T[deep].v[i]<s[mid]) isame--;
        for(i=left;i<=right;i++)
        {
            if(i==left) T[deep].num[i]=0;
            else T[deep].num[i]=T[deep].num[i-1];
            if(T[deep].v[i]<s[mid])
            {
                T[deep+1].v[ln++]=T[deep].v[i];
                T[deep].num[i]++;
            }
            if(T[deep].v[i]>s[mid]) T[deep+1].v[rn++]=T[deep].v[i];
            if(T[deep].v[i]==s[mid])
            {
                same++;
                if(isame>=same)
                {
                    T[deep+1].v[ln++]=T[deep].v[i];
                    T[deep].num[i]++;
                }
                else T[deep+1].v[rn++]=T[deep].v[i];
            }
        }
        build(left,mid,deep+1);
        build(mid+1,right,deep+1);
    }
    int cx(int x,int y,int k,int left,int right,int deep)
    {
        int mid=(left+right)/2,before,have,b,h,tx,ty,fk=y-x+1+1-k;
        if(left==right) return T[deep].v[left];
        if(x==left)
        {
            before=0;
            have=T[deep].num[y];
        }
        else
        {
            before=T[deep].num[x-1];
            have=T[deep].num[y]-T[deep].num[x-1];
        }
        if(fk<=have)//左 
        {
            tx=left+before;
            ty=left+before+have-1;
            k=ty-tx+1+1-fk;
            return cx(tx,ty,k,left,mid,deep+1);
        }
        else//右 
        {
            b=x-1-left-before+1;
            h=y-x+1-have;
            tx=mid+1+b;
            ty=mid+1+b+h-1;
            k=ty-tx+1+1-(fk-have);
            return cx(tx,ty,k,mid+1,right,deep+1);
        }
    }
    void tj(int x,int t)
    {
        int i;
        heap[++ph]=t;
        pos[ph]=x;
        for(i=ph;i!=1;i/=2)
        {
            if(heap[i]>heap[i/2]) jh_heap(i,i/2);
            else return;
        }
    }
    void sc()
    {
        int i=1;
        jh_heap(1,ph);
        ph--;
        while(i*2<=ph)
        {
            i*=2;
            if(i+1<=ph&&heap[i+1]>heap[i]) i++;
            if(heap[i]>heap[i/2]) jh_heap(i,i/2);
            else return;
        }
    }
    int main()
    {
        LL ans=0;
        int n,k,l,r,i,x;
        scanf("%d%d%d%d",&n,&k,&l,&r);
        for(i=1;i<=n;i++)
        {
            scanf("%d",&s[i]);
            s[i]+=s[i-1];
            T[0].v[i]=s[i];
        }
        T[0].v[0]=0;
        kp(1,n);
        build(1,n,0);
        for(i=1;i<=n-l+1;i++)
        {
            p[i]=1;
            tj(i,cx(i+l-1,min(n,i+r-1),1,1,n,0)-T[0].v[i-1]);
        }
        for(i=1;i<=k;i++)
        {
            ans+=(LL)heap[1];
            x=pos[1];
            sc();
            p[x]++;
            if((x+l-1)+p[x]-1<=min(n,x+r-1)) tj(x,cx(x+l-1,min(n,x+r-1),p[x],1,n,0)-T[0].v[x-1]);
        }
        printf("%lld",ans);
        return 0;
    }


    展开全文
  • 依据煤层裂隙分布规律瓦斯运移特征,推导了瓦斯渗流量与瓦斯压力关系...运用改进的非连续变形分析(DDA)方法模拟了鹤壁煤电股份有限公司十煤矿煤巷掘进时一次煤与瓦斯突出过程。模拟结果与实际案例数据统计结论一致。
  • InnoDB将数据划分为若干页,以页作为磁盘内存之间交互的基本单位,InnoDB中页的大小一般为16kb(可以修改)。也就是说一般情况下,一次最少从磁盘中读取16kb的内容到内存中。一次最少把16kb的内容刷新到磁盘中。页...
  • 在微机内,若插入块D/A转换卡,然后编制段小程序,如连续进行加一运算到一定值,然后连续进行减 运算回到原值,在反复运行该程序,则微机输出的数字量经过d/a转换为小阶梯式模拟量波形。 在正弦波周期...
  • 晓萌希望将1到N的连续整数组成的集合划分成两个子集合,且保证每个集合的数字和是相等。例如,对于N=3,对应的集合{1,2,3}能被划分成{3} {1,2}两个子集合. 这两个子集合中元素分别的和是相等的。 对于N=3,我们...
  • HTTP请求走私(

    2020-09-10 18:13:30
    keep-Alive: 在进行一次HTTP请求后,不关闭TCP连接,后面的请求重复使用这个TCP。 Pipeline: http1.0中是发个请求服务器回应一个请求再才发送下一个请求,在http1.1中可以连续发送不用等回应,然后服务器遵循先进先...
  • 文件都是储存在硬盘上,硬盘的最小存储单位叫做"扇区"...所以读取的时候都是一次连续读取8个扇区,即一次性读取一个"块"(block)。这种由多个扇区组成的"块",是文件存取的最小单位。"块"(block)的大小,最...
  • 缺点:效率问题 空间问题 会产生大量的不连续的内存碎片 分配较大对象时,无法找到足够的连续内存而不得不提前触发另一次垃圾 收集动作 2.复制算法(Copying) 原理:可用内存按容量划分为大小相等的两块,每次只使用一...
  • 分区式内存管理:将整个程序一次性加载到内存的一个区域中。会产生区外无法利用的外部碎片。 分页式内存管理:将内存分成固定大小的页,一般是4k,将程序按页分切割。分配给程序的页可以物理上不连续,不会产生外部...
  • 散度最近要进行全国第七人口普查啦,为了全社会的繁荣稳定,我们决定研究一下水流很相似的人流的性质。假如有个无限长的大厅,我们将它划分为很多方形区域。每个区域都有一些人,人可能会到处移动:如下图现在...
  • 并查集也叫不相交集合,可以描述把个集合通过等价关系(满足自反性、对称性传递性的关系)划分为若干个等价类这过程。并查集只有两个操作findunion: find返回个元素所属的等价类,union合并两个元素所在的...
  • IPV6下DHCPICMP

    2021-03-07 10:43:23
    IE 笔记 IPv6: 一、为什么需要IPv6? a、IPv4地址空间不足(2的32次方) b、IPv6地址空间很大,近乎无限。...b、地址中包含连续全为0的组,可以用双冒号代替,仅使用一次 例: 2001:0000:0000:0001:0000:
  • 碎片太多,假如程序运行时,需要分配较大对象时,无法找到连续内存,而不得不提前触发另一次垃圾回收 B:复制算法:运行高效。它将可用内存容量划分为大小相等的两块,每次只使用其中的一块。 当这一块用完之后...
  • 栈是进程虚拟内存模型中的连续内存区域,不同的操作系统对于虚拟内存的划分策略存在一定的差异,但是不论是什么操作系统都会流出大块内存区用作栈空间(大多数情况下是堆栈共享)。 x86架构下,栈是向着低...
  • 从页式管理开始,到之后的段式管理,都与之前的分区管理不同,最大的区别就在于个是分区管理是连续存储,二这两种方式可以非连续。 实现原理 首先是必要概念: 物理块:将物理存储空间划分为大小相等的若干存储块...
  • 永久区(PGS) JVM内存结构分为 堆,方法区,栈,程序计数器,本地方法区。 这些都是逻辑内存区域划分,实际上不同的 虚拟机的实现方式是不同的,我们常用...当第一次使用类的静态方法(包括构造方法)时,JVM会将对应的
  • 一、垃圾收集算法 1、标记—清除算法 算法分为“标记”“清除”两个阶段:首先标记出所有需要回收的对象... 当这一块的内存用完了,就将还存活着的对象复制到另外一块上面,然后再把已使用过的内存空间一次清理掉
  • IP地址规划的重要性

    千次阅读 2012-04-07 13:59:16
    原则就是:尽量使逻辑上同类的地址规划成连续的地址,并且起始地址最好是2的幂。这样做的原因在于可以方便的划分子网。考虑下面的拓扑:有天,需要在该局域网增加台加密网关,所有到达外部网络
  • 一个序列为不无聊序列,则必须满足划分任意长度的连续子序列(包括其本身),其中至少存在一个元素仅仅出现一次,即至少有一个元素不重复。 例子: 123321 ——无聊序列,子序列33中没有独特元素。 12321 ——不无聊...
  • CF578D. LCS Again

    2019-10-01 13:41:07
    n<=100000个字符的小写字母串,问用前m<...如挖掉a,那么就剩aa|bb|c|dd,可以发现一个连续相同段挖谁都一样所以一个连续相同段只算一次,然后补一个。可以发现在自己的相同段中不能丢一个原来一样的,而...
  • kmeans聚类算法

    千次阅读 2013-05-30 23:56:23
    kmeans聚类算法的步骤: •1 设置初始类别中心类别数;...•5 如果连续的类别划分结果不变则停止算法;否则循环2~5 ; 数据样本:可以随机产生个100行2列的数据样本, 代码实现: 实验结果:
  • 题解: 根据题目要求,最多进行两次买卖股票,而且手中不能有2只股票,就是不能连续两次买入操作。 所以,两次交易必须是分布在2各区间内,也就是动作为:买入卖出...一次划分的最大利益为:Profit[i] = MaxProfit...
  • 1、分代收集算法 由对象存活周期将内存划分为:...分区则是将堆空间划分连续几个不同小区间,每一个小区间独立回收,可以控制一次回收多少个小区间,方便控制 GC 产生的停顿时间。 具体的实现是G1垃圾收集器。 ...
  • 模拟出栈顺序,将出栈划分为几次,原来栈只要入栈一次就打破了连续出栈的顺序,让现在对比栈匹配出栈元素如果匹配到,就判断出栈顺序(需要判断的出栈顺序)当前对比栈顺序是否相同, 如果相同清理对比栈元素,...
  • poj 3017 题解

    2019-04-29 21:53:09
    一次写poj的题目的题解呢QωQ\color{pink}Q\omega QQωQ。 题意简述 给定一个序列,一个常数mmm,要你把这个序列分成几个连续的部分,每一个部分的都不能超过mmm,然后让你最小化每一段的最小值的。 数据...
  • 垃圾收集算法

    2020-09-22 11:39:43
    当一块内存用完了,就将还存活着的对象复制到另一块内存上面,然后再把已使用过的内存空间一次清理掉。 缺点:将内存分为原来的一半,代价太大。 但实际上的虚拟机并不是按1:1的比例划分空间的,而是将内存划分为...

空空如也

空空如也

1 2 3 4 5 ... 10
收藏数 187
精华内容 74
关键字:

一次划分和连续划分