当前位置：网站首页>第46届ICPC亚洲区域赛（昆明） B Blocks（容斥+子集和DP+期望DP）

第46届ICPC亚洲区域赛（昆明） B Blocks（容斥+子集和DP+期望DP）

2022-04-23 02:41:00 【JXNU_SONG】

B Blocks

https://ac.nowcoder.com/acm/contest/32708/B

我们首先对每个矩形进行二进制状压，状态 i i i 的每一位表示一个矩形，此位置为 1 1 1 表示此矩形已经选过，否则没选。

那么我们设 f [ i ] f[i] f[i] 表示当前状态为 i i i ，我们还需要花费多少步（期望），才可以把整个大矩形 W H WH WH 填满。那么 f [ 0 ] f[0] f[0] 就是我们要求的答案。

我们此时分两种情况求解：

（1）状态 i i i 已经将大矩形 W H WH WH 填满，那么我们有：
f [ i ] = 0 f[i]=0 f[i]=0
（2）状态 i i i 尚未将大矩形 W H WH WH 填满，那么我们此时就考虑下一步可能的选择，显然我们此时有 n n n 种选择。那么 n n n 种选择也可以分为两种情况：

①若我们选择了一个矩形 j j j 且 j j j 是状态 i i i 种已经选择过的矩形（即 ( i > > j & 1 = 1 ) (i>>j\&1=1) (i>>j&1=1) ），那么之后的期望步数仍是 f [ i ] f[i] f[i] 。

②若选择的矩形 j j j 并未存在于 i i i 中（即 ( i > > j & 1 = 0 ) (i>>j\&1=0) (i>>j&1=0) ），那么在选择 j j j 之后的期望步数即为 f [ i ⊕ ( 1 < < j ) ] f[i\oplus (1<<j)] f[i⊕(1<<j)] 。

那么我们这里设：

c n t = 状 态 i 中 已 经 选 择 了 的 矩 形 的 个 数 cnt=状态i中已经选择了的矩形的个数 cnt=状态i中已经选择了的矩形的个数

c = ∑ i > > j & 1 = 0 f [ i ⊕ ( 1 < < j ) ] c=\sum\limits_{i>>j\&1=0}f[i\oplus (1<<j)] c=i>>j&1=0∑​f[i⊕(1<<j)]

我们则可以得到方程（其中的 1 1 1 为到达下一个状态一定要选择的一步，后续两个分式即分别对应情况①和情况②）：
f [ i ] = 1 + c n t × f [ i ] n + c n f[i]=1+\frac{cnt\times f[i]}{n}+\frac{c}{n} f[i]=1+ncnt×f[i]​+nc​
整理后即有：
f [ i ] = n + c n − c n t f[i]=\frac{n+c}{n-cnt} f[i]=n−cntn+c​

那么我们可以发现，倒序枚举 i i i 即可递推出所有 f [ i ] f[i] f[i] ，直至得到答案 f [ 0 ] f[0] f[0] 。

那么现在还有个大问题就是如何得知状态 i i i 中的矩形是否能覆盖全 W H WH WH ，这里我们把每个面积为 1 1 1 的小矩形看成一个元素，那么给出的 n n n 个矩形即可看成 n n n 个集合，那么现在我们其实就是要求若干个集合的并集集合大小，那么我们可以用容斥枚举其子集的交集大小去求得并集集合的大小，子集的交集大小实则就是若干矩形的面积交，这里我们维护四个边界即可求得。这样做的时间复杂度为 O ( 3 N ) O(3^N) O(3N) ，当然我们也可以通过 S O S D P SOSDP SOSDP 将时间复杂度优化到优化到 O ( 2 N N ) O(2^NN) O(2NN) 。

c o d e 1 code1 code1 （未优化，直接枚举子集，代码中 a r e a [ i ] area[i] area[i] 代表状态 i i i 的面积交， d p [ i ] dp[i] dp[i] 代表状态 i i i 的面积并）：

#include <bits/stdc++.h>

using namespace std;

typedef long long ll;

const int N = 12;
const ll mod = 998244353;

ll ksm(ll base, ll n) {
    
    ll ans = 1;
    while(n) {
    
        if (n & 1ll) ans = ans * base % mod;
        base = base * base % mod;
        n >>= 1ll;
    }
    return ans;
}

int n;
int x[N], y[N], xx[N], yy[N], W, H;
ll dp[1 << N], area[1 << N], f[1 << N], inv[N];

