1 条题解
-
0蔡竣凯 LV 6 @ 2022-4-18 20:00:23
首先,我们可以利用等比数列求和公式,因为 ,删去分子上的 算出每对男女 在一起的概率。询问时倒序插入并用树状数组维护。
比如对一个女生 ,有 个候选男生编号为 至 。那么对于第 个男生, 在一起的概率就是
我们不妨先利用等比数列求和公式:
其中, 。那么在 很大时, 就非常接近 。所以我们不妨将 当作 ,呢么答案就是 。
我们发现,这个思路只能拿到 60 分。我们可以倒叙枚举女生,使用树状数组维护后 个女生和前 个男生配对的概率和,这一题就做完了。
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; }
- 1
信息
- ID
- 1848
- 时间
- 1000ms
- 内存
- 256MiB
- 难度
- 9
- 标签
- 递交数
- 7
- 已通过
- 7
- 上传者