LightOJ-1284 Lights inside 3D Grid (概率计数)

el/2024/4/20 16:05:52

 

J - Lights inside 3D Grid

 LightOJ - 1284 

 

 

 

题解:概率计数。因为是求期望值,考虑每个点对答案的贡献:对每个点是亮着的概率求和就是所求期望。


那么每个点亮着的概率为多少呢?根据题意,对于点(x,y,z)只有当被选中的2个点(x1,y1,z1),(x2,y2,z2),
满足x1<=x<=x2且y1<=y<=y2且z1<=z<=z2时,该点的状态才会改变,因此对于每一维,

在区间内的概率=1-区间在该点的同一侧的概率
该点状态会改变的概率p=x维在区间内的概率*y维在区间内的概率*z维在区间内的概率


上述的只是状态改变一次的概率,题目中说会选择k次区间,根据异或原理,在这k次中,如果状态改变的次数为奇数次,那么该点最终是亮着的。
设f(x)为选择x次区间时,状态改变次数为奇数的概率,g(x)为状态改变次数为偶数的概率。
f(x)=(1-p)*f(x-1)+p*g(x-1)
g(x)=(1-p)*g(x-1)+p*f(x-1)
f(x)+g(x)=1
因此f(x)=(1-2p)*f(x-1)+p,两边同时除以(1-2p)^x,再化简成等比数列通项公式f(x)=0.5-0.5*(1-2p)^x

 

#include<cstdio>
#include<algorithm>
#include<string.h>
using namespace std;double P (int i, int x) {return 1.0 - 1.0 * ( (i - 1) * (i - 1) + (x - i) * (x - i)) / (x * x);
}
double pow (double a, int b) {double ret = 1;while (b) {if (b & 1) ret = ret * a;a = a * a;b >>= 1;}return ret;
}
int main() {int T, x, y, z, k;scanf ("%d", &T);for (int cas = 1; cas <= T; cas++) {scanf ("%d%d%d%d", &x, &y, &z, &k);double ans = 0;for (int i = 1; i <= x; i++) {for (int j = 1; j <= y; j++) {for (int s = 1; s <= z; s++) {double p = P (i, x) * P (j, y) * P (s, z);ans += 0.5 - 0.5 * pow (1 - 2 * p, k);}}}printf ("Case %d: %.7f\n", cas, ans);}return 0;
}

 

 

 

 

 


http://www.ngui.cc/el/2314502.html

相关文章

LightOJ-1287 Where to Run(期望dp)

K - Where to Run LightOJ - 1287 题意&#xff1a;有n个城市&#xff0c;编号为0~n-1&#xff0c;有m条有权无向边&#xff0c;有个小偷从编号为0的城市出发&#xff0c;他不会走已经走过的城市&#xff0c; 他有2种决策&#xff1a;①停留在这个城市5分钟&#xff1b;②如果…

LightOJ-1408 Batting Practice(期望推公式)

Q - Batting Practice LightOJ - 1408 题意&#xff1a;每次投球投偏的概率为p&#xff0c;如果连续投中k1次或者连续投偏k2次则投球结束&#xff0c;问投球个数的期望值 题解&#xff1a;数学期望推导公式 设f(x)为连续投偏x次的期望,g(x)为连续投中x次的期望 f(k1)g(k2)0 先…

LightOJ-1395 A Dangerous Maze (II) (期望dp)

P - A Dangerous Maze (II) LightOJ - 1395 题解&#xff1a;期望dp&#xff0c;设正确的门有a个&#xff0c;平均耗时为sum1&#xff0c;错误的门有b个&#xff0c;平均耗时为sum2。 状态转移分2部分&#xff1a; ①当ik时&#xff0c;即已经记住k次走错的门&#xff0c; ②…

LightOJ-1321 Sending Packets(期望+spfa)

M - Sending Packets LightOJ - 1321 题意&#xff1a;给定一张无向图&#xff0c;每条边都有一个通过的概率 &#xff0c;如果无法通过&#xff0c;那么就要回到起点重新出发从起点到终点的时间固定为K&#xff0c;如果成功到达&#xff0c;又需要额外花费K的时间&#xff0c;…

LightOJ-1364 Expected Cards(期望dp)

O - Expected Cards LightOJ - 1364 题解&#xff1a;高维期望dp&#xff0c;dp[i][j][k][s][q][p]表示每种牌分别有i,j,k,s张&#xff0c;Joker的状态分别为q,p时的期望值&#xff0c;用记忆化搜索一下#include<bits/stdc.h> using namespace std; const double eps 1…

LightOJ-1342 Aladdin and the Magical Sticks(期望dp)

N - Aladdin and the Magical Sticks LightOJ - 1342 题解&#xff1a;期望dp。设不可分辨的木棍个数为n1&#xff0c;平均权值为tot1,可分辨的木棍个数为n2&#xff0c;平均权值为tot2 对于dp[i][j]&#xff0c;表示已拿过i个不可分辨的木棍和j个可分辨的木棍&#xff0c;那么…

期望amp;概率dp总结

总算刷完kuangbin期望&概率专题了&#xff0c;下面总结一下心得和题解&#xff01;1.期望dp 期望dp通常逆推&#xff0c;即从结果推向初始状态&#xff0c;也可以用记忆化搜索进行dp&#xff1b; EΣp1*(E1X1)Σp2*(EX2) 其中E为当前状态的期望&#xff0c;E1为下一个状态的…

HDU-4352 XHXJ's LIS(数位dp+状压)

B - XHXJs LIS HDU - 4352 题意&#xff1a;给定一个区间[l,r]&#xff0c;问区间内有多少个数满足&#xff1a;它的每一位上的数字所组成的序列的最长上升子序列的长度恰好是k 题解&#xff1a;数位dp,考虑到最长上升子序列的O(nlogn)的解法&#xff0c;因为只有0~9共10种数字…

HDU-4734 F(x) (数位dp)

H - F(x) HDU - 4734 题解&#xff1a;数位dp&#xff0c;考虑到T很大&#xff0c;不能每次都清空dp数组 一开始想错了&#xff0c;开了3维数组dp[i][tot][sum],表示当前数位是第i位&#xff0c;F(A)tot&#xff0c;到当前数位为止的F(x)的值&#xff0c;结果超内存了。 发现只…

HDU-4507 吉哥系列故事――恨7不成妻 (数位dp)

J - 吉哥系列故事――恨7不成妻 HDU - 4507 题解&#xff1a;数位dp 和简单的数位dp不同&#xff0c;这道题要算所有合法数的平方和 考虑到一个数可以写成XΣAi*Pi,(其中Ai为X每一位的值&#xff0c;Pi10^i) 因为(AB)^2A*A2*A*BB*B (X1X2X3...Xn)^2X1^22*X1*(X2X3...Xn)(X2X…