Why so serious? --[NKU]schindlerlee

pku3744

schindlerlee原创,禁止转载和用于商业用途
刚比赛完,先贴代码
  1 /* 
  2  * SOUR:pku 3744
  3  * ALGO:compulicted
  4  * DATE: 2009年 08月 23日 星期日 12:37:44 CST
  5  * COMM:3
  6  * */
  7 #include<iostream>
  8 #include<cstdio>
  9 #include<cstdlib>
 10 #include<cstring>
 11 #include<algorithm>
 12 using namespace std;
 13 #define inf 0x7fffffff
 14 #define debug 1
 15 double p;
 16 int mine[26], n;
 17 
 18 struct M {
 19     double v11, v12, v21, v22;
 20     M operator*( M b)
 21     {
 22         M c;
 23         c.v11 = v11 * b.v11 + v12 * b.v21;
 24         c.v12 = v11 * b.v12 + v12 * b.v22;
 25         c.v21 = v21 * b.v11 + v22 * b.v21;
 26         c.v22 = v21 * b.v12 + v22 * b.v22;
 27         return c;
 28     }
 29 
 30     M operator*double c)
 31     {
 32         v11 *= c, v12 *= c;
 33         v21 *= c, v22 *= c;
 34         return *this;
 35     }
 36 } unit,self;
 37 
 38 
 39 M f(int t)
 40 {
 41     if (t == 0) {
 42         M a;
 43         a.v11 = 1, a.v12 = 0;
 44         a.v21 = 0, a.v22 = 1;
 45         return a;
 46     }
 47     if (t == 1) {
 48         return unit;
 49     }
 50     if (t % 2 == 0) {
 51         M tmp = f(t / 2);
 52         return tmp * tmp;
 53     }
 54     M tmp = f(t / 2);
 55     return tmp * tmp * unit;
 56 }
 57 
 58 /*
 59  f(n)      { p ,1-p }    f(n-1)   
 60  f(n-1) =  { 1 , 0  } *  f(n-2)
 61  * */
 62 int main()
 63 {
 64     int i, j;
 65     while (scanf("%d %lf"&n, &p) == 2) {
 66         unit.v11 = p, unit.v12 = 1 - p;
 67         unit.v21 = 1, unit.v22 = 0;
 68 
 69         self.v11 = 1, self.v12 = 0;
 70         self.v21 = 0, self.v22 = 1;
 71 
 72         bool flag = false;
 73         for (i = 0; i < n; i++) {
 74             scanf("%d", mine + i);
 75         }
 76         sort(mine, mine + n);
 77         n = unique(mine, mine + n) - mine;
 78         for (i = 1; i < n; i++) {
 79             if (mine[i] - mine[i - 1== 1) {
 80                 flag = true;
 81                 break;
 82             }
 83         }
 84         if (flag || mine[0== 1) {
 85             printf("%.7f\n"0.0);
 86             continue;
 87         }
 88         int t = 1;
 89         M res = self, tmp;
 90         for (i = 0; i < n; i++) {
 91             tmp = f(mine[i] - 1 - t);
 92             t = mine[i] + 1;
 93             res = res * tmp * (1 - p);
 94             res.v12 = 0//跳地雷
 95         }
 96         if(res.v11 <= 0) {
 97             printf("%.7f\n"0.0);
 98         }else {
 99             printf("%.7f\n", res.v11);
100         }
101     }
102     return 0;
103 }
104 

posted on 2009-08-23 18:50 schindlerlee 阅读(1264) 评论(0)  编辑 收藏 引用 所属分类: 解题报告


只有注册用户登录后才能发表评论。
网站导航: 博客园   IT新闻   BlogJava   知识库   博问   管理