2022杭电多校第一场 1004 Ball

题目链接

Ball

题目大意

题目给定我们二维平面上的$n$个点，横纵坐标均不超过$100000$，问我们从中选出三个点，三个点构成的三条边中距离的中位数是素数的方案数是多少？

题解

直接枚举三个点，势必会TLE；所以我们考虑把所有边都构建出来，时间复杂度$O(n^2)$，然后按照边的大小从小到大排序，然后依次枚举每条边，如果当前边是质数，假设当前边的两个端点为$a$ 和 $b$，我们需要知道连接$a$的边比当前边权值小的个数，连接$b$的边比当前边权值大的个数；同理反过来也要求一下。直接枚举不太行，我们考虑使用$bitset$进行优化，$p[i]$表示有哪些点到$i$点的距离小于等于当前边，枚举边的过程中维护即可。最终时间复杂度$O(n^{2}log(n^2))$。

代码

#include<iostream>
#include<cstring>
#include<bitset>
#include<algorithm>
using namespace std;
#define int long long
const int maxn = 2010, M = 200010;
#define x first
#define y second
typedef pair<int,int> PII;
PII a[maxn];
bool st[M];
int primes[M], cnt;
typedef struct node
{
    
    int a, b, c;
    bool operator < (const struct node &w) const {
    
        return c < w.c;
    }
}Node;
Node edges[maxn * maxn];
bitset<maxn> p[maxn];
int n, m;
void init(int n)
{
    
    for(int i = 2; i <= n; i ++){
    
        if(!st[i]) primes[cnt ++] = i;
        for(int j = 0; primes[j] <= n / i; j ++){
    
            st[primes[j] * i] = true;
            if(i % primes[j] == 0) break;
        }
    }
}
int get_dist(PII a, PII b)
{
    
    return abs(a.x - b.x) + abs(a.y - b.y);
}
signed main()
{
    
    init(200000);
    st[1] = true;
    int t; cin >> t;
    while(t --){
    
        for(int i = 0; i < maxn; i ++) p[i].reset();
        cin >> n >> m;
        for(int i = 1; i <= n; i ++) cin >> a[i].x >> a[i].y;
        int k = 0;
        for(int i = 1; i <= n; i ++){
    
            for(int j = i + 1; j <= n; j ++){
    
                edges[k ++] = {
    i, j, get_dist(a[i], a[j])};
            }
        }
        int res = 0;
        sort(edges, edges + k);
        for(int i = 0; i < k; i ++){
    
            int a = edges[i].a, b = edges[i].b, c = edges[i].c;
            if(!st[c]) res += (p[a] ^ p[b]).count();
            p[a][b] = 1, p[b][a] = 1;
        }
        cout << res << endl;
    }
    return 0;
}