首页 > ACM题库 > HDU-杭电 > HDU 4649-Professor Tian-概率-[解题报告]HOJ
2015
09-17

HDU 4649-Professor Tian-概率-[解题报告]HOJ

Problem Description
Timer took the Probability and Mathematical Statistics course in the 2012, But his bad attendance angered Professor Tian who is in charge of the course. Therefore, Professor Tian decided to let Timer face a hard probability problem, and announced that if he
fail to slove the problem there would be no way for Timer to pass the final exam. 
As a result , Timer passed. 
Now, you, the bad guy, also angered the Professor Tian when September Ends. You have to faced the problem too. The problem comes that there is an expression and you should calculate the excepted value of it. And the operators it may contains are ‘&’ (and),’|'(or)
and ‘^’(xor) which are all bit operators. For example: 7&3=3, 5&2=0, 2|5=7, 4|10=14, 6^5=3, 3^4=7.
Professor Tian declares that each operator Oi with its coming number Ai+1 may disappear, and the probability that it happens is Pi (0<i<=n). 
 


Input
The input contains several test cases. For each test case, there is a integer n (0<n<=200) in the first line.In the second line, there are n+1 integers, stand for {Ai}. The next line contains n operators ,stand for {Oi}. The forth line
contains {Pi}. 
Ai will be less than 220, 0<=Pi<=1.
 


Output
For each text case, you should print the number of text case in the first line.Then output the excepted value of the expression, round to 6 decimal places.
 


Sample Input
2 1 2 3 ^ ^ 0.1 0.2 2 8 9 10 ^ ^ 0.5 0.78 1 1 2 & 0.5
 


Sample Output
Case 1: 0.720000 Case 2: 4.940000 Case 3: 0.500000
 
题意:
给你一个式子,第i位有pi说的概率消失掉,要计算最后值的期望
思路:
每个数二进制最多20位,我们对每一位为1的情况进行计算即可
#include <iostream>
#include <stdio.h>
#include <string.h>
#include <stack>
#include <queue>
#include <map>
#include <set>
#include <vector>
#include <math.h>
#include <bitset>
#include <algorithm>
#include <climits>
using namespace std;

#define ls 2*i
#define rs 2*i+1
#define UP(i,x,y) for(i=x;i<=y;i++)
#define DOWN(i,x,y) for(i=x;i>=y;i--)
#define MEM(a,x) memset(a,x,sizeof(a))
#define W(a) while(a)
#define gcd(a,b) __gcd(a,b)
#define LL long long
#define N 205
#define MOD 1000000007
#define INF 0x3f3f3f3f
#define EXP 1e-8
#define rank rank1
const int mod = 10007;

int n,a[N];
double dp[N],p[N],ans;
char op[N][5];

int main()
{
    int i,j,k,cas=1;
    while(~scanf("%d",&n))
    {
        for(i = 0; i<=n; i++)
            scanf("%d",&a[i]);
        for(i = 1; i<=n; i++)
            scanf("%s",op[i]);
        for(i = 1; i<=n; i++)
            scanf("%lf",&p[i]);
        ans = 0;
        for(i = 0; i<=20; i++)
        {
            double q;
            if(a[0]&(1<<i)) q = 1;
            else q = 0;
            for(j = 1; j<=n; j++)
            {
                if(a[j]&(1<<i))
                {
                    if(op[j][0]=='&')
                        continue;
                    else if(op[j][0]=='^')
                        q = q*p[j]+(1-q)*(1-p[j]);
                    else
                        q = q*p[j]+(1-p[j]);
                }
                else
                {
                    if(op[j][0]=='&')
                        q = q*p[j];
                    else
                        continue;
                }
            }
            ans += q*(1<<i);
        }
        printf("Case %d:\n%lf\n",cas++,ans);
    }

    return 0;
}

版权声明:本文为博主原创文章,未经博主允许不得转载。

参考:http://blog.csdn.net/libin56842/article/details/46929207