AT_abc366_e Manhattan Multifocal Ellipse 题解

ABC 最水的一场。

题意#

给定二维平面上的 $N$ 个点 $(x_{1},y_{1})，(x_{2},y_{2})\ldots(x_{N},y_{N})$ 和非负整数 $D$ ，试求满足 $\sum_{i=1}^n(|x-x_{i}|,|y-y_{i}|) \le D$ 的整数对 $(x,y)$ 的个数。

解析#

需要满足的条件为 $\sum_{i=1}^n(|x-x_{i}|,|y-y_{i}|) \le D$ ，移项即得 $D-\sum_{i=1}^n{|x-x_i|} \geq \sum_{i=1}^n|y-y_i|$ 。

不妨枚举所有的 $x$ 与 $y$ ，并将其排序并记录，然后用双指针维护即可。理论二分也可行，未尝试。

赛时代码#

1
#include<bits/stdc++.h>
2
using namespace std;
3
typedef long long ll;
4
const ll N=1e6+10,M=(N<<2)+10;
5
ll n,d,i,j,t,s,ans,x[N],y[N],f1[M],f2[M],s1[M],s2[M];
6
int main(){
7
 cin>>n>>d;
8
 for(i=1;i<=n;i++)cin>>x[i]>>y[i],f1[(N<<1)+y[i]+1]++,f2[(N<<1)+y[i]-1]++;
9
 for(i=0;i<=M;i++)t+=f1[i],f1[i]=0,s+=t,s2[i]+=s;
10
 t=s=0;
11
 for(i=M;i>=0;i--)t+=f2[i],f2[i]=0,s+=t,s2[i]+=s;
12
 for(i=1;i<=n;i++)f1[(N<<1)+x[i]+1]++,f2[(N<<1)+x[i]-1]++;
13
 t=s=0;
14
 for(i=0;i<=M;i++)t+=f1[i],f1[i]=0,s+=t,s1[i]+=s;
15
 t=s=0;
16
 for(i=M;i>=0;i--)t+=f2[i],f2[i]=0,s+=t,s1[i]+=s;
17
 t=M;stable_sort(s1,s1+t+1);stable_sort(s2,s2+t+1);
18
 for(i=t;i>=0;i--){
19
  while(j<=t&&s1[i]+s2[j]<=d)j++;
20
  ans+=j;
21
 }
22
 cout<<ans;
23
}

Walter_Fang 的博客

AT_abc366_e Manhattan Multifocal Ellipse 题解

题意#

解析#

赛时代码#

支持与分享

评论区

目录