NOIP 2017 Day2 T1 奶酪

luogu题面

两天中唯一的良心题，然而我在考场上蜜汁RE成70...

做法应该很多，朴素做法应该有 并查集 和 搜索；

我打的 并查集，不过好像 DFS 快的一批；

思路很简单，就是把能连在一起的洞并成同一个集合；

最后要查询一下底面和顶面是否在同一集合中；

就完了（好裸啊然而我就是没AC）。

复杂度O（n²×T）

AC代码如下，个人感觉还比较清晰（244 ms 2183 kb）：

#include<bits/stdc++.h>    // NOIP 可不敢这么写
#define m(a,b) memset(a,b,sizeof(a))    // 懒...
#define ll long long
using namespace std;
int f[];
struct _{    // 表示洞的结构体
    int x,y,z;
}a[];
inline bool cmp(_ a,_ b){    // 快排中用到
    return a.z<b.z;
}
inline ll q(ll x){    // 平方（还不是懒）
    return x*x;
}
inline double dis(_ a,_ b){    // 求两洞距离
    return (double)sqrt(q(a.x-b.x)+q(a.y-b.y)+q(a.z-b.z));
}
int find(int x){    // 并查集————查询
    if(f[x]==x) return x;
    return f[x]=find(f[x]);
}
void bing(int a,int b){    // 并查集————合并
    int x=find(a),y=find(b);
    f[x]=y;
}
inline void init(){    // 初始化，应付多组数据
    m(a,),m(f,);
}
int main(){
    int n,t,h,r;
    scanf("%d",&t);
    while(t--){
        init();
        scanf("%d%d%d",&n,&h,&r);
        for(int i=;i<=n+;i++) f[i]=i;    // 0是底面，n+1是顶面
        for(int i=;i<=n;i++) 
        scanf("%d%d%d",&a[i].x,&a[i].y,&a[i].z);
        sort(a+,a+n+,cmp);    // 预处理，按z排序，能加快速度
        for(int i=;i<n;i++)
            for(int j=i+;j<=n&&a[j].z-(r<<)<=a[i].z;j++)    // 当高度（z）之差大于 2*r 时跳出
                if(dis(a[i],a[j])<=r<<) bing(i,j);
        for(int i=;i<=n;i++) if(a[i].z<=r) bing(,i);    // 洞和两面之
        for(int i=n;i>;i--) if(a[i].z>=h-r) bing(i,n+);    // 间连边
        if(find()==find(n+)) printf("Yes\n");
        else printf("No\n");
    }
    return ;    // 庄严地结束程序...
}

%%% 写 扫描线 的 Dalao %%%

By The_Seventh——一个刚学了半年的高一蒟蒻

2017-12-2318:08:34