LightOj_1284 Lights inside 3D Grid

题目链接

题意：

　　给一个X * Y * Z 的立方体，每个单位立方体内都有一盏灯，初始状态是灭的，你每次操作如下：

　　1）选择一个点(x1, y1, z1)

　　再选择一个点（x2, y2, z2）

　　将这两个点所形成的立方体内所有的灯全部转换状态（灭的变亮的，亮的变灭的）

　　问， K次操作后，亮着的灯的期望数目。

思路：

　　三维坐标系，每个维度都是相互独立的，所以可以分开计算再相乘。

　　考虑x轴，对于每个点，被选中的概率是多少：假设这个点左边有a个点，右边有b个点，

　　那么这个点不被选中的概率是p = 1.0 - ((x - 1) * (x - 1) - (a * a + b * b)) / x * x。

　　则，这个点在K次操作后被点亮的期望为：E = sigma C(k, i) * p * (1 - p) ^ (k - i)，i为奇数，因为i为偶数时灯是灭的。

　　这是二项展开式（p + (1 - p)） ^ k 的所有奇数项。

　　因此， E = ((p + (1 - p)) ^ k - (-p + (1 - p)) ^ k) / 2, 蓝色部分将所有的奇数项变成了负数，偶数项不变，相减后则成了两倍的奇数项之和。

代码：

 #include <cmath>

 #include <cstdio>

 #include <cstring>

 #include <cstdlib>

 #include <ctime>

 #include <set>

 #include <map>

 #include <list>

 #include <queue>

 #include <string>

 #include <vector>

 #include <fstream>

 #include <iterator>

 #include <iostream>

 #include <algorithm>

 using namespace std;

 #define LL long long

 #define INF 0x3f3f3f3f

 #define MOD 1000000007

 #define eps 1e-6

 #define MAXN 1000000

 #define dd cout<<"debug"<<endl

 #define p(x) cout<<x<<endl

 int x, y, z, k;

 double qpow(double x, int k)

 {

     double res = 1.0;

     while(k)

     {

         if(k & ) res = res * x;

         x = x * x;

         k >>= ;

     }

     return res;

 }

 double get_p(int x, int n)

 {

     return 1.0 - ((x - ) * (x - ) * 1.0 + (n - x) * (n - x) * 1.0) * 1.0 / (n * n);

 }

 int main()

 {

     int T;

     int kcase = ;

     scanf("%d", &T);

     while(T --)

     {

         double ans = 0.0;

         scanf("%d %d %d %d", &x, &y, &z, &k);

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

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

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

                 {

                     double p = get_p(i, x) * get_p(j, y) * get_p(g, z);

                     ans += (1.0 - qpow( - 2.0 * p, k)) / 2.0;

                 }

         printf("Case %d: %.7lf\n", ++kcase, ans);

     }

     return ;

 }

巴特西

LightOj_1284 Lights inside 3D Grid

最新文章

热门文章