首页 > 代码库 > 【BZOJ2253】[2010 Beijing wc]纸箱堆叠 cdq分治

【BZOJ2253】[2010 Beijing wc]纸箱堆叠 cdq分治

2024-09-15 12:31:15   220人阅读

【BZOJ2253】[2010 Beijing wc]纸箱堆叠

Description

P 工厂是一个生产纸箱的工厂。纸箱生产线在人工输入三个参数 n p a , , 之后，即可自动化生产三边边长为

(a mod P,a^2 mod p,a^3 mod P)
(a^4 mod p,a^5 mod p,a^6 mod P)
....
(a^(3n-2) mod p,a^(3n-1) mod p,a^(3n) mod p)的n个纸箱。在运输这些纸箱时，为了节约空间，必须将它们嵌套堆叠起来。一个纸箱可以嵌套堆叠进另一个纸箱当且仅当它的最短边、次短边和最长边长度分别严格小于另一个纸箱的最短边、次短边和最长边长度。这里不考虑任何旋转后在对角线方向的嵌套堆叠。 你的任务是找出这n个纸箱中数量最多的一个子集，使得它们两两之间都可嵌套堆叠起来。

Input

输入文件的第一行三个整数，分别代表 a,p,n  

Output

输出文件仅包含一个整数，代表数量最多的可嵌套堆叠起来的纸箱的个数。

Sample Input

10 17 4

Sample Output

2
【样例说明】
生产出的纸箱的三边长为(10, 15, 14), (4, 6, 9) , (5, 16, 7), (2, 3, 13)。其中只有
(4, 6, 9)可堆叠进(5, 16, 7)，故答案为 2。
2<=P<=2000000000,1<=a<=p-1,a^k mod p<>0,ap<=2000000000,1<=N<=50000

题解：先把每个纸箱的边长都算出来，然后这题就变成了求二维LIS

先按x排序，然后用cdq分治，在处理区间[l,r]的时候，一定要先处理[l,mid]，再处理[l,r]内部，最后[mid+1,r]，处理[l,r]内部的具体方法如下：

先将[l,mid]和[mid+1,r]分别按y排序，然后用两个指针去扫，将左边的f[i]加入树状数组，再用树状数组里的f值更新右边的f[i]，注意一定要满足左边的x,y都比右边的小才能加入树状数组，最后再按x排回来

#include <cstdio>#include <cstring>#include <iostream>#include <algorithm>#define pc (B=(B*A)%P)using namespace std;const int maxn=50010;typedef long long ll;ll A,P,B;int n,nm,ans;int x[maxn],y[maxn],z[maxn],p[maxn],q[maxn],tr[maxn],f[maxn];struct NUM{	int v,org;}num[maxn];bool cmp(NUM a,NUM b){	return a.v<b.v;}bool cmpx(int a,int b){	if(x[a]==x[b]&&y[a]==y[b])	return z[a]<z[b];	if(x[a]==x[b])	return y[a]<y[b];	return x[a]<x[b];}bool cmpy(int a,int b){	if(x[a]==x[b]&&y[a]==y[b])	return z[a]<z[b];	if(y[a]==y[b])	return x[a]<x[b];	return y[a]<y[b];}void updata(int a,int v){	for(int i=a;i<=nm;i+=i&-i)	tr[i]=max(tr[i],v);}void clr(int a){	for(int i=a;i<=nm;i+=i&-i)	tr[i]=0;}int query(int a){	if(!a)	return 0;	int i,ret=0;	for(i=a;i;i-=i&-i)	ret=max(ret,tr[i]);	return ret;}void dfs(int l,int r){	if(l==r)	return ;	int mid=l+r>>1,h1=l,h2=mid+1,i;	dfs(l,mid);	sort(p+l,p+mid+1,cmpy);	sort(p+mid+1,p+r+1,cmpy);	for(i=l;i<=r;i++)	{		if(h1<=mid&&(h2>r||(y[p[h1]]<y[p[h2]]&&x[p[h1]]<x[p[h2]])))	updata(z[p[h1]],f[p[h1]]),h1++;		else	f[p[h2]]=max(f[p[h2]],query(z[p[h2]]-1)+1),h2++;	}	for(i=l;i<=mid;i++)	clr(z[p[i]]);	sort(p+l+1,p+r+1,cmpx);	dfs(mid+1,r);}int main(){	scanf("%lld%lld%d",&A,&P,&n);	B=1;	int i;	for(i=1;i<=n;i++)	{		x[i]=pc,y[i]=pc,z[i]=pc;		if(x[i]<y[i])	swap(x[i],y[i]);		if(x[i]<z[i])	swap(x[i],z[i]);		if(y[i]<z[i])	swap(y[i],z[i]);		num[i].v=z[i],num[i].org=p[i]=i,f[i]=1;	}	sort(num+1,num+n+1,cmp);	for(num[0].v=-1,i=1;i<=n;i++)	{		if(num[i].v>num[i-1].v)	nm++;		z[num[i].org]=nm;	}	sort(p+1,p+n+1,cmpx);	dfs(1,n);	for(i=1;i<=n;i++)	ans=max(ans,f[i]);	printf("%d",ans);	return 0;}
 

【BZOJ2253】[2010 Beijing wc]纸箱堆叠 cdq分治


联系
我们