BZOJ 2969: 矩形粉刷（期望）

时间：2022-05-25 06:25:26

题意

给你一个\(w*h\)的方阵，不断在上面刷格子。每次等概率选择方阵中的两个点（可以相同）将以这两个点为端点的矩形（边平行于矩形边界）进行染色。共染\(k\)次，问最后被染色的格子的期望值。

题解

（参考了liu_runda大佬的博客）

这真是一道好题~ 思维比较巧妙~

因为我们无法直接考虑每个点\(k\)次后被染色的期望（想一想，为什么）

正难则反，我们可以考虑\(k\)次后没被染色的期望，所以原来被染色的期望就可以转化为\(1-\)没有被染色的期望。

然后期望的线性性使得我们能够直接计算出每个点的答案。

我们先求它一次没有被染色的期望，在求它的\(k\)次方就行了。

我也不是直接求它没被染色的期望，而先求它被染色的期望，再用\(1-\)它就行了。

注意我这里化了两次，一次是求\(k\)次时，一次是求单次的时候，两次化的不同 也就是最后被染色的期望就是 \([1-(1-p)^k]\)

则先求它左上方选个点（要包括该点，后同）和右下方选点的方案数 加上 它右上方和左下方选点的方案数。

这个可以直接乘法原理算出来，但这个会算重复，可以画个图理解理解（我没画图，就调了贼久。。）

就是它所在的列和行的期望会算两遍，所以我们要减去这些贡献。然后中间的又少算了一遍，又要加上。

因为我们选择是有序的，但它选择是无序的，所以要乘上一个\(2\)。

但有一个特殊点我一直算错了，就是自己本身选两遍的方案不能乘\(2\)，因为你本身考虑的就是无序的了。

然后用当前的方案数除以总方案数\((w*h)^2\)就可以得出它一次被染色期望了，然后瞎搞搞就行了。

我的代码应该是网上所见的最简洁的了QAQ

代码

/**************************************************************

    Problem: 2969

    Language: C++

    Result: Accepted

    Time:204 ms

    Memory:1288 kb

****************************************************************/

#include <bits/stdc++.h>

#define For(i, l, r) for(register int i = (l), i##end = (int)(r); i <= i##end; ++i)

#define Fordown(i, r, l) for(register int i = (r), i##end = (int)(l); i >= i##end; --i)

#define Set(a, v) memset(a, v, sizeof(a))

using namespace std;

inline bool chkmin(int &a, int b) {return b < a ? a = b, 1 : 0;}

inline bool chkmax(int &a, int b) {return b > a ? a = b, 1 : 0;}

inline int read() {

    int x = 0, fh = 1; char ch = getchar();

    for (; !isdigit(ch); ch = getchar()) if (ch == '-') fh = -1;

    for (; isdigit(ch); ch = getchar()) x = (x * 10) + (ch ^ 48);

    return x * fh;

}

void File() {

#ifdef zjp_shadow

    freopen ("P2969.in", "r", stdin);

    freopen ("P2969.out", "w", stdout);

#endif

} 

double Pow(double x, int power) {

    double res = 1.0;

    for (; power; power >>= 1, x *= x)

        if (power & 1) res *= x;

    return res;

}

#define area(xl, yl, xr, yr) ((xr - xl + 1) * (yr - yl + 1))

int k, w, h;

double allprob, plan, expect = 0.0, now;

int main () {

    File();

    cin >> k >> w >> h;

    allprob = (double)(w * h) * (w * h);

    For (i, 1, w)

        For (j, 1, h) {

            plan = 0;

            plan += (double)area(1, 1, i, j) * area(i, j, w, h);

            plan += (double)area(1, j, i, h) * area(i, 1, w, j);

            plan -= (double)i * (w - i + 1);

            plan -= (double)j * (h - j + 1);

            plan = plan * 2 + 1;

            now = 1.0 - Pow(1.0 - plan / allprob, k);

            expect += now;

        }

    printf ("%.0lf\n", expect);

    return 0;

}

相关文章