題目鏈接：http://acm.hdu.edu.cn/showproblem.php?pid=5481

題解：

實際上求的是所有子集的并集長度之和。

把坐標離散化之后，可以單獨考慮每一段區間在并集內部的出現次數，如果有m個大區間覆蓋這段小區間，就會發現當且僅當這m個區間都不在子集中時，這一小段區間不會成為并集的一部分，所以一共有2?n??2?n?m??個子集包含這段小區間。把長度乘以出現次數即可。

總結：

1、出現區間計數或者區間并的時候，如果簡單的話可以直接求；

2、如果題目復雜， 可以先算出每一段小區間的貢獻，再累加。

#include<iostream> #include<cstdio> #include<cstring> #include<algorithm> using namespace std;typedef long long LL; const int maxn = 100005; const int mod = 1e9+7; struct Segment {int x,f; }seg[maxn<<1]; int n,tot; LL p[maxn];bool cmp(Segment a,Segment b) {if(a.x == b.x) return a.f > b.f;return a.x < b.x; }int main() {int t,l,r;scanf("%d",&t);p[0] = 1;for(int i = 1; i <= maxn; i++) p[i] = p[i-1] * 2 % mod;while(t--){tot = 0;scanf("%d",&n);for(int i = 1; i <= n; i++){scanf("%d%d",&l,&r);seg[tot].x = l;seg[tot++].f = 1;seg[tot].x = r;seg[tot++].f = -1;}sort(seg,seg+tot,cmp);int cnt = 0;LL ans = 0;for(int i = 0; i < tot; i++){if(cnt > 0)ans = (ans + (seg[i].x - seg[i-1].x) * (p[n] - p[n-cnt] + mod) % mod) % mod;cnt += seg[i].f;}printf("%lld\n",ans);}return 0; }

總結

以上是生活随笔為你收集整理的hdu 5481(数学期望+区间合并)的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。