今天来整理一下最近做的一类题目,其基本思想就是二分答案,我们来说几道例题

\(No.1\;\; AGC006D\;Median\;Pyramid\;Hard\)

link

这个题我们发现如果我们按题意模拟,我们发现我们无论如何都想不出如何在不改变原序列的情况下,使得能在正确的复杂度内得到答案,那么我们就要想优化。

我们考虑二分答案,设当前所枚举的答案为 \(mid\),最后顶上的答案为 \(res\),那么我们就将所有大于等于 \(mid\) 的数的值置为 \(1\),将小于 \(mid\) 的数置为 \(0\),并且我们发现只要有相同的两个数字相邻,那么它上面的数字还是他,那么我们就可以在 \(O(n)\) 的复杂度内递推了。

我们还需要特判没有出现相邻两个数相同的情况,那么此时的答案即为我们两边的数字。

如果 \(res=1\) 那么说明最终答案大于等于 \(mid\),我们令 \(l=mid+1\),并记录此时的最优答案,反之,令 \(r=mid-1\)

\(code\)

#include<bits/stdc++.h>
using namespace std;
const int N=2e5+10;
int a[N];
int n,T;
bool check(int x){
    for(int i=0;i<n-1;i++){
        if((a[n-i]<x&&a[n-i-1]<x)||(a[n+i]<x&&a[n+i+1]<x))return 0;
        if((a[n-i]>=x&&a[n-i-1]>=x)||(a[n+i]>=x&&a[n+i+1]>=x))return 1;
    }
    return a[1]>=x;
}
void work(){
    scanf("%d",&n);
    for(int i=1;i<=2*n-1;i++)scanf("%d",&a[i]);
    int l=1,r=2*n-1,res=0;
    while(l<=r){
        int mid=(l+r)>>1;
        if(check(mid))res=mid,l=mid+1;
        else r=mid-1;
    }
    printf("%d\n",res);
}
int main(){work();return 0;}

\(No.2\;\; CF484E\;Sign\;on\;Fence\)

link

这是一道数据结构题,当然也用到了这种思路。我们发现对于一个区间中的长度为 \(k\) 的子区间的最小值的最大值,我们考虑进行二分。

我们设当前所枚举的答案为 \(mid\),那么我们将大于等于 \(mid\) 的数视作 \(1\),小于 \(mid\) 的数视作 \(0\),我们的目的就是找出这个区间中是否有一个长度大于等于 \(k\) 的连续的 \(1\),如果有,那么答案就大于等于 \(mid\),我们令 \(l=mid+1\),并记录最优答案;反之,我们令 \(r=mid-1\)。这个是可以用线段树维护的。

当然,因为我们的每一个 \(mid\) 所对应的线段树不相同,所以我们考虑使用主席树来做。

\(code\)

