郑州个人做网站,时尚wordpress免费主题下载,wordpress如何搭建,手机开发者选项怎么打开题意#xff1a;有n棵树在水平线上#xff0c;给出每棵树的坐标和高度#xff0c;然后向左倒的概率和向右倒的概率#xff0c;和为1#xff0c;然后给出了m个蘑菇的位置#xff0c;每一个蘑菇都有一个魔法值#xff0c;假设蘑菇被压死了#xff0c;也就是在某棵树[a[i]… 题意有n棵树在水平线上给出每棵树的坐标和高度然后向左倒的概率和向右倒的概率和为1然后给出了m个蘑菇的位置每一个蘑菇都有一个魔法值假设蘑菇被压死了也就是在某棵树[a[i] - h[i], a[i]) 或 (a[i], a[i] h[i]]范围内。魔法值就没有了。仅仅有生存下来的蘑菇才有魔法值问生存下来的蘑菇的魔法值的期望。 题解能够看到n和m的范围是1e5。而坐标范围是1e9。所以肯定要离散化然后更新每一个区间的概率值单点查询每一个蘑菇所在区间的概率值乘其魔法值。 #include cstdio
#include cstring
#include algorithm
#include map
using namespace std;
const int N 100005;
int n, m, a[N], h[N], b[N], z[N], c[N 2];
double tree[N 4], flag[N 4], pl[N], pr[N];
mapint, int mp;void pushdown(int k) {if (flag[k]) {tree[k * 2] * tree[k];tree[k * 2 1] * tree[k];flag[k * 2] flag[k * 2 1] 1;tree[k] 1.0;flag[k] 0;}
}void build(int k, int left, int right) {flag[k] 0;tree[k] 1.0;if (left ! right) {int mid (left right) / 2;build(k * 2, left, mid);build(k * 2 1, mid 1, right);}
}void modify(int k, int left, int right, int l1, int r1, double x) {if (l1 left right r1) {tree[k] * x;flag[k] 1;return;}pushdown(k);int mid (left right) / 2;if (l1 mid)modify(k * 2, left, mid, l1, r1, x);if (r1 mid)modify(k * 2 1, mid 1, right, l1, r1, x);
}double query(int k, int left, int right, int pos) {if (left right)return tree[k];pushdown(k);int mid (left right) / 2;if (pos mid)return query(k * 2, left, mid, pos);elsereturn query(k * 2 1, mid 1, right, pos);
}int main() {scanf(%d%d, n, m);mp.clear();int cnt 0;for (int i 1; i n; i) {scanf(%d%d%lf%lf, a[i], h[i], pl[i], pr[i]);pl[i] / 100.0, pr[i] / 100.0; c[cnt] a[i];c[cnt] a[i] - h[i];c[cnt] a[i] h[i];}for (int i 1; i m; i) {scanf(%d%d, b[i], z[i]);c[cnt] b[i];}sort(c 1, c 1 cnt);cnt unique(c 1, c 1 cnt) - (c 1);for (int i 1; i cnt; i)mp[c[i]] i;build(1, 1, cnt);for (int i 1; i n; i) {modify(1, 1, cnt, mp[a[i] - h[i]], mp[a[i]] - 1, 1.0 - pl[i]);modify(1, 1, cnt, mp[a[i]] 1, mp[a[i] h[i]], 1.0 - pr[i]);}double res 0;for (int i 1; i m; i)res z[i] * query(1, 1, cnt, mp[b[i]]);printf(%lf\n, res);return 0;
} 转载于:https://www.cnblogs.com/llguanli/p/7401510.html
