Codeforces Round 345 (Div. 1)A. Watchmen（容斥原理）

本文主要是介绍Codeforces Round 345 (Div. 1)A. Watchmen（容斥原理），希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

A. Watchmen
当欧几里得距离和曼哈顿距离相等时，$x1==x2||y1==y2$
这两个条件满足其一。这和容斥原理一样，至少选择一个的条件。

我们可以计算xi，以及小于i之前的这些，这样可以保证只计算一次。
然后容斥一下计算答案。

#include <bits/stdc++.h> 
#define int long long
#define rep(i,a,b) for(int i = (a); i <= (b); ++i)
#define fep(i,a,b) for(int i = (a); i >= (b); --i)
#define pii pair<int, int>
#define pll pair<long long, long long>
#define ll long long
#define db double
#define endl '\n'
#define x first
#define y second
#define pb push_backusing namespace std;void solve()
{int n;cin>>n;map<int,int>cntx,cnty;map<pii,int>s;int ans=0,k=0;rep(i,1,n){int x,y;cin>>x>>y;ans+=cntx[x]+cnty[y]-s[{x,y}];cntx[x]++;cnty[y]++;s[{x,y}]++;}cout<<ans<<endl;
}signed main(){ios::sync_with_stdio(false); cin.tie(0); cout.tie(0);
//   	freopen("1.in", "r", stdin);int _;
//	cin>>_;
//	while(_--)solve();return 0;
}

这篇关于Codeforces Round 345 (Div. 1)A. Watchmen（容斥原理）的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---