首页 > 其他 > 详细

[20181016][模拟赛]

时间:2018-10-16 17:18:19      阅读:126      评论:0      收藏:0      [点我收藏+]

题目

技术分享图片

思路

全都是位运算,考虑按照二进制拆分进行dp。f[i][j]表示前i个数,二进制的第j位为1的概率。对于为0的概率,直接用(1-f[i][j])即可。

然后就是转移,其实这个题转移蛮好想的,只要一点一点慢慢推就可以了。

PS:注意题目中的\(c_i\)表示的是第i个运算"不"进行的概率。某位大(S)佬(B)就看成了进行当前运算的概率,一首凉凉

代码

#include<cstdio>
#include<iostream>
using namespace std;
typedef long long ll;
const int N = 100000+100;
ll read() {
    ll x = 0,f = 1;char c = getchar();
    while(c < '0' || c > '9') {
        if(c == '-') f = -1;
        c = getchar();
    }
    while(c >= '0' && c <= '9') {
        x = x * 10 + c - '0';
        c = getchar();
    }
    return x * f;
}
int a[N],b[N];//0表示& , 1表示 | ,2表示^
double c[N], f[N][40];
int main() {
    freopen("exp.in","r",stdin);
    freopen("exp.out","w",stdout);
    int n = read();
    for(int i = 1; i <= n; ++i) a[i] = read();
    for(int i = 1; i <= n; ++i) b[i] = read();
    for(int i = 1; i <= n; ++i) scanf("%lf",&c[i]);
    for(int i = 1; i <= n; ++i) {
        for(int j = 0; j <= 30; ++j) {
            int k = (b[i] >> j) & 1;
            if(a[i] == 0) {
                if(k)
                    f[i][j] = f[i-1][j];
                else 
                    f[i][j] = c[i] * f[i-1][j];
            }
            if(a[i] == 1) {
                if(k) 
                    f[i][j] = (1 - c[i]) + c[i] * f[i-1][j];
                else 
                    f[i][j] = f[i-1][j];
            }
            if(a[i] == 2) {
                if(k)
                    f[i][j] = (1 - c[i]) * (1 - f[i-1][j]) + c[i] * f[i-1][j];
                else 
                    f[i][j] = f[i-1][j];
            }
        }
    }
    int now = 1;
    double ans = 0.0;
    for(int i = 0; i <= 30; ++i) {
        ans += f[n][i] * now;
        now <<= 1;
    }
    printf("%.1lf",ans);
    return 0;
}

每篇一言

在珍惜着某个人时,有时候会很难过,有时候会感到寂寞,但是,有时候也会觉得非常快乐。

[20181016][模拟赛]

原文:https://www.cnblogs.com/wxyww/p/9798812.html

(0)
(0)
   
举报
评论 一句话评论(0
关于我们 - 联系我们 - 留言反馈 - 联系我们:wmxa8@hotmail.com
© 2014 bubuko.com 版权所有
打开技术之扣,分享程序人生!