[POJ3695]Rectangles（容斥原理 + 离线 + 玄学）

题目传送门：3695 -- Rectangles (poj.org)

题目大意 / Problem

给定若干个矩形（N <= 20），求某几个矩形的面积之和。

分析 / Analyse

因为矩形比较少，可以状态压缩来表示矩形是否被选中，先计算出所有的可能情况的交集，再用容斥原理来计算最终的面积（并集）。容斥原理中如果元素个数为奇数个就加，偶数个就减，这个可以通过状态中1的个数来判定。

复杂度O(2 ^ N * M)，玄学过题。

代码一dfs版本 / Code 1

#include <iostream>
#include <cstring>
#include <bitset>
using namespace std;
const int maxn = 2e6 + 5, inf = 1e9;
int n_area[maxn], q[maxn], ans[maxn];
int N, M, kase = 0;

struct Rect
{
	int x1, y1, x2, y2;
}r[25];

int lowbit(int x)
{
	return x & -x;
}

int count1(int x)
{
	int res = 0;
	while(x)res ++, x -= lowbit(x);
	return res;
}

void dfs(int x1, int y1, int x2, int y2,int dep,int status)
{
	if(x1 >= x2 || y1 >= y2)return;
	if(dep == N)
	{
		if(status)
		{
			int sign = (count1(status) & 1) ? 1 : -1;
			for(int i = 1;i <= M; ++ i)
			{
				if((q[i] | status) == q[i])
				{
					ans[i] += sign * (x2 - x1) * (y2 - y1);
				}
			}
		}
		return;
	}
	
	dfs(x1, y1, x2, y2, dep + 1, status);
	dfs(max(x1, r[dep].x1), max(y1, r[dep].y1), min(x2, r[dep].x2), min(y2, r[dep].y2), dep + 1, status | (1 << dep));
	
}

void solve()
{
	cout << "Case " << ++kase << ":\n";
	for(int i = 0;i < N; ++ i)cin >> r[i].x1 >> r[i].y1 >> r[i].x2 >> r[i].y2;
	
	memset(q, 0, sizeof q);
	memset(ans, 0, sizeof ans);
	
	for(int i = 1;i <= M; ++ i)
	{
		int k;cin >> k;
		while(k --)
		{
			int x;cin >> x;
			q[i] |= (1 << (x - 1));
		}
	}
	dfs(-inf ,-inf ,inf ,inf, 0, 0);
	for(int i = 1;i <= M; ++ i)cout << "Query " << i << ": " << ans[i] << '\n';
	cout << '\n';
}

signed main()
{
	ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
	while(cin >> N >> M && (N || M) )solve();
	return 0;
}

代码二循环版本 / Code 2

#include <iostream>
#include <cstring>
using namespace std;
const int maxn = 2e6 + 5, inf = 1e9;
int n_area[maxn], u_area[maxn], q[maxn], ans[maxn];
int N, M, kase = 0;

struct Rect
{
	int x1, y1, x2, y2;
}r[25];

int lowbit(int x)
{
	return x & -x;
}

int count1(int x)
{
	int res = 0;
	while(x)res ++, x -= lowbit(x);
	return res;
}

void solve()
{
	cout << "Case " << ++kase << ":\n";
	for(int i = 0;i < N; ++ i)cin >> r[i].x1 >> r[i].y1 >> r[i].x2 >> r[i].y2;
	
	for(int i = 0;i < (1 << N); ++ i)
	{
		int x1 = -inf, y1 = -inf, x2 = inf, y2 = inf; 
		for(int j = 0;j < N && (x2 - x1) > 0 && (y2 - y1) > 0; ++ j)
		{
			if(i >> j & 1)//i中有j这一项 
			{
				x1 = max(x1, r[j].x1);
				y1 = max(y1, r[j].y1);
				x2 = min(x2, r[j].x2);
				y2 = min(y2, r[j].y2);
			}
		}
		n_area[i] = max(0, x2 - x1) * max(0, y2 - y1);
	}
	memset(q, 0, sizeof q);
	memset(ans, 0, sizeof ans);
	for(int i = 1;i <= M; ++ i)
	{
		int k;cin >> k;
		while(k --)
		{
			int x;cin >> x;
			q[i] |= (1 << (x - 1));
		}
	}
	
	for(int i = 1;i < (1 << N); ++ i)
	{
		if(n_area[i] == 0)continue;
		
		int sign = (count1(i) & 1) ? 1 : -1;
		for(int j = 1;j <= M; ++ j)
			if((q[j] | i) == q[j])ans[j] += sign * n_area[i];
	}
	
	for(int i = 1;i <= M; ++ i)cout << "Query " << i << ": " << ans[i] << '\n';
	cout << '\n';
}

signed main()
{
	ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
	while(cin >> N >> M && (N || M) )solve();
	return 0;
}