Watchmen

题意:有n (1 ≤ n ≤ 200 000) 个点,问有多少个点的开平方距离与横纵坐标的绝对值之差的和相等;

Codeforces Round #345 (Div. 1) A. Watchmen 模拟加点-LMLPHP = |x - x| + |y - y|.(|x|, |y| ≤ 10)

思路:开始想的是容斥原理,即按x,y分别排序,先计算同x的点,然后在计算同y的点,这时由于相同的点之间的连边已经算过了,这样就不能再算。并且同一个y的点中可以每个点有多个点,算是不好编码的(反正我敲了很久..WA了)

反思:上面的容斥原理是从总体的思路来考虑的,这道题的难点也就是不重不漏。那么我们就模拟题目输入来往平面加点即可;每次加入一个点时,看与其同x,y有多少个点,这时由于当前点加了两次所以减去即可;坐标值较大,用map表示即可;

时间复杂度O(n)

#include<bits/stdc++.h>
using namespace std;
typedef __int64 ll;
map<int,int> x,y;
map<pair<int,int>,int> mp; int main()
{
int n,x,y;
ll ans=;
scanf("%d",&n);
while(n--)
{
scanf("%d%d",&x,&y);
     ans += x[a] + y[b] - mp[MK(a,b)];
x[a]++;
y[b]++;
mp[MK(a,b)]++;
  }
   printf("%I64d\n",ans);
}
04-21 05:11