概率、期望



前言

被dalao们虐成渣了 QAQQQQQQQ
回到正题，从高中开始，个人就挺怕概率/期望类的题目的，以为到大学可以逃过一劫，没想到竞！赛！要！考！
是福不是祸，是祸躲不过，只能好好练题找找感觉了_(:з」∠)_


A Dangerous Maze - LightOJ 1027

题意
在一个迷宫中，有n扇门，每扇门需要花费Ti时间带你出迷宫或者回到起点，求出迷宫的时间的期望值
思路
!

  #include <cstdio>
  #include <cstring>
  #include <algorithm>
  #include <cmath>
  using namespace std;

  int main(){
      int t, csn = 1;
      scanf("%d", &t);
      while(t--){
          int n;
          int sum = 0, cnt = 0;
          scanf("%d", &n);
          for(int i = 0; i < n; i++){
              int val;
              scanf("%d", &val);
              if(val < 0)     cnt++;
              sum += (int)fabs(val);
          }
          printf("Case %d: ", csn++);
          if(n == cnt){
              printf("inf\n");
          }else{
              int m = __gcd(n - cnt, sum);
              printf("%d/%d\n", sum/m, (n - cnt)/m);
          }
      }
  }


Birthday Paradox - LightOJ 1104

题意
给定n天，问要使得n天中至少有2人生日在同一天的概率不低于0.5，至少要有多少人
思路
具体查百度百科“生日悖论”

  #include <iostream>
  #include <cstdio>
  #include <cstring>
  using namespace std;

  int main(){
      int t, csn = 1;
      scanf("%d", &t);
      while(t--){
          int val;
          scanf("%d", &val);

          int ans = 1;
          double sum = 1;
          while(true){
              sum = sum*(val - ans + 1)/val;
              if(1 - sum >= 0.5)   break;
              ans++;
          }
          printf("Case %d: %d\n", csn++, ans - 1);
      }
      return 0;
  }


Just another Robbery - LightOJ 1079

题意
哈利波特拍完戏没事做要去抢银行（出题人你这样出题会被打死的），给定危险率临界值P和m家银行，每家银行能抢劫得到的金额Mi和危险率pi，问最多能抢到多少钱
思路
一开始有想到01背包的，然而很纳闷这概率是double型的怎么做背包DP呢
翻了一下题解惊到了
把金额作为背包容量，DP安全率（1-pi），维护最大值，最后倒回来扫在安全率临界值（1-P）之上的最大金额

  #include <iostream>
  #include <cstdio>
  #include <cstring>
  #include <algorithm>
  using namespace std;
  const int N = 1e4 + 15;

  double pp[N];
  int val[N];
  double dp[N];

  int main(){
      int t, csn = 1;
      scanf("%d", &t);
      while(t--){
          memset(dp, 0, sizeof(dp));
          dp[0] = 1;
          double p;
          int m;
          scanf("%lf%d", &p, &m);
          p = 1 - p;
          for(int i = 1; i <= m; i++){
              scanf("%d%lf", &val[i], &pp[i]);
              pp[i] = 1 - pp[i];
          }
          for(int i = 1; i <= m; i++){
              for(int j = N - 1; j >= val[i]; j--){
                  dp[j] = max(dp[j], dp[j - val[i]]*pp[i]);
              }
          }
          int ans;
          for(int i = N - 1; i >= 0; i--){
              if(dp[i] >= p){
                  ans = i;
                  break;
              }
          }
          printf("Case %d: %d\n", csn++, ans);
      }
      return 0;
  }


Race to 1 Again - LightOJ 1038

题意
一个数可以随机地从它的因子中选择一个，变成那个数，再重复以上操作，求期望步数
思路

  #include <cstdio>
  #include <cstring>
  #include <algorithm>
  #include <vector>
  using namespace std;
  const int N = 1e5 + 15;
  const int inf = 0x3f3f3f3f;

  vector<int> vec[N];
  double dp[N];

  int main(){
      dp[1] = 0;
      vec[1].push_back(1);
      for(int i = 1; i < N; i++){
          for(int j = 1; i*j < N; j++){
              vec[i*j].push_back(j);
          }
      }
      for(int i = 2; i < N; i++){
          int m = vec[i].size();
          double sum = m;
          for(int j = 1; j < m; j++){
              sum += dp[vec[i][j]];
          }
          dp[i] = sum/(m - 1);
      }

      int t, csn = 1;
      scanf("%d", &t);
      while(t--){
          int idx;
          scanf("%d", &idx);
          printf("Case %d: %.15f\n", csn++, dp[idx]);
      }
  }


Dice (III) - LightOJ 1248

题意
求一个骰子各面各出现至少一次所需投掷次数的期望
思路

  #include <cstdio>
  #include <cstring>
  #include <algorithm>
  #include <iostream>
  using namespace std;
  const int N = 1e6 + 15;
  const int inf = 0x3f3f3f3f;
  typedef long long ll;

  int main(){
      int t, csn = 1;
      scanf("%d", &t);
      while(t--){
          double sum = 0;
          int n;
          scanf("%d", &n);
          for(int i = 0; i < n; i++)  sum += (double)n/(n - i);
          printf("Case %d: %.15f\n", csn++, sum);
      }
  }