首页 > ACM题库 > HDU-杭电 > HDU 4694-Important Sisters-概率-[解题报告]HOJ
2015
09-17

HDU 4694-Important Sisters-概率-[解题报告]HOJ

Important Sisters

问题描述 :

There are N clones of Misaka Mikoto (sisters) forming the Misaka network. Some pairs of sisters are connected so that one of them can pass message to the other one. The sister with serial number N is the source of all messages. All the other sisters get message directly or indirectly from her. There might be more than one path from sister #N to sister #I, but some sisters do appear in all of these paths. These sisters are called important sister of sister #K. What are the important sisters of each sister?
Huge String

输入:

There are multiple test cases. Process to the End of File.
The first line of each test case contains two integers: the number of sisters 1 ≤ N ≤ 50,000 and the number of connections 0 ≤ M ≤ 100,000. The following M lines are M connections 1 ≤ Ai, Bi ≤ N, indicating that Ai can pass message to Bi.

输出:

There are multiple test cases. Process to the End of File.
The first line of each test case contains two integers: the number of sisters 1 ≤ N ≤ 50,000 and the number of connections 0 ≤ M ≤ 100,000. The following M lines are M connections 1 ≤ Ai, Bi ≤ N, indicating that Ai can pass message to Bi.

样例输入:

3 2
3 2
2 1
5 7
3 2
1 2
2 1
3 1
3 2
5 3
5 4

样例输出:

6 5 3
9 10 8 9 5

  题目链接:http://acm.hdu.edu.cn/showproblem.php?pid=4649

  题意:给一个位运算的表达式,每个运算符和其后的运算数有一定概率不计算,求最后表达式的期望。

  因为只有20位,而且&,|,^都不会进位,那么一位一位地看,每一位不是0就是1,这样求出每一位是1的概率,再乘以该位的十进制数,累加,就得到了总体的期望。

  对于每一位,状态转移方程如下:

    f[i][j]表示该位取前i个数,运算得到j(0或1)的概率是多少。

    f[i][1]=f[i-1][1]*p[i]+根据不同运算符和第i位的值运算得到1的概率。

    f[i][0]同理。

 //STATUS:C++_AC_0MS_248KB
 #include <functional>
 #include <algorithm>
 #include <iostream>
 //#include <ext/rope>
 #include <fstream>
 #include <sstream>
 #include <iomanip>
 #include <numeric>
 #include <cstring>
 #include <cassert>
 #include <cstdio>
 #include <string>
 #include <vector>
 #include <bitset>
 #include <queue>
 #include <stack>
 #include <cmath>
 #include <ctime>
 #include <list>
 #include <set>
 #include <map>
 using namespace std;
 //#pragma comment(linker,"/STACK:102400000,102400000")
 //using namespace __gnu_cxx;
 //define
 #define pii pair<int,int>
 #define mem(a,b) memset(a,b,sizeof(a))
 #define lson l,mid,rt<<1
 #define rson mid+1,r,rt<<1|1
 #define PI acos(-1.0)
 //typedef
 typedef __int64 LL;
 typedef unsigned __int64 ULL;
 //const
 const int N=210;
 const int INF=0x3f3f3f3f;
 const int MOD= 1000000007,STA=8000010;
 const LL LNF=1LL<<55;
 const double EPS=1e-9;
 const double OO=1e30;
 const int dx[4]={-1,0,1,0};
 const int dy[4]={0,1,0,-1};
 const int day[13]={0,31,28,31,30,31,30,31,31,30,31,30,31};
 //Daily Use ...
 inline int sign(double x){return (x>EPS)-(x<-EPS);}
 template<class T> T gcd(T a,T b){return b?gcd(b,a%b):a;}
 template<class T> T lcm(T a,T b){return a/gcd(a,b)*b;}
 template<class T> inline T lcm(T a,T b,T d){return a/d*b;}
 template<class T> inline T Min(T a,T b){return a<b?a:b;}
 template<class T> inline T Max(T a,T b){return a>b?a:b;}
 template<class T> inline T Min(T a,T b,T c){return min(min(a, b),c);}
 template<class T> inline T Max(T a,T b,T c){return max(max(a, b),c);}
 template<class T> inline T Min(T a,T b,T c,T d){return min(min(a, b),min(c,d));}
 template<class T> inline T Max(T a,T b,T c,T d){return max(max(a, b),max(c,d));}
 //End
 
 #define get(a,k) ((a)&(1<<(k))?1:0)
 
 double f[N][2],p[N];
 int num[N],op[N];
 int n;
 
 int main(){
  //   freopen("in.txt","r",stdin);
     int ca=1,i,j,k;
     double ans;
     char s[2];
     while(~scanf("%d",&n))
     {
         for(i=0;i<=n;i++)
             scanf("%d",&num[i]);
         for(i=1;i<=n;i++){
             scanf("%s",s);
             op[i]=(s[0]=='&'?0:(s[0]=='|'?1:2));
         }
         for(i=1;i<=n;i++)
             scanf("%lf",&p[i]);
         ans=0;
         for(k=0;k<20;k++){
             f[0][0]=!get(num[0],k);
             f[0][1]=!f[0][0];
             for(i=1;i<=n;i++){
                 f[i][0]=f[i-1][0]*p[i];
                 f[i][1]=f[i-1][1]*p[i];
                 if(get(num[i],k)){
                     if(op[i]==0){
                         f[i][0]+=f[i-1][0]*(1-p[i]);
                         f[i][1]+=f[i-1][1]*(1-p[i]);
                     }
                     else if(op[i]==1)
                         f[i][1]+=1-p[i];
                     else {
                         f[i][0]+=f[i-1][1]*(1-p[i]);
                         f[i][1]+=f[i-1][0]*(1-p[i]);
                     }
                 }
                 else {
                     if(op[i]==0)
                         f[i][0]+=1-p[i];
                     else {
                         f[i][0]+=f[i-1][0]*(1-p[i]);
                         f[i][1]+=f[i-1][1]*(1-p[i]);
                     }
                 }
             }
             ans+=f[n][1]*(1<<k);
         }
 
         printf("Case %d:\n%.6lf\n",ca++,ans);
     }
     return 0;
 }

 

参考:http://www.cnblogs.com/zhsl/archive/2013/08/07/3242263.html