题意:给你n+1个数,n个运算符(代表在n+1个数之间的运算关系),n个概率(代表第i部运算被略去的概率),求最后期望。
吐槽:擦!大板刷题,今天下午却卡到最后都没想出来,蛋疼死的节奏。
之后看官方报告才恍然大悟,居然是二进制记录概率,哎,只怪思路不够开阔啊,赛后写了下A了。
官方思路:
G. Professor Tian
反状态压缩——把数据转换成20位的01来进行运算
因为只有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]同理。
初始状态:f[0][0~1]=0或1(根据第一个数的该位来设置)
每一位为1的期望 f[n][1]
#include<iostream> #include<cstdio> #include<cstring> #include<cmath> using namespace std; double a[30],d[300],ans; int b[20],s[300],n; char f[300],c[5]; int ca; int main() { ca=0; while(scanf("%d",&n)!=EOF) { for(int i=0;i<=n;i++)scanf("%d",&s[i]); for(int i=1;i<=n;i++) { scanf("%s",&c); f[i]=c[0]; } for(int i=1;i<=n;i++)scanf("%lf",&d[i]); for(int i=1;i<=20;i++) { if(s[0]%2==1)a[i]=1; else a[i]=0; s[0]/=2; } for(int j=1;j<=n;j++) { if(f[j]=='&') { for(int i=1;i<=20;i++) { if(s[j]%2==1)a[i]=a[i]*(1.0-d[j])+a[i]*d[j]; else a[i]*=d[j]; s[j]/=2; } } else if(f[j]=='|') { for(int i=1;i<=20;i++) { if(s[j]%2==1)a[i]=(1.0-d[j])+a[i]*d[j]; s[j]/=2; } } else if(f[j]=='^') { for(int i=1;i<=20;i++) { if(s[j]%2==1)a[i]=(1.0-a[i])*(1.0-d[j])+a[i]*d[j]; s[j]/=2; } } } ans=0; for(int i=1;i<=20;i++) { ans+=a[i]*((double)pow(2,i-1)); } printf("Case %d:\n%.6f\n",++ca,ans); } return 0; }