题解：P10907 [蓝桥杯 2024 国 B] 蚂蚁开会

一道数学和哈希表的结合。

要在所有整数交点上建会议中心，直接求出这么多线段的交点再判断是否为整点显然不优，正难则反，直接把所有线段上的整点存到一个数组里，判断这个点的出现次数，如果大于等于

2

，就是两条或多条线段的交点。

自然想到使用哈希表进行维护。

CPP

const int t = 2e6+7;
struct hash_map{ //哈希表 
    struct data{
        long long u;
        int v,nex;
    };
    data e[t << 1];
    int h[t],cnt;
    int hash(long long u){
        return (u % t + t)% t;
    }
    int& operator[](long long u){
        int hu = hash(u);
        for(int i = h[hu];i;i = e[i].nex){
            if(e[i].u == u) return e[i].v;
        }
        e[++cnt]=data{u, 0, h[hu]};
        h[hu] = cnt;
        return e[cnt].v;
    }
    hash_map(){
        cnt = 0;
        memset(h, 0, sizeof(h));
    }
};

创建了一个哈希表，并保证对于所有没有存过值的键，它们的初始值都为

0

。

那么如何求出每条线段上的整点？

这里需要一点数学方法。可以把两点组成的线段看为一个向量，那么只需求出它的单位向量，再将这个向量分解到 x 轴和 y 轴上。这样，我们每走一个单位步长，就可以到一个新的整点。代码如下：

CPP

int delx = c-a;
int dely = d-b;
int k = __gcd(abs(delx), abs(dely));
int xs = delx/k; //遍历线段上的所有整点
int ys = dely/k;

那么后面的步骤显然，将每个点的横坐标与纵坐标拟合成一个哈希值存入即可。

接下来遍历哈希表，找到出现次数大于等于

2

的点的个数。

完整代码如下：

CPP

#include<bits/stdc++.h>
using namespace std;
const int t = 2e6+7;
struct hash_map{//哈希表 
    struct data{
        long long u;
        int v,nex;
    };
    data e[t << 1];
    int h[t],cnt;
    int hash(long long u){
        return (u % t + t)% t;
    }
    int& operator[](long long u){
        int hu = hash(u);
        for(int i = h[hu];i;i = e[i].nex){
            if(e[i].u == u) return e[i].v;
        }
        if(cnt >= (t << 1) -1){//避免数字过大越界 
            static int q = 0;
            return q; 
        }
        e[++cnt] = data{u, 0, h[hu]};
        h[hu] = cnt;
        return e[cnt].v;
    }
    hash_map(){
        cnt=0;
        memset(h, 0, sizeof(h));
    }
};
hash_map nump;
int n,a,b,c,d,cnt;
int main() {
    cin>>n;
    for(int i = 0;i < n;i++){
        cin>>a>>b>>c>>d;
        int delx = c-a;
        int dely = d-b;
        int k = __gcd(abs(delx), abs(dely));
        int xs = delx/k;//遍历线段上的所有整点
        int ys = dely/k;
        for(int j = 0;j <= k;j++){
            long long x = a+j*xs;
            long long y = b+j*ys;
            const long long m = 1e9+7;
            long long r = x * m + y;//组合坐标作为哈希表的键 
            nump[r]++;
        }
    }
    for(int i = 0;i < t;i++){//统计重复出现的点 
        for(int j = nump.h[i];j;j = nump.e[j].nex){
        	nump.e[j].v >= 2?cnt++:cnt;
        }
    }
    cout<<cnt<<endl;
    return 0;
}

题解：P10907 [蓝桥杯 2024 国 B] 蚂蚁开会

文章操作

相关推荐

评论

题解：P10907 [蓝桥杯 2024 国 B] 蚂蚁开会