ErikTse Runtime

  • 首页 / Home
  • | 算法学习 / Algorithm
    • 所有 / All
    • 简单 / Easy
    • 中等 / Medium
    • 困难 / Hard
  • | 技术分享 / Technology
    • 所有 / All
    • 网络技术 / NetWork
    • 资源共享 / Resource
    • 项目实践 / Event
Keep Going.
温故而知新.
  1. 首页
  2. 算法学习
  3. 中等
  4. 正文

[POJ3695]Rectangles(容斥原理 + 离线 + 玄学)

2022年10月3日 164点热度 0人点赞 0条评论

题目传送门: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;
}
本作品采用 知识共享署名-非商业性使用 4.0 国际许可协议 进行许可
标签: C++ poj 容斥原理 矩形面积 算法竞赛
最后更新:2022年10月3日

Eriktse

19岁,性别未知,ACM-ICPC现役选手,ICPC亚洲区域赛银牌选手,CCPC某省赛铜牌蒟蒻,武汉某院校计算机科学与技术专业本科在读。

点赞
< 上一篇
下一篇 >

文章评论

razz evil exclaim smile redface biggrin eek confused idea lol mad twisted rolleyes wink cool arrow neutral cry mrgreen drooling persevering
取消回复

订阅本站
Loading
文章目录
  • 题目大意 / Problem
  • 分析 / Analyse
  • 代码一dfs版本 / Code 1
  • 代码二循环版本 / Code 2

COPYRIGHT © 2022 ErikTse Runtime. ALL RIGHTS RESERVED.

Theme Kratos Made By Seaton Jiang

赣ICP备2022001555号-1

赣公网安备 36092402000057号