hdu5481 Desiderium

时间：2024-01-11 11:47:44

  1. 链接

    Desiderium

  2. 题意

    　　给定n条线段,从中选取若干条,共有2n种选法(因为每一条线段有两种方法:选或者不选).

    　　每一种选法都对应一个长度,也就是所选线段的并集长度.

    　　求这2n种选法长度之和.

  3. 解法:

    把这n条线段进行离散化,使得任意一条线段都可以由若干条元线段组成.

    什么叫元线段呢?把全部的x坐标进行排序,去重,就得到了很多元线段.

    统计每条元线段出现的次数,也就是说它被这n条线段里面的多少个线段覆盖.

    如合统计呢?假设元线段被m条线段覆盖,那么有n-m条线段不覆盖它.

    所以,该元线段被2n种选法中的2n-2n-m种选法覆盖.

    ans=累加(元线段的长度*元线段使用的次数).

  4. 写法:

    主要是如何统计元线段出现的次数.

    • 建立线段树,把没一条线段进行插入O(nlgn)
    • 树状数组O(nlgn)
    • 普通数组O(n),这种方法最好,不仅简单,而且快.

  5. 代码(树状数组版):

    #include<iostream>
#include<string.h>
#include<stdio.h>
#include<math.h>
#include<stdlib.h>
#include<algorithm>
using namespace std;
#define re(i,n) for(int i=0;i<n;i++)
typedef long long ll;
const int maxn = 1e5 + 7;
const int mod = 1e9 + 7;
int n;
struct Re{
	int l, r;
}a[maxn];
int x[maxn << 1], xi;
int tr[maxn << 1];
#define lson(x) x<<1,f,mid
#define rson(x) x<<1|1,mid+1,r
int lowbit(int x){
	return x&-x;
}
void ins(int x, int v){
	for (int i = x; i > 0; i -= lowbit(i)){
		tr[i] += v;
	}
}
int query(int x){
	int ans = 0;
	for (int i = x; i < xi; i += lowbit(i)){
		ans += tr[i];
	}
	return ans;
}
int data[maxn];
int f(int m){
	return data[n] - data[n - m];
}
void init(){
	data[0] = 1;
	re(i, maxn - 2){
		data[i + 1] = ((ll)data[i] << 1) % mod;
	}
}
int cnt[maxn << 1];
int main(){
	//freopen("in.txt", "r", stdin);
	init();
	int T; cin >> T;
	while (T--){
		scanf("%d", &n);
		xi = -1;
		re(i, n){
			scanf("%d%d", &a[i].l, &a[i].r);
			x[++xi] = a[i].l, x[++xi] = a[i].r;
		}
		++xi;
		sort(x, x + xi);
		xi = unique(x, x + xi) - x;
		memset(tr, 0, sizeof(tr));
		re(i, n){
			int beg = lower_bound(x, x + xi, a[i].l) - x;
			int over = lower_bound(x, x + xi, a[i].r) - x;
			ins(beg, -1), ins(over, 1);
		}
		cnt[0] = 0;
		for (int i = 1; i < xi; i++)cnt[i] = query(i);
		//re(i, xi)printf("(%d,%d) ", i, cnt[i]);
		//puts("");
		ll ans = 0;
		re(i, xi - 1){
			ll len = (ll)x[i + 1] - x[i];
			int ge = cnt[i + 1];
			//cout << len << " " << ge << endl;
			ans = (len*f(ge) + ans) % mod;
		}
		if (ans < 0)ans += mod;
		printf("%lld\n", ans);
	}
	return 0;
}

  6. 代码(普通数组版):

     #include<iostream>
 #include<algorithm>
 #include<stdio.h>
 using namespace std;
 typedef long long ll;
 #define re(i,n) for(int i=0;i<n;i++)
 ;
 ;
 struct Node{
     int l, r;
 }a[maxn];
 int n;
 ], xi;
 ];
 int data[maxn];
 void init(){
     data[] = ;
     ; i < maxn-; i++){
         data[i] = (data[i - ] << ) % mod;
     }
 }
 int main(){
     //freopen("in.txt", "r", stdin);
     int T; cin >> T;
     init();
     while (T--){
         scanf("%d", &n);
         xi = -;
         re(i, n)scanf("%d%d", &a[i].l, &a[i].r), x[++xi] = a[i].l, x[++xi] = a[i].r;
         sort(x, x + xi + );
         xi = unique(x, x + xi + ) - x;
         re(i, xi)cnt[i] = ;
         re(i, n){
             int f = lower_bound(x, x + xi, a[i].l) - x,
                 t = lower_bound(x, x + xi, a[i].r) - x;
             cnt[t]++, cnt[f]--;
         }
         ; i >= ; i--){
             cnt[i] += cnt[i + ];
         }
         ll ans = ;
         re(i, xi-){
             ] - x[i];
             ];
             ans = (ans + (ll)len*(data[n] - data[n - m])) % mod;
         }
         )ans += mod;
         printf("%lld\n", ans);
     }
     ;
 }

相关文章