1 条题解

  • 0
    @ 2022-4-18 20:00:23

    首先,我们可以利用等比数列求和公式,因为 0.4p<0.60.4 \le p < 0.6,删去分子上的 A(q+1)A(q+1) 算出每对男女 (i,j)(i,j) 在一起的概率。询问时倒序插入并用树状数组维护。

    比如对一个女生 aa,有 kk 个候选男生编号为 11kk。那么对于第 mm 个男生, (a,m)(a,m) 在一起的概率就是 (1p)m1×p+(1p)k×(1p)m1×p+(1p)2k×(1p)m1×p+...+(1p)x1×(1p)m1×p(1-p) ^ {m-1} \times p + (1-p)^k \times (1-p) ^ {m-1} \times p + (1-p)^{2k} \times (1-p) ^ {m-1} \times p + ...+(1-p)^{x-1}\times (1-p) ^ {m-1} \times p

    我们不妨先利用等比数列求和公式:

    Sn=a1×1qn1qS_n=a1\times \dfrac{1-q^n}{1-q}

    其中, a1=(1p)m1×p,q=(1p)ka_1 = (1-p)^{m-1} \times p,q = (1 - p)^k。那么在 nn 很大时, qnq^n 就非常接近 00。所以我们不妨将 qnq^n 当作 00,呢么答案就是 a1÷(1q)a_1 \div (1-q)

    我们发现,这个思路只能拿到 60 分。我们可以倒叙枚举女生,使用树状数组维护后 ii 个女生和前 jj 个男生配对的概率和,这一题就做完了。

    AC 代码

    #include<iostream>
    #include<cmath>
    #include<algorithm>
    #include<cstring> 
    #include<cstdio>
    using namespace std;
    typedef long long LL;
    const int MAXN = 1e6 + 10;
    const int INF = 0x3f;
    int n, m;
    struct TA{
    	double a[MAXN];
    	double sum(int p){
    		double res = 0;
    		for(;p;p-=(p&-p)){
    			res += a[p];
    		}
    		return res;
    	}
    	void modify(int p,double val){
    		p++;
    		for(;p<=n;p+=(p&-p)){
    			a[p] += val;
    		}
    	}
    }ta;
    struct Edge{
    	int u, v;
    	double p;
    	Edge(){}
    	Edge(int u,int v,double p):u(u),v(v),p(p){}
    }e[MAXN];
    bool cmp(Edge a,Edge b){
    	if(a.u != b.u)return a.u < b.u;
    	return a.v < b.v;
    } 
    double p;
    double powp[MAXN];
    int deg[MAXN], cnt[MAXN];
    int main()
    {
    	cin >> n >> m >> p;
    	for(int i = 0;i < m; i++){
    		int u, v;
    		cin >> u >> v;
    		u--;
    		v--;
    		deg[u]+=1;
    		e[i] = Edge(u, v, 0);
    	}
    	sort(e,e + m, cmp);
    	powp[0] = 1.0;
    	for(int i = 0;i < n; i++){
    		powp[i + 1] = powp[i] * (1 - p);
    	}
    	memset(cnt, 0, sizeof(cnt));
    	for(int i = 0;i < m; i++){
    		int u = e[i].u;
    		e[i].p = p * (powp[cnt[u]]) / (1 - powp[deg[u]]);
    		cnt[u] += 1;
    	}
    	reverse(e, e + m);
    	int pointer = 0;
    	double res = 0.0;
    	for(int i = n-1;i >= 0; i--){
    		for(int j = pointer;j < m && e[j].u == i; j++){
    			res += ta.sum(e[j].v) * e[j].p;
    		}
    		for(int j = pointer;j < m && e[j].u == i; j++){
    			ta.modify(e[j].v, e[j].p);
    			pointer = j + 1;
    		}
    	}
    	printf("%.2lf", res);
        return 0;
    }
    

    我的博客中观看:https://caijacky-note.blog.luogu.org/solution-p6089

    • 1

    信息

    ID
    1848
    时间
    1000ms
    内存
    256MiB
    难度
    9
    标签
    递交数
    7
    已通过
    7
    上传者