int main() {
    
#ifndef ONLINE_JUDGE
    freopen("in.txt", "r", stdin);
    freopen("out.txt", "w", stdout);
#endif
    for (int i = 1; i <= 10; ++i) inv[i] = ksm(i, mod - 2);
    int T; scanf("%d", &T);
    while(T--) {
    
        scanf("%d%d%d", &n, &W, &H);
        for (int i = 0; i < n; ++i) {
    
            scanf("%d%d%d%d", &x[i], &y[i], &xx[i], &yy[i]);
        }
        for (int i = 1; i < (1 << n); ++i) {
    
            int xl = 0, yl = 0, xr = W, yr = H;
            for (int j = 0; j < n; ++j) {
    
                if (i >> j & 1) {
    
                    xl = max(xl, x[j]);
                    xr = min(xr, xx[j]);
                    yl = max(yl, y[j]);
                    yr = min(yr, yy[j]);
                }
            }
            area[i] = 1ll * max(0, (xr - xl)) * max(0, (yr - yl));
        }
        for (int i = 1; i < (1 << n); ++i) {
    
            dp[i] = 0;
            for (int s = i; s; s = (s - 1) & i) {
    
                dp[i] += area[s] * (__builtin_parity(s) ? 1 : -1);
            }
        }
        ll SS = W * H;
        if (dp[(1 << n) - 1] != SS) {
    
            puts("-1");
            continue;
        }
        for (int i = (1 << n) - 1; i >= 0; --i) {
    
            f[i] = 0;
            if (dp[i] == SS) continue;
            ll csum = 0;
            for (int j = 0; j < n; ++j) {
    
                if (!(i >> j & 1)) {
    
                    csum = (csum + f[i ^ (1 << j)]) % mod;
                }
            }
            f[i] = (n + csum) * inv[n - __builtin_popcount(i)] % mod;
        }
        printf("%lld\n", f[0]);
    }
}

c o d e 2 code2 code2（ S O S D P SOSDP SOSDP优化）：

#include <bits/stdc++.h>

using namespace std;

typedef long long ll;

const int N = 12;
const ll mod = 998244353;

ll ksm(ll base, ll n) {
    
    ll ans = 1;
    while(n) {
    
        if (n & 1ll) ans = ans * base % mod;
        base = base * base % mod;
        n >>= 1ll;
    }
    return ans;
}

int n;
int x[N], y[N], xx[N], yy[N], W, H;
ll dp[1 << N], area[1 << N], f[1 << N], inv[N];

int main() {
    
#ifndef ONLINE_JUDGE
    freopen("in.txt", "r", stdin);
    freopen("out.txt", "w", stdout);
#endif
    for (int i = 1; i <= 10; ++i) inv[i] = ksm(i, mod - 2);
    int T; scanf("%d", &T);
    while(T--) {
    
        scanf("%d%d%d", &n, &W, &H);
        for (int i = 0; i < n; ++i) {
    
            scanf("%d%d%d%d", &x[i], &y[i], &xx[i], &yy[i]);
        }
        for (int i = 1; i < (1 << n); ++i) {
    
            int xl = 0, yl = 0, xr = W, yr = H;
            for (int j = 0; j < n; ++j) {
    
                if (i >> j & 1) {
    
                    xl = max(xl, x[j]);
                    xr = min(xr, xx[j]);
                    yl = max(yl, y[j]);
                    yr = min(yr, yy[j]);
                }
            }
            area[i] = 1ll * max(0, (xr - xl)) * max(0, (yr - yl));
        }

        for (int j = 0; j < (1 << n); ++j) {
    
            dp[j] = area[j] * (__builtin_parity(j) ? 1 : -1);
        }
        for (int i = 0; i < n; ++i) {
    
            for (int j = 0; j < (1 << n); ++j) {
    
                if (j >> i & 1) {
    
                    dp[j] += dp[j ^ (1 << i)];
                }
            }
        }
        ll SS = W * H;
        if (dp[(1 << n) - 1] != SS) {
    
            puts("-1");
            continue;
        }
        for (int i = (1 << n) - 1; i >= 0; --i) {
    
            f[i] = 0;
            if (dp[i] == SS) continue;
            ll csum = 0;
            for (int j = 0; j < n; ++j) {
    
                if (!(i >> j & 1)) {
    
                    csum = (csum + f[i ^ (1 << j)]) % mod;
                }
            }
            f[i] = (n + csum) * inv[n - __builtin_popcount(i)] % mod;
        }
        printf("%lld\n", f[0]);
    }
}

版权声明
本文为[JXNU_SONG]所创，转载请带上原文链接，感谢
https://blog.csdn.net/qq_45863710/article/details/124322717

边栏推荐

猜你喜欢

随机推荐