#include<bits/stdc++.h>
#define lson(rt) (tree[rt].ls)
#define rson(rt) (tree[rt].rs)
using namespace std;
const int N=2e5+10;
int n,q,a[N],id[N],lsh[N],cnt,len,root[N];
bool cmp(int x,int y){return a[x]<a[y];}
struct President_Tree{
    struct Seg{
        int ls,rs,pre,suf,len,length;
        Seg(){ls=0,rs=0,pre=0,suf=0,len=0,length=0;}
    }tree[N*50];
    int tot;
    inline friend Seg operator + (Seg a,Seg b){
        Seg c;
        c.length=a.length+b.length;
        c.len=max(a.len,max(b.len,a.suf+b.pre));
        c.pre=((a.pre==a.length)?a.len+b.pre:a.pre);
        c.suf=((b.suf==b.length)?a.suf+b.len:b.suf);
        return c;    
    }
    void pushup(int rt){
        int lls=lson(rt),rrs=rson(rt);
        tree[rt]=tree[lson(rt)]+tree[rson(rt)];
        lson(rt)=lls,rson(rt)=rrs;
    }
    int build(int rt,int l,int r){
        int k=++tot;
        tree[k]=tree[rt];
        if(l==r){
            tree[k].pre=tree[k].suf=tree[k].len=0;
            tree[k].length=1;
            return k;
        }
        int mid=(l+r)>>1;
        lson(k)=build(lson(rt),l,mid);
        rson(k)=build(rson(rt),mid+1,r);
        pushup(k);
        return k;
    }
    int update(int rt,int l,int r,int pos,int val){
        int k=++tot;
        tree[k]=tree[rt];
        if(l==r){
            tree[k].pre=tree[k].suf=tree[k].len=val;
            tree[k].length=1;
            return k;
        }
        int mid=(l+r)>>1;
        if(pos<=mid)lson(k)=update(lson(rt),l,mid,pos,val);
        else rson(k)=update(rson(rt),mid+1,r,pos,val);
        pushup(k);
        return k;
    }
    Seg ask(int rt,int l,int r,int L,int R){
        if(l<=L&&R<=r)return tree[rt];
        int mid=(L+R)>>1;
        Seg res1,res2;
        if(l<=mid)res1=ask(lson(rt),l,r,L,mid);
        if(r>mid)res2=ask(rson(rt),l,r,mid+1,R);
        return res1+res2;
    }
    bool check(int l,int r,int k,int val){
        Seg tmp;
        tmp=ask(root[val],l,r,1,n);
        return tmp.len>=k;
    }
    int getans(int l,int r,int k){
        int L=1,R=len,ans=0;
        while(L<=R){
            int mid=(L+R)>>1;
            if(check(l,r,k,mid))L=mid+1,ans=mid;
            else R=mid-1;
        }
        return lsh[ans];
    }
}T;
int main(){
    scanf("%d",&n);
    for(int i=1;i<=n;i++)scanf("%d",&a[i]),lsh[++cnt]=a[i],id[i]=i;
    sort(id+1,id+1+n,cmp);
    sort(lsh+1,lsh+1+cnt);
    len=unique(lsh+1,lsh+1+cnt)-lsh-1;
    int r=n+1;
    root[len+1]=T.build(root[len+1],1,n);
    for(int i=len;i>=1;i--){
        root[i]=root[i+1];
        while(r-1>=1&&a[id[r-1]]==lsh[i]){
            r--;
            root[i]=T.update(root[i],1,n,id[r],1);
        }
    }
    scanf("%d",&q);
    for(int i=1;i<=q;i++){
        int s1=0,s2=0,s3=0;
        scanf("%d%d%d",&s1,&s2,&s3);
        printf("%d\n",T.getans(s1,s2,s3));
    }
    return 0;
}

\(No.3\;\; HEOI2016\; 排序\)

link

这个题让人一看就想打暴力,并且因为我们发现当我们按他所说的操作进行时,最坏复杂度还是为 \(O(mg(n))\) 的(其中 \(g(n)\) 为你所用的排序方式,好像最好可以做到 \(O(n)\)),那么我们就要想优化。

我们考虑二分答案,我们设当前所枚举的答案为 \(mid\),那么我们将大于等于 \(mid\) 的数视作 \(1\),将小于 \(mid\) 的视作 \(0\),我们就发现排序变成了 \(0,1\) 变换。

举个例子,我们假设当前要排序的区间为 \([l,r]\),设当前 \([l,r]\)\(1\) 的数量为 \(cnt\),那么假如我们降序排序,就是将 \([l,l+cnt-1]\) 区间内的数置为 \(1\),将 \([l+cnt,r]\) 区间内的数置为 \(0\) 即可;同理,升序也是一样的。我们发现这种转化是对的,我们最终查 \(q\) 这个位置,如果此时这个位置为 \(1\),那么我们最终的答案就大于等于 \(mid\),我们就令 \(l=mid+1\),并更新最优答案,反之,令 \(r=mid-1\)

那么我们就可以通过二分答案和线段树在 \(O(nlog^n)\) 的复杂度内解决这道题了。

当然,如果 \(cnt=0\)\(cnt=n\) 时可能会出现我们更改的区间的 \(l>r\) 的情况,我们判断一下就可以了。

\(code\)

