ABC 366E Manhattan Multifocal Ellipse

时间：2024-08-11 09:38:13浏览次数：13

标签：Multifocal ABC 个点距离 366E abs Manhattan

题意
给你N个在二位平面上的整点(即横纵坐标都为整数的点),以及一个距离阈值D，求有多少个整点(x,y)满足Σ(abs(x-x[i])+abs(y-y[i])),(1≤i≤N)

思路
题目显然是要要求某个点到给定的N个点的曼哈顿距离之和，但是如果强行枚举点，根据数据范围显然是不可以通过的。那么我们仔细思考一下曼哈顿距离的性质，观察可得我们其实可以把一个二维问题拆维到两个一维问题。我们可以通过O(NlogN)的复杂度以内求得某个点距离这N个点的纵向距离之和并进行储存。然后我们在以相同的方式求一遍横向距离之和，对于每一个横向距离之和，我们都可以找到纵向距离之和的一个区间，统计这个区间桶有多少个元素即可。注意这里的查询是维护的一个区间信息，如果强行暴力循环就O(N*N)了，所以我们可以通过权值线段树来维护这个查询。至于在一个维度上求一个点到其他N个点的距离之和，我是通过前缀和加二分进行维护，就推导出了某个神秘公式，具体的看代码吧。

代码
https://atcoder.jp/contests/abc366/submissions/56570362

标签：Multifocal,ABC,个点,距离,366E,abs,Manhattan
From： https://www.cnblogs.com/lulu7/p/18353109

ABC366-D 题解
三维前缀和板子。三维前缀和可以类似二维前缀和来做，先给一下二维前缀和数组的计算方法：\[sum_{i,j}=a_{i,j}+sum_{i-1,j}+sum_{i,j-1}-sum_{i-1,j-1}\]同样的，可以写出三维前缀和数组的计算方法：\[sum_{i,j,k}=a_{i,j,k}+sum_{i,j,k-1}+sum_{i,j-1,k}+sum_{i-1,j,k}-sum_{i,j-1,k......
ABC 366 题解
AtCoderBeginnerContest366题解：$Problem\hspace{2mm}A-Election\hspace{2mm}2$题目链接opinion:很显然，当一个人的票数大于等于$\lceil\frac{n}{2}\rceil$时此人一定当选。（或可理解为投票结果一定固定。）依次判断两人即可。code:#include<bits/stdc++......
ABC366
A[link](https://atcoder.jp/contests/abc366/tasks/abc366_a]判断一下少的那个人加上剩下的所有票是否会超过另一个人，如果超过，不确定，否则目前票多的必胜。神奇的代码#include<bits/stdc++.h>usingnamespacestd;signedmain(){ intn,a,b; cin>>n>>a>>b; i......
ABC201E Xor Distances 题解
ABC201EXorDistances题解题目大意给定一个带权树，求树上每两点的简单路径上的边权的异或和的和。形式化的，定义$dis(i,j)$为$i$到$j$的简单路径上的边权的异或和，求$\large\sum\limits_{i=1}^n\sum\limits_{j=i+1}^n\text{dis}(i,j)$。Solve令\(\largef(u)=......
[AGC036E] ABC String
又是一个逐步简化的模型，好烦了又不会做这种题了呜啊呜啊。首先相邻且相同的字符，我们可以缩在一起。不妨假设$c_a\leqc_b\leqc_c$，我们考虑逐步删除来达到三个字符相同的情况。按照$A$将整个字符串划分成若干段，每一段一定形如$BC$交错的情形。注意到中间字符串长......
ABC 365
赛时通过：A、B、C。赛后补题：D、E。A依题判断即可。#include<bits/stdc++.h>usingnamespacestd;inty;intmain(){ cin>>y; if(y%4!=0)cout<<365; if(y%4==0&&y%100!=0)cout<<366; if(y%100==0&&y%400!=0)cout<<365; if(y%400==0)......
AT_abc208_d 题解
题目传送门做完这道题后感觉对Floyd的理解更深了。根据题面要求，设$f(k,i,j)$表示从$i$到$j$的所有只经过$1\simk$的点的所有路径的最短距离。很明显$k$那一维是阶段，因为它描述了从$i$到$j$路径中的不同点，而我们就是根据这一条件来划分集合，这......
【题解】ABC365（A~E）
前四题30min切，然后T5死磕70min+几发小唐错，距离比赛结束还有16s交最后一发，AC了。目录A.LeapYear题目描述思路代码B.SecondBest题目描述思路代码C.TransportationExpenses题目描述思路代码D.AtCoderJanken3题目描述思路代码E.XorSigmaProblem题目描述思路代码A.Lea......
ABC349D题解
[ABC349D]DivideInterval题解传送门：luogu|atcoder题目简述给定非负整数$l$和$r$（$l<r$），令$S(l,r)$表示序列$(l,l+1,\ldots,r-2,r-1)$，其中包含从$l$到$r-1$的所有整数。此外，一个序列被称为“好序列”，当且仅当它可以表示为$S(2^ij,2^{i}(j+1))$，......
ABC349D题解
[ABC349D]DivideInterval题解传送门：luogu|atcoder题目简述给定非负整数$l$和$r$（$l<r$），令$S(l,r)$表示序列$(l,l+1,\ldots,r-2,r-1)$，其中包含从$l$到$r-1$的所有整数。此外，一个序列被称为“好序列”，当且仅当它可以表示为$S(2^ij,2^{i}(j+1))$，其中$i$和$j$......

ABC 366E Manhattan Multifocal Ellipse

相关文章

赞助商

阅读排行