【BZOJ4481】【JSOI2015】非诚勿扰
程序员文章站
2022-07-14 12:20:45
...
【题目链接】
【思路要点】
- 用等比数列求和公式求出每条边出现的概率。
- 对于每一条边,用树状数组统计与它交叉的边的出现概率和,计算答案即可。
- 时间复杂度\(O(NLogN)\)(\(N\),\(M\)同阶)。
【代码】
#include<bits/stdc++.h> using namespace std; const int MAXN = 500005; template <typename T> void chkmax(T &x, T y) {x = max(x, y); } template <typename T> void chkmin(T &x, T y) {x = min(x, y); } template <typename T> void read(T &x) { x = 0; int f = 1; char c = getchar(); for (; !isdigit(c); c = getchar()) if (c == '-') f = -f; for (; isdigit(c); c = getchar()) x = x * 10 + c - '0'; x *= f; } template <typename T> void write(T x) { if (x < 0) x = -x, putchar('-'); if (x > 9) write(x / 10); putchar(x % 10 + '0'); } template <typename T> void writeln(T x) { write(x); puts(""); } struct BinaryIndexTree { long double a[MAXN]; int n; void init(int x) { n = x; memset(a, 0, sizeof(a)); } void modify(int x, long double p) { x = n - x + 1; for (int i = x; i <= n; i += i & -i) a[i] += p; } long double query(int x) { x = n - x; long double ans = 0; for (int i = x; i >= 1; i -= i & -i) ans += a[i]; return ans; } } BIT; int n, m; long double p; vector <int> a[MAXN]; int main() { read(n), read(m); scanf("%Lf", &p); for (int i = 1; i <= m; i++) { int x, y; read(x), read(y); a[x].push_back(y); } BIT.init(n); long double ans = 0; for (int i = 1; i <= n; i++) { sort(a[i].begin(), a[i].end()); long double r = pow(1 - p, a[i].size()), x = p; for (unsigned j = 0; j < a[i].size(); j++) { long double tmp = x / (1 - r); ans += tmp * BIT.query(a[i][j]); BIT.modify(a[i][j], tmp); x *= 1 - p; } } printf("%.2Lf\n", ans); return 0; }