hdu 5481(数学期望+区间合并)
标签： hdu 5481(数学期望+区间合并) 博客 51CTO博客
2023-05-29 18:24:14 187浏览
hdu 5481(数学期望+区间合并)，题目链接：http://acm.hdu.edu.cn/showproblem.php?pid=5481题解：实际上求的是所有子集的并集长度之和。把坐标离散化之后，可以单独考虑每一段区间在并集内部的出现次数，如果有m个大区间覆盖这段小区间，就会发现当且仅当这m个区间都不在子集中时 −2 n−m 个子集包含这段小区间。把长度乘以出现次数
题目链接：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;
}
好博客就要一起分享哦！分享海报
此处可发布评论
评论（0）展开评论
暂无评论，快来写一下吧
展开评论
您可能感兴趣的博客
