【BZOJ4036】【LOJ2127】【HAOI2015】按位或

Author Avatar
q234rty 2月 25, 2018

Min-Max容斥+子集和变换即可。

下面不区分普通的数和集合。

设第一次访问第 i 位的时间为 X_i ，设 U 为 \{X_i\} ，则原题就是求 E(max(U)) 。 直接套用Min-Max容斥可得：

E(max(U))= \sum_{S \subseteq U} (-1)^{|S|+1}E(min(S))

考虑计算 E(min(S)) ，设

k=\sum_{T \subseteq {U-S}} P_T

由等比数列求和公式容易发现

E(min(S))=\frac{1}{1-k}

于是子集和变换求出所有的 k 即可，注意特判INF的情况。

Code

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int MAXSIZE=30000020;
int bufpos;
char buf[MAXSIZE];
#define NEG 0
void init(){
    #ifdef LOCAL
        freopen("4036.txt","r",stdin);
    #endif
    buf[fread(buf,1,MAXSIZE,stdin)]=' ';
    bufpos=0;
}
#if NEG
int readint(){
    bool isneg;
    int val=0;
    for(;!isdigit(buf[bufpos]) && buf[bufpos]!='-';bufpos++);
    bufpos+=(isneg=buf[bufpos]=='-');
    for(;isdigit(buf[bufpos]);bufpos++)
        val=val*10+buf[bufpos]-'0';
    return isneg?-val:val;
}
#else
int readint(){
    int val=0;
    for(;!isdigit(buf[bufpos]);bufpos++);
    for(;isdigit(buf[bufpos]);bufpos++)
        val=val*10+buf[bufpos]-'0';
    return val;
}
#endif
char readchar(){
    for(;isspace(buf[bufpos]);bufpos++);
    return buf[bufpos++];
}
int readstr(char* s){
    int cur=0;
    for(;isspace(buf[bufpos]);bufpos++);
    for(;!isspace(buf[bufpos]);bufpos++)
        s[cur++]=buf[bufpos];
    s[cur]='\0';
    return cur;
}
double p[1<<20];
char s[101];
int main(){
    init();
    int n=readint();
    for(int i=0;i<(1<<n);i++){
        readstr(s);
        p[i]=strtod(s,0);
    }
    for(int i=0;i<n;i++)
        for(int j=0;j<(1<<n);j++)
            if (j>>i&1)
                p[j]+=p[j^(1<<i)];
    double ans=0;
    for(int i=1;i<(1<<n);i++){
        double t=1-p[(1<<n)-1-i];
        if (t<1e-9)
            return puts("INF"),0;
        t=1/t;
        if (__builtin_parity(i))
            ans+=t;
        else ans-=t;
    }
    printf("%.10f",ans);
}

Written with StackEdit.

知识共享许可协议
本作品采用知识共享署名-相同方式共享 4.0 国际许可协议进行许可。
本文链接：https://www.q234rty.top/2018/02/25/bzoj4036/

隐藏