题解：P3997 [SHOI2013] 扇形面积并

题意

将一个圆形分成

2m

个小扇形，在给出

n

个大扇形，第

i

个扇形半径为

r_i

。给上方的的扇形逆时针编号为正，下方顺时针编号为负，则大扇形就是覆盖了第

s_i

个小扇形转到到第

t_i

个扇形。求至少被

k

个大扇形覆盖的面积，设答案为

T

。则输出

T \times \frac{\pi}{2m}

。这里先给一张图。

解题

题意转换

首先，这里先看一下怎么算一个小扇形的覆盖面积。设半径为

r

。则面积为

\pi \times r^2 \times \frac{1}{2m} \times \frac{2m}{\pi} = r^2

。

我们可以将题目转换为每一个小扇形中，覆盖了这个小扇形的所有大扇形有

cnt

个。则这块小扇形的贡献就是其中半径第

cnt-k+1

大的大扇形在这块小扇形中的面积。也就是说因为需要求至少被

k

个大扇形覆盖的地方的面积，所以每块小扇形有了

k

个大扇形的覆盖之后就从半径最小的大扇形开始算。

思路

显然，每个大扇形都是连续的。那我们用一个树状数组，可以在某个地方把它加上，再在某个地方减去即可。因为要求第

cnt-k+1

大，所以对于每个大扇形，将它在它的半径的位置加或减

1

，然后使用树状数组倍增就行。

Code

CPP

#include<bits/stdc++.h>
#define int long long
using namespace std;
int n,k,m,ans,luozhi;
int c[3000000]; 
vector<int> tree[3000000];
int lowbit(int x){
	return x&(-x);
}
void change(int k,int x){
	for(int i=x;i<=100000;i+=lowbit(i))c[i]+=k;
}
int sum(int id){
	int x=0,k=0,y=0,cnt=0;
	for(int i=21;~i;i--){
		x=k+(1<<i);if(x>100000) continue;
		y=cnt+c[x];
		if(y<id)k=x,cnt=y;
	}
	return k+1;
}
signed main(){
	cin>>n>>m>>k;
	for(int i=1;i<=n;i++){
		int r,s,t;
		cin>>r>>s>>t,s+=m,t+=m;
		if(s<t){
			tree[s].push_back(-r);
			tree[t].push_back(r);
		}
		else{
			tree[m*2].push_back(r);
			tree[s].push_back(-r);
			tree[t].push_back(r);
		}
	}
	for(int i=2*m;i>=1;i--){
		for(int j=0;j<tree[i].size();j++){
			int e=tree[i][j];
			if(e>0)change(1,e),luozhi++;
			else change(-1,-e),luozhi--;
		}
		if(luozhi>=k)ans+=sum(luozhi-k+1)*sum(luozhi-k+1);
	}
	cout<<ans;
}

题解：P3997 [SHOI2013] 扇形面积并

文章操作

题意

解题

题意转换

思路

Code

相关推荐

评论

题解：P3997 [SHOI2013] 扇形面积并