AT_abc402_d 题解

· · 题解

思路

首先可以发现转化，答案也就等于每个 i 与 j 的组合再减去平行的个数。即 \frac{n \times (n-1)}{2} 减去两条线相平行的个数。

接下来我们需要考虑如何去求这个东西。通过对样例解释的观察与一些手玩，可以发现 a_i，b_i 与 a_{i} + k，b_{i}-k 是平行的。k 是指一个能使上式大于 0 小于等于 n 的整数，可正可负。注意 k 不等于 0。

这就结束了吗？并没有。例如，如果 a_{i} + k 是大于 n 的，这并不代表它不成立。在一个环上，物极必反（感性理解一下）。到 n 后会跳到 1。所以 a_{i} + k 将会变成 a_{i} + k - n。

好麻烦！这不仅需要经过大量分讨，并且也没法在时间限制下实现。

进一步观察上式，如果从两对点的和入手，事情是不是就无比简单了？只有两种情况，两对点的和相等或差 n。

开一个 map，每次将 a_i + b_i 在 map 内加一下就行了。答案也很好求（详见代码）。

AC code

#include<bits/stdc++.h>
using namespace std;
long long n,m,sum;
map<long long,long long>ji;
int main(){
    scanf("%lld%lld",&n,&m);
    for(int i=1;i<=m;i++){
        long long a,b;
        scanf("%lld%lld",&a,&b);
        sum+=ji[a+b]+ji[a+b+n]+ji[a+b-n];//真的不会算重！因为边是按顺序加的。
        ji[a+b]++;
    }
    printf("%lld",m*(m-1)/2-sum);
}