#include<bits/stdc++.h>
using namespace std;
const int N=2e5+10;
int n,m,a[N],b[N],q;
struct Ask{int opt,l,r;}ask[N];
struct Segment_Tree{
	#define lson (rt << 1)
	#define rson (rt << 1 | 1)
	struct Seg{int sum,lazy;}tree[N<<2];
	void pushup(int rt){tree[rt].sum=tree[lson].sum+tree[rson].sum;}
	void add(int rt,int val,int l,int r){tree[rt].sum=(r-l+1)*val,tree[rt].lazy=val;}
	void pushdown(int rt,int l,int r){if(tree[rt].lazy!=-1){int mid=(l+r)>>1;add(lson,tree[rt].lazy,l,mid),add(rson,tree[rt].lazy,mid+1,r);tree[rt].lazy=-1;}}
	void build(int rt,int l,int r){
		tree[rt].lazy=-1;
		if(l==r){tree[rt].sum=a[l];return ;}
		int mid=(l+r)>>1;
		build(lson,l,mid);
		build(rson,mid+1,r);
		pushup(rt);
	}
	void update(int rt,int l,int r,int L,int R,int val){
		if(l>r)return ;
		if(l<=L&&R<=r){add(rt,val,L,R);return ;}
		int mid=(L+R)>>1;
		pushdown(rt,L,R);
		if(l<=mid)update(lson,l,r,L,mid,val);
		if(r>mid)update(rson,l,r,mid+1,R,val);
		pushup(rt);
	}
	int ask(int rt,int l,int r,int L,int R){
		if(l<=L&&R<=r)return tree[rt].sum;
		int mid=(L+R)>>1;
		pushdown(rt,L,R);
		int ans=0;
		if(l<=mid)ans+=ask(lson,l,r,L,mid);
		if(r>mid)ans+=ask(rson,l,r,mid+1,R);
		return ans;
	}
}T;
bool check(int val){
	for(int i=1;i<=n;i++){
		if(b[i]<val)a[i]=0;
		else a[i]=1;
	}
	T.build(1,1,n);
	for(int i=1;i<=m;i++){
		int O=ask[i].opt,L=ask[i].l,R=ask[i].r;
		int cnt=T.ask(1,L,R,1,n);
		if(O==1){
			T.update(1,L,L+cnt-1,1,n,1);
			T.update(1,L+cnt,R,1,n,0);
		}
		else {
			T.update(1,R-cnt+1,R,1,n,1);
			T.update(1,L,R-cnt,1,n,0);
		}
	}
	if(T.ask(1,q,q,1,n))return true;
	return false;
}
int main(){
	scanf("%d%d",&n,&m);
	for(int i=1;i<=n;i++)scanf("%d",&b[i]);
	for(int i=1;i<=m;i++)scanf("%d%d%d",&ask[i].opt,&ask[i].l,&ask[i].r);
	scanf("%d",&q);
	int l=1,r=n,res=0;
	while(l<=r){
		int mid=(l+r)>>1;
		if(check(mid))l=mid+1,res=mid;
		else r=mid-1;
	}
	printf("%d\n",res);
	return 0;
}

原文地址:http://www.cnblogs.com/hxqasd/p/16863178.html

1. 本站所有资源来源于用户上传和网络,如有侵权请邮件联系站长! 2. 分享目的仅供大家学习和交流,请务用于商业用途! 3. 如果你也有好源码或者教程,可以到用户中心发布,分享有积分奖励和额外收入! 4. 本站提供的源码、模板、插件等等其他资源,都不包含技术服务请大家谅解! 5. 如有链接无法下载、失效或广告,请联系管理员处理! 6. 本站资源售价只是赞助,收取费用仅维持本站的日常运营所需! 7. 如遇到加密压缩包,默认解压密码为"gltf",如遇到无法解压的请联系管理员! 8. 因为资源和程序源码均为可复制品,所以不支持任何理由的退款兑现,请斟酌后支付下载 声明:如果标题没有注明"已测试"或者"测试可用"等字样的资源源码均未经过站长测试.特别注意没有标注的源码不保证任何可用性