首页 > 代码库 > POJ 3695

POJ 3695

可以用容斥原理来求。求两个矩形的并的时候可以使用条件

x1=max(p.x1,q.x1);
y1=max(p.y1,q.y1);
x2=min(p.x2,q.x2);
y2=min(p.y2,q.y2);

if(x2>x1&&y2>y1)可以并,否则,并不了。

 

。。。

开始时,我对每个询问都做一次容斥原理,TLE。可以这样改进一下。对每个询问,用了哪些矩形可以用一个二进制的数来存起来。对所有的矩形做一次DFS,然后判断当一个组合内的矩形均属于某个询问内(可用二进制或计算),则按照容斥原理公式计算即可。

 

#include <iostream>#include <cstdio>#include <cstring>#include <algorithm>#define M 100005using namespace std;struct Rectangle{	int x1,y1,x2,y2;};Rectangle r[25];int status[1250000];int choice[M];int ans;bool WhetherRec(int x1,int y1,int x2,int y2){	if(x2>x1&&y2>y1)	return true;	return false;}void dfs(int i,int num,Rectangle p,int al,int sta,int ml){		if(i>=al){		if(num==0){			for(int k=1;k<=ml;k++)			status[choice[k]]=0;		}		else if(num&1){			for(int k=1;k<=ml;k++){				if((sta|choice[k])<=choice[k])				status[choice[k]]+=(p.x2-p.x1)*(p.y2-p.y1);			}		}		else{			for(int k=1;k<=ml;k++){				if((sta|choice[k])<=choice[k])				status[choice[k]]-=(p.x2-p.x1)*(p.y2-p.y1);			}		}		return ;	}		dfs(i+1,num,p,al,sta,ml);	Rectangle tmp;	int x1=max(p.x1,r[i].x1);	int y1=max(p.y1,r[i].y1);	int x2=min(p.x2,r[i].x2);	int y2=min(p.y2,r[i].y2);	if(WhetherRec(x1,y1,x2,y2)){		tmp.x1=x1; tmp.x2=x2;		tmp.y1=y1; tmp.y2=y2;		dfs(i+1,num+1,tmp,al,sta|(1<<(i)),ml);	}}void work(int n,int m){	Rectangle p;	p.x1=p.y1=0; p.x2=p.y2=1000;	dfs(0,0,p,n,0,m);}int main(){	int kase=0;	int n,m,k,tmp,sta;	while(scanf("%d%d",&n,&m),n||m){		kase++;		for(int i=0;i<n;i++)		scanf("%d%d%d%d",&r[i].x1,&r[i].y1,&r[i].x2,&r[i].y2);		for(int i=1;i<=m;i++){			scanf("%d",&k);			sta=0;			for(int p=0;p<k;p++){				scanf("%d",&tmp);				sta=(sta|(1<<(tmp-1)));			}			choice[i]=sta;		}		work(n,m);		printf("Case %d:\n",kase);		for(int e=1;e<=m;e++){			printf("Query %d: %d\n",e,status[choice[e]]);		}		printf("\n");	}	return 0;}

  

POJ 3695