c/c++语言开发共享BZOJ2244 拦截导弹

此题最早看到是在我还什么都不会的去年的暑期集训,是V8讲的DP专题,我当时还跑去问这概率怎么做。这道题要求的是二维最长不上升子序列,加上位置一维就成了三维偏序问题,也就是套用CDQ分治,对位置排序,然后对一维分治,对剩下的一维树状数组,类似的问题用树状数组套平衡树也能解决,但似乎常数很大。然后这题的 …

 

此题最早看到是在我还什么都不会的去年的暑期集训,是v8讲的dp专题,我当时还跑去问这概率怎么做。这道题要求的是二维最长不上升子序列,加上位置一维就成了三维偏序问题,也就是套用cdq分治,对位置排序,然后对一维分治,对剩下的一维树状数组,类似的问题用树状数组套平衡树也能解决,但似乎常数很大。然后这题的第一个关键就是在做cdq的时候先做cdq(l,mid)的区间,然后去计算左边对右边的影响,最后去计算cdq(mid+1,r),昨晚看别人博客中说这是显然的,当时我就懵逼了,于是这题今天上课看了很久。发现的确要这么做的,因为其实你是在维护第三维树状数组的时候去做了这个dp的过程,当计算以该点为结尾的最长不上升子序列时,你当然应该先做左区间,然后就可以去更新一下相对右边这些点的值,然后就再去做cdq的右区间。具体是分别维护区间的最长不上升子序列的长度,以及出现的次数。做法是这样的,首先对左右两边分别按照第二维从小到大排序,将左边的所有的第二维大于右边的点全部加入树状数组,更新第三维,要注意更新和查询的方向正好是反过来的,因为你要查的是大于右边某个值的最长不上升子序列的长度,然后更新一下dp数组,也就是代码中的f[0]数组。然后再把整个序列反过来做一遍cdq,求以某个点为开始的最长不上升子序列。

加一个学习的链接:%ignore_a_1%s://www.cnblogs.com/liu-runda/p/6416195.html  

 

 

