【bzoj2969】矩形粉刷 期望
矩形 期望
2023-09-11 14:22:40 时间
题目描述
为了庆祝新的一年到来,小M决定要粉刷一个大木板。大木板实际上是一个W*H的方阵。小M得到了一个神奇的工具,这个工具只需要指定方阵中两个格子,就可以把这两格子为对角的,平行于木板边界的一个子矩形全部刷好。小M乐坏了,于是开始胡乱地使用这个工具。
假设小M每次选的两个格子都是完全随机的(方阵中每个格子被选中的概率是相等的),而且小M使用了K次工具,求木板上被小M粉刷过的格子个数的期望值是多少。
输入
第一行是整数K,W,H
输出
一行,为答案,四舍五入保留到整数。
样例输入
1 3 3
样例输出
4
题解
期望
由于期望具有可加性,因此可以计算出每个格子被染色的概率,加起来即为答案。
那么一个格子被染色的概率即为$1-(每次都不被染色的概率)^k$。
考虑单次染色没有没染的情况:选定的两个点都在左边、上边、右边、下边,但是会发现四个角的部分会计算两次,因此还需要减掉两个点都在左上、左下、右上、右下的情况。然后求幂加起来即可。
#include <cmath> #include <cstdio> inline double squ(double x) { return x * x; } int main() { int k , n , m , i , j; double ans = 0; scanf("%d%d%d" , &k , &n , &m); for(i = 1 ; i <= n ; i ++ ) for(j = 1 ; j <= m ; j ++ ) ans += 1 - pow((squ((i - 1) * m) + squ((j - 1) * n) + squ((n - i) * m) + squ((m - j) * n) - squ((i - 1) * (j - 1)) - squ((i - 1) * (m - j)) - squ((n - i) * (j - 1)) - squ((n - i) * (m - j))) / squ(n * m) , k); printf("%.0lf\n" , ans); return 0; }
相关文章
- Java实现 LeetCode 84 柱状图中最大得矩形
- java矩形的关系
- java矩形的关系
- Java实现第十届蓝桥杯矩形切割
- java实现矩形区域的交和并
- java实现矩形区域的交和并
- 【OpenCV函数】轮廓提取;轮廓绘制;轮廓面积;外接矩形
- 【队列&栈】LeetCode 84. 柱状图中最大的矩形【困难】
- LeetCode(85):最大矩形
- 1725. 可以形成最大正方形的矩形数目
- C/C++基础讲解(六十一)之图形篇(矩形区域的颜色填充/音乐动画)
- Linux Ubuntu 22.04修改启动界面和登录界面的矩形LOGO
- 利用IIdentify接口实现点选和矩形选择要素
- 【hihocoder 1476】矩形计数
- 华为OD机试 - 矩形相交的面积
- poj 2559求柱形图中最大矩形
- MATLAB | MATLAB地形生成:矩形迭代法 · 傅里叶逆变换法 · 分形柏林噪声法
- 习题 12.4 写一个程序,定义抽象基类Shape,由它派生出3个派生类:Circle(圆形)、Rectangle(矩形)、Triangle(三角形),用一个函数printArea分别输出以上。。。
- pygame学习笔记(1)——安装及矩形、圆型画图