喝绿茶的好处,雯雅婷5出招表,倚天之青瑶
joyful
time limit: 2000/1000 ms (java/others) memory limit: 65536/65536 k (java/others)
total submission(s): 781 accepted submission(s): 339
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
the 2015 acm-icpc china shanghai metropolitan programming contest
题目大意：
就是有一个 m*n 的矩阵方格，然后你每次取两个方格，分别是(x1,y1)和(x2,y2);然后就是每次覆盖一个子矩阵是以(x1,y1)和(x2,y2)为对角线构成的矩阵，让你求的就是你进行 k 次之后得到的方格数的期望。
解题思路：
其实这个题，画一下就行了而且非常清楚，我也不会画，我就用语言描述啦，我们先求一下总的方案数，第一个方格是m*n,第二个方格还是m*n,那么总的方案数就是 m^2*n^2,假设我们选的(i, j)点就是没有被覆盖的点，那么我们选的那两个方格肯定是 i行上面的和下面的 j列左面的和右面的，但是我们重复了那4个角（其实也不能叫角，应该叫子矩阵），所以我们要减去那四个角的矩阵，假设结果是ans，那么概率显然就是 p = ans/(m^2*n^2)然后我们取了k次之后就是p^k,那么被覆盖的概率就是 1-p^k,然后我们进行的就是 两个循环 for(i: 1-m)，for(j: i-n)，那么每次都对1-p^k进行累加得到的就是期望，注意的就是m^2*n^2会爆int,
最后的结果是四舍五入的，有一个小窍门（四舍五入的时候加上0.5就行了）
my code：
我要评论#include
#include
using namespace std;
typedef long long ll;
int main()
{
int t;
cin>>t;
for(int cas=1; cas>m>>n>>k;
ll tot = (m*n) * (m*n);
double ret = 0;
for(ll i=1; i
如对本文有疑问，请在下面进行留言讨论，广大热心网友会与你互动！！ 点击进行留言回复
如何在没有core文件的情况下用dmesg+addr2line定位段错误
用QT制作3D点云显示器——QtDataVisualization
网友评论