UVA 11605 Lights inside a 3d Grid —— （概率和期望）

　　题意：见大白书P181。

　　分析：一个一个点的进行分析，取其期望然后求和即可。假设当前点在第一次中被选到的概率为p，f[i]表示进行k次以后该点亮的概率（在这里也可以理解为期望），g[i]表示k次后该点不亮的概率，那么联立：

　　　　1.f[1] = p;

　　　　2.f[i] + g[i] = 1.0;

　　　　3.f[i] = f[i-1] * (1-p) + g[i-1] * p;

　　上面三个式子都很好理解。然后借助一下高中推数列的方法，可以推得：f[i] = 1/2-1/2*(1-2*p)^i。

　　那么，我们该怎么求p呢。不妨把三维分解成三个一维，那么，一个维度（即线段）上求的方法如下：

　　　　假设这个维度的长度是len，总的可能种数是len*len（因为题目没规定A和B两点之间坐标的大小，因此反过来的情况也必须算上），同理可以计算得　　　　到包含了这个点的线段总数，后者除以前者即可得到该维度下的p'。

　　然后三个维度的p'相乘即可得到p。

　　最后O(n^3)枚举点并累和即可解决该问题。

　　代码如下：

 #include <stdio.h>

 #include <algorithm>

 #include <string.h>

 #include <math.h>

 using namespace std;

 int n,m,p,k;

 // f表示某个点，该点被选到的概率为x，其经过k次以后能亮的概率

 double f(double x)

 {

     return 0.5 - 0.5 * pow((-*x), k);

 }

 // get表示分解后的某条轴上这个点被选到的概率

 double get(int x,int len)

 {

     // -1 是因为两个点都在x这个位置这种情况被多算了一次

     return (2.0*x*(len-x+) - ) / (1.0*len*len);

 }

 int main()

 {

     int T;

     scanf("%d",&T);

     for(int kase=;kase<=T;kase++)

     {

         scanf("%d%d%d%d",&n,&m,&p,&k);

         double ans = 0.0;

         for(int i=;i<=n;i++)

         {

             double nn = get(i, n);

             for(int j=;j<=m;j++)

             {

                 double mm = get(j, m);

                 for(int z=;z<=p;z++)

                 {

                     ans += f(nn * mm * get(z, p));

                 }

             }

         }

         printf("Case %d: %.15f\n",kase,ans);

     }

     return ;

 }

　　值得注意的是，这题下k的范围是1e4，如果k更大例如1e9，那么就不能用数学方法直接算出表达式了，因为带个pow复杂度毕竟是较高的，应当使用矩阵快速幂来直接递推。

巴特西

UVA 11605 Lights inside a 3d Grid —— （概率和期望）

最新文章

热门文章