#include<bits/stdc++.h> #define ll long double #define pb push_back #define _mp make_pair const int maxn=1e5+7; const int mod=1e9+7; using namespace std; int n; int h[2][maxn],v[2][maxn]; int iq[maxn],hq[maxn],vq[maxn]; int f[2][maxn]; ll g[2][maxn]; int max[maxn]; ll cnt[maxn]; void add1(int x,int w,ll cnt) { 	while(x>0) 	{ 		if(max[x]<w) 		{ 			max[x]=w;cnt[x]=cnt; 		} 		else if(max[x]==w)cnt[x]+=cnt; 		x-=x&-x; 	} } void add2(int x,int w,ll cnt) { 	while(x<maxn) 	{ 		if(max[x]<w) 		{ 			max[x]=w;cnt[x]=cnt; 		} 		else if(max[x]==w)cnt[x]+=cnt; 		x+=x&-x; 	} } int query1(int x) { 	int ans=0; 	while(x<maxn) 	{ 		if(max[x]>ans)ans=max[x]; 		x+=x&-x; 	} 	return ans; } int query2(int x) { 	int ans=0; 	while(x>0) 	{ 		if(max[x]>ans)ans=max[x]; 		x-=x&-x; 	} 	return ans; } ll query_cnt(int x,int val) { 	ll ans=0; 	while(x<maxn) 	{ 		if(max[x]==val)ans+=cnt[x]; 		x+=x&-x; 	} 	return ans; } ll query_cnt2(int x,int val) { 	ll ans=0; 	while(x>0) 	{ 		if(max[x]==val)ans+=cnt[x]; 		x-=x&-x; 	} 	return ans; } bool cmp1(const int& a,const int& b) { 	return h[0][a]<h[0][b]; } bool cmp2(const int& a,const int& b) { 	return v[0][a]<v[0][b]; } bool cmp3(const int& a,const int& b) { 	return h[1][a]<h[1][b]; } void del1(int x) { 	while(x>0) 	{ 		max[x]=cnt[x]=0; 		x-=x&-x; 	} } void del2(int x) { 	while(x<maxn) 	{ 		max[x]=cnt[x]=0; 		x+=x&-x; 	} } void cdq1(int l,int r) { 	if(l==r)return; 	int mid=(l+r)>>1; 	cdq1(l,mid); 	for(int i=l;i<=r;i++)iq[i]=i; 	sort(iq+l,iq+mid+1,cmp1); 	sort(iq+mid+1,iq+r+1,cmp1); 	int pp=mid; 	for(int i=r;i>mid;i--) 	{ 		while(pp>=l&&h[0][iq[pp]]>=h[0][iq[i]]) 		{ 			add1(v[0][iq[pp]],f[0][iq[pp]],g[0][iq[pp]]); 			pp--; 		} 		int tmp=query1(v[0][iq[i]]); 		if(tmp+1>f[0][iq[i]]) 		{ 			f[0][iq[i]]=tmp+1;g[0][iq[i]]=query_cnt(v[0][iq[i]],tmp); 		} 		else if(tmp+1==f[0][iq[i]]) 		{ 			g[0][iq[i]]+=query_cnt(v[0][iq[i]],tmp); 		} 	} 	for(int i=mid;i>pp;i--) 	{ 		del1(v[0][iq[i]]); 	} 	cdq1(mid+1,r); } void cdq2(int l,int r) { 	if(l==r)return; 	int mid=(l+r)>>1; 	cdq2(l,mid); 	for(int i=l;i<=r;i++)iq[i]=i; 	sort(iq+l,iq+mid+1,cmp3); 	sort(iq+mid+1,iq+r+1,cmp3); 	int pp=l; 	for(int i=mid+1;i<=r;i++) 	{ 		while(pp<=mid&&h[1][iq[pp]]<=h[1][iq[i]]) 		{ 			add2(v[1][iq[pp]],f[1][iq[pp]],g[1][iq[pp]]); 			pp++; 		} 		int tmp=query2(v[1][iq[i]]); 		if(tmp+1>f[1][iq[i]]) 		{ 			f[1][iq[i]]=tmp+1;g[1][iq[i]]=query_cnt2(v[1][iq[i]],tmp); 		} 		else if(tmp+1==f[1][iq[i]]) 		{ 			g[1][iq[i]]+=query_cnt2(v[1][iq[i]],tmp); 		} 	} 	for(int i=l;i<pp;i++) 	{ 		del2(v[1][iq[i]]); 	} 	cdq2(mid+1,r); } int main() {	 	scanf("%d",&n); 	for(int i=1;i<=n;i++) 	{ 		scanf("%d%d",&h[0][i],&v[0][i]); 		iq[i]=i; 	} //	cout<<222<<endl; 	sort(iq+1,iq+1+n,cmp1); 	int tot=0,las=-1; 	for(int i=1;i<=n;i++) 	{ 		if(las!=h[0][iq[i]]) 		{ 			las=h[0][iq[i]]; 			++tot; 		} 		h[0][iq[i]]=tot; 	} 	tot=0;las=-1; 	for(int i=1;i<=n;i++) iq[i]=i; 	sort(iq+1,iq+1+n,cmp2); 	for(int i=1;i<=n;i++) 	{ 		if(las!=v[0][iq[i]]) 		{ 			las=v[0][iq[i]]; 			++tot; 		}v[0][iq[i]]=tot; 	} 	for(int i=1;i<=n;i++) 	{ 		h[1][i]=h[0][n+1-i]; 		v[1][i]=v[0][n+1-i]; 	} 	for(int i=1;i<=n;i++) 	{ 		iq[i]=i; 		f[0][i]=f[1][i]=g[0][i]=g[1][i]=1; 	} //	cout<<222<<endl; 	cdq1(1,n);cdq2(1,n); //	cout<<222<<endl; 	int ans=0; 	for(int i=1;i<=n;i++) 	{ 		if(f[0][i]>ans)ans=f[0][i]; 	} 	printf("%dn",ans); 	ll sum=0; 	for(int i=1;i<=n;i++) 	{ 		if(f[0][i]==ans)sum+=g[0][i]; 	} 	//cout<<sum<<endl; 	for(int i=1;i<=n;i++) 	{ 	//	cout<<g[0][i]<<" "<<g[1][n-i+1]<<endl; 		if(f[0][i]+f[1][n-i+1]!=ans+1)printf("%.8f ",0.0); 		else printf("%.8f ",double(g[0][i]*g[1][n-i+1]/(sum))); 		//cout<<endl; 	//	cout<<222<<endl; 	} //	} //	for(int i=1;i<=n;i++)	cout<<g[0][i]<<" "<<g[1][n-i+1]<<endl; 	 } 

  

本文来自网络收集,不代表计算机技术网立场,如涉及侵权请点击右边联系管理员删除。

如若转载,请注明出处:https://www.ctvol.com/c-cdevelopment/607906.html

(0)
上一篇 2021年5月14日
下一篇 2021年5月14日

精彩推荐