题解：P14233 [COI 2011] 收视率 / TELKA

发现平均值等于区间和除以区间长度，而每个居民可以看作一个区间，然后就发现就是区间增加

1

，区间求和，考虑线段树，是个模板。

但是题目中存在这样一句话：“需注意，部分居民可能在前一天深夜开始观看电视（例如

23:45:30

），并在次日结束观看（例如

01:15:00

）。”

然后我们考虑将这些区间分成两块，一块是前一天，一块是后一天，然后问询的区间也可以分成两块。

最后一个难点是时间处理，我发现中间的冒号和杠是不会被整型变量读入，只会被字符变量读入的，于是我采用整型数和标志符分离的方式，具体可以看代码。我将一个时间哈希了一下，变成

H \times 60^2+M \times 60+S

，这样保证不产生哈希冲突。

代码：

CPP

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const ll N=300009,INF=2e9;
ll n,m,MOD;
struct Segment{
	ll l;
	ll r;
	ll len;
	ll sum;
	ll toAdd;
};
Segment tr[N*4];
void build(ll u,ll l,ll r){
	if(l==r){
		tr[u]=(Segment){l,r,r-l+1,0,0};
		return;
	}
	ll m=(l+r)/2; 
	build(u*2,l,m);
	build(u*2+1,m+1,r);
	tr[u]=(Segment){l,r,r-l+1,tr[u*2].sum+tr[u*2+1].sum,0};
}
void pushdown(ll u){
	if(tr[u].l==tr[u].r) return;
	ll A=tr[u].toAdd;
	tr[u].toAdd=0;
	tr[u*2].sum+=tr[u*2].len*A;
	tr[u*2+1].sum+=tr[u*2+1].len*A;
	tr[u*2].toAdd+=A;
	tr[u*2+1].toAdd+=A;
}
void add(ll u,ll l,ll r,ll delta){
	pushdown(u);
	if(r<tr[u].l||tr[u].r<l) return;
	if(l<=tr[u].l&&tr[u].r<=r){
		tr[u].toAdd+=delta;
		tr[u].sum+=tr[u].len*delta;
		return;
	}
	add(u*2,l,r,delta);
	add(u*2+1,l,r,delta);
	tr[u].sum=tr[u*2].sum+tr[u*2+1].sum;
}
ll rsq(ll u,ll l,ll r){
	pushdown(u);
	if(r<tr[u].l||tr[u].r<l) return 0;
	else if(l<=tr[u].l&&tr[u].r<=r) return tr[u].sum;
	return rsq(u*2,l,r)+rsq(u*2+1,l,r);
}
int main(){
	ll n;
	cin>>n;
	build(1,1,86400);
	for(ll i=1;i<=n;i++){
		ll x,y,z,a,b,c;
		char op;
		cin>>x>>op>>y>>op>>z>>op>>a>>op>>b>>op>>c;
		ll l=x*3600+y*60+z;
		ll r=a*3600+b*60+c;
		l++;r++;
		if(l>r){
			add(1,l,86400,1);
			add(1,1,r,1);
		}
		else add(1,l,r,1); 
	}
	ll q;
	cin>>q;
	for(ll i=1;i<=q;i++){
		ll x,y,z,a,b,c;
		char op;
		cin>>x>>op>>y>>op>>z>>op>>a>>op>>b>>op>>c;
		ll l=x*3600+y*60+z;
		ll r=a*3600+b*60+c;
		l++;r++;
		if(l>r)
			cout<<fixed<<setprecision(10)<<((double)rsq(1,l,86400)+rsq(1,1,r))/(r+86400-l+1)<<endl;
		else
			cout<<fixed<<setprecision(10)<<((double)rsq(1,l,r))/(r-l+1)<<endl;
	}
	return 0;
}

题解：P14233 [COI 2011] 收视率 / TELKA

文章操作

相关推荐

评论

题解：P14233 [COI 2011] 收视率 / TELKA