博客
关于我
强烈建议你试试无所不能的chatGPT,快点击我
hdu 5245 Joyful(期望的计算,好题)
阅读量:5881 次
发布时间:2019-06-19

本文共 2962 字,大约阅读时间需要 9 分钟。

Problem Description
Sakura has a very magical tool to paint walls. One day, kAc asked Sakura to paint a wall that looks like an M×N matrix. The wall has M×N squares in all. In the whole problem we denotes (x,y) to be the square at the x-th row, y-th column. Once Sakura has determined two squares (x1,y1) and (x2,y2), she can use the magical tool to paint all the squares in the sub-matrix which has the given two squares as corners.However, Sakura is a very naughty girl, so she just randomly uses the tool for K times. More specifically, each time for Sakura to use that tool, she just randomly picks two squares from all the M×N squares, with equal probability. Now, kAc wants to know the expected number of squares that will be painted eventually.

 

Input
The first line contains an integer T(T≤100), denoting the number of test cases.For each test case, there is only one line, with three integers M,N and K.It is guaranteed that 1≤M,N≤500, 1≤K≤20.
 

 

Output
For each test case, output ''Case #t:'' to represent the t-th case, and then output the expected number of squares that will be painted. Round to integers.

 

 
Sample Input
2 3 3 1 4 4 2

 

 
Sample Output
Case #1: 4 Case #2: 8

 

Hint
The precise answer in the first test case is about 3.56790123.

 

 

Source
 
题意大致是:进行K次染色,每次染色会随机选取一个以(x1,y1),(x2,y2)为一组对角的子矩阵进行染色,求K次染色后染色面积的期望值(四舍五入)。
 
对于这道题的话,首先要考虑的是进行一次选择时的期望。求期望的方法为单独考虑每一格所能获得的期望,然后将所有格的期望相加即为答案。
对于每一个所能获得的期望,即要计算所有包含这一格的个数ans,除于总的选择方案tot

此时我们的问题转向了如何计算A[x.y]上

由题目描述,一次染色中可能的操作有n^2*m^2种

计算A[x,y]时,我们可以把整个矩阵做如下拆分

当前计算的方块为[x,y],即图中编号为5的部分

将其他部分拆分成图上8个区域,则可得到以下关系

对于一种染色方案能够覆盖方块[x,y]时①[x1,y1]取在区域1内时,[x2,y2]可以在5、6、8、9四个区域内任取;②[x1,y1]取在区域2内时,[x2,y2]可以在4、5、6、7、8、9六个区域内任取;③[x1,y1]取在区域3内时,[x2,y2]可以在4、5、7、8四个区域内任取;④[x1,y1]取在区域4内时,[x2,y2]可以在2、3、5、6、8、9六个区域内任取;⑤[x1,y1]取在区域5内时,[x2,y2]可以在所有区域内任取;⑥[x1,y1]取在区域6内时,[x2,y2]可以在1、2、4、5、7、8六个区域内任取;⑦[x1,y1]取在区域7内时,[x2,y2]可以在2、3、5、6四个区域内任取;⑧[x1,y1]取在区域8内时,[x2,y2]可以在1、2、3、4、5、6六个区域内任取;⑨[x1,y1]取在区域1内时,[x2,y2]可以在1、2、4、5四个区域内任取;

计算出这个格子的概率p后,总的答案加上 1-pow(1-p,k),得到最后的答案

 
1 #include
2 #include
3 #include
4 #include
5 #include
6 #include
7 using namespace std; 8 #define ll long long 9 int m,n,k;10 int main()11 {12 int t;13 int ac=0;14 scanf("%d",&t);15 while(t--){16 scanf("%d%d%d",&n,&m,&k);17 double ans=0;18 for(int i=1;i<=n;i++){19 for(int j=1;j<=m;j++){20 double tmp=0;21 tmp=tmp+(double)(i-1)*(j-1)*(n-i+1)*(m-j+1);//122 tmp=tmp+(double)(i-1)*(n-i+1)*m;//223 tmp=tmp+(double)(i-1)*(m-j)*(n-i+1)*j;//324 tmp=tmp+(double)(m-j)*n*j;//625 tmp=tmp+(double)n*m;//526 tmp=tmp+(double)(j-1)*n*(m-j+1);//427 tmp=tmp+(double)(n-i)*(j-1)*i*(m-j+1);//728 tmp=tmp+(double)(n-i)*i*m;//829 tmp=tmp+(double)(n-i)*(m-j)*i*j;//930 31 double p=tmp/n/n/m/m;32 ans=ans+1-pow((1-p),k);33 34 }35 }36 printf("Case #%d: ",++ac);37 printf("%d\n",int(ans+0.5));38 }39 return 0;40 }
View Code

 

 

你可能感兴趣的文章
Windows phone8 基础篇(三) 常用控件开发
查看>>
Oracle学习笔记之五,Oracle 11g的PL/SQL入门
查看>>
大叔手记(3):Windows Silverlight/Phone7/Mango开发学习系列教程
查看>>
考拉消息中心消息盒子处理重构(策略模式)
查看>>
so easy 前端实现多语言
查看>>
【追光者系列】HikariCP源码分析之ConcurrentBag&J.U.C SynchronousQueue、CopyOnWriteArrayList...
查看>>
在navicat中如何新建连接数据库
查看>>
canvas系列教程05-柱状图项目3
查看>>
css绘制几何图形
查看>>
HTML标签
查看>>
理解JS中的Event Loop机制
查看>>
转载:字符编码笔记:ASCII,Unicode和UTF 8
查看>>
修复看不懂的 Console Log
查看>>
Android跨进程通信 AIDL使用
查看>>
ajax常见面试题
查看>>
结合kmp算法的匹配动画浅析其基本思想
查看>>
vue进行wepack打包执行npm run build出现错误
查看>>
【d3.js v4基础】过渡transition
查看>>
VUEJS开发规范
查看>>
Android系统的创世之初以及Activity的生命周期
查看>>