程式師世界 >> 編程語言 >> C語言 >> C++ >> C++入門知識 >> POJ 3695 Rectangles 1w詢問求20個矩陣面積並容斥

POJ 3695 Rectangles 1w詢問求20個矩陣面積並容斥

編輯：C++入門知識

POJ 3695 Rectangles 1w詢問求20個矩陣面積並容斥

題目大意是給出若干個矩形(n <= 20) 然後m個詢問(m <= 100000)

每個詢問會給出一些矩形的編號，問這些矩形的面積並有多大

談到矩形並，也許第一反應都是線段樹

但是此題有一個特點，就是n非常小，m卻非常大

用線段樹很有可能會不行

於是換個思路，n很小，我們可以把所有的可能組合情況都考慮到，然後呢預處理出來，這樣詢問時就是O(1)的查詢了

但是1<<20顯然是遠大於100000的

也就是說我們沒必要把所有情況都考慮到。

只需要考慮這m個詢問中的情況就可以了

於是我們先把詢問中情況都讀進來，用二進制存起來。

然後就是DFS，根據容斥原理

一個矩形的面積-二個矩形相交的面積+三個矩形相交的面積。。。。。。就這樣

所以DFS中可以有兩種分支，一種是拿這個矩形，另一種是不拿

#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include
const int inf = 1e8;
const double eps = 1e-8;
const double pi = acos(-1.0);
template   
inline bool rd(T &ret) {  
    char c; int sgn;  
    if(c=getchar(),c==EOF) return 0;  
    while(c!='-'&&(c<'0'||c>'9')) c=getchar();  
    sgn=(c=='-')?-1:1;  
    ret=(c=='-')?0:(c-'0');  
    while(c=getchar(),c>='0'&&c<='9') ret=ret*10+(c-'0');  
    ret*=sgn;  
    return 1;  
} 
template  
inline void pt(T x) { 
    if (x <0) { putchar('-');x = -x; }  
    if(x>9) pt(x/10);  
    putchar(x%10+'0');  
}
using namespace std;
typedef long long ll;
typedef pair pii;
    
int n, m; 
struct node{
	int x1, x2, y1, y2;
	int area(){return abs(x1-x2)*abs(y1-y2);}
}a[30];
int ask[100005];
int st[1<<21];
void dfs(int xa, int ya, int xb, int yb, int deep, int flag, int sta){
	if(xa >= xb || ya >= yb)return;
	if(deep == n)
	{
		if(sta){
			for(int i = 1; i <= m; i++)
				if((ask[i]|sta) == ask[i])
					st[ask[i]] += flag*(xb-xa)*(yb-ya);
		}
		return ;
	}
	dfs(xa, ya, xb, yb, deep+1, flag, sta);
	dfs(max(xa, a[deep+1].x1), max(ya, a[deep+1].y1), min(xb, a[deep+1].x2), min(yb, a[deep+1].y2), deep+1, -flag, sta|(1<>n>>m, n+m){
    	printf(Case %d:
, Cas++);
		for(int i = 1; i <= n; i++){
			rd(a[i].x1); rd(a[i].y1); rd(a[i].x2); rd(a[i].y2);
		}
		for(int i = 1, siz, num; i <= m; i++){
			ask[i] = 0;
			rd(siz);
			while(siz-->0){rd(num); ask[i]|=1<<(num-1);}
		}
		memset(st, 0, sizeof st);
		dfs(0,0,inf,inf, 0,-1,0);
		for(int i = 1; i <= m; i++)
			printf(Query %d: %d
, i, st[ask[i]]);
		puts();
	}
    return 0;
}