题目传送门: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; }
Comments NOTHING