[Luogu 3958] NOIP2017 D2T1 奶酪-白红宇

[Luogu 3958] NOIP2017 D2T1 奶酪

阅读量：5013 次

发布时间：2019-06-12

本文共 2434 字，大约阅读时间需要 8 分钟。

人生第一篇题解，多多关照吧。

注意事项：

1.多组数据，每次要先初始化。

2.因为涉及到开根，所以记得开double。

整体思路：

建图，判断「起点」与「终点」是否连通。

方法可选择搜索（我写的BFS）或并查集（UFS）。

首先，读入时记录这些球的最小高度和最大高度，如果最低的球与底面相离，或是最高的球与顶面相离，直接Pass。

我们会发现，可能不止一个球与底面相切或相交，也可能不止一个球与顶面相切或相交。

这就是说，起点和终点都可能不止一个，这给我们操作造成了一些麻烦（然而考场上我就这么硬搜的居然AC了）。

其实，通过建立「超级起点」和「超级终点」，可以把操作变得简单——用结构体数组的第0个元素表示「超级起点」，第n+1个元素表示「超级终点」。

两种方法都需要进行的预处理操作：

对于每一组球(i,j)，计算两球球心距离是否小于半径×2。

走一遍所有的球，如果当前球可以做起点，就连上当前球和超级起点；终点亦然。

方法1——BFS：

用二维bool数组e[i][j]记录i能否到达j，相当于存图（链式前向星也可以的，只是本题数据范围没有必要）。

对于每一个球，依次判断其能否到达0..n+1，当「超级终点」已被访问或队列已为空时结束搜索。

如果「超级终点」被访问过说明搜到了，可以到达；否则无法到达。

#include 
    
     #include 
     
      #include 
      
       #include 
       
        #include 
        
         using namespace std;const int MAXN=1010;bool vis[MAXN],e[MAXN][MAXN];double h,r,low,high;int T,n;struct ball{    double x,y,z;}s[MAXN];double dis(ball a,ball b){    double t1=a.x-b.x,t2=a.y-b.y,t3=a.z-b.z;    return sqrt(t1*t1+t2*t2+t3*t3);}void Init()//一定记得初始化{    low=h,high=0;    memset(vis,0,sizeof vis);    memset(e,0,sizeof e);}void Pre()//预处理{    for(int i=1;i<=n;++i)    {        if(s[i].z-r<=0)//超级起点            e[0][i]=e[i][0]=1;        if(s[i].z+r>=h)//超级终点            e[n+1][i]=e[i][n+1]=1;    }    for(int i=1;i

q; q.push(0); vis[0]=1; while(!vis[n+1] && !q.empty())//超级终点被搜到了，或队列已空 { int x=q.front(); q.pop(); for(int i=0;i<=n+1;++i) if(!vis[i] && e[x][i]) { q.push(i); vis[i]=1; } }}int main(int argc,char *argv[]){ scanf("%d",&T); while(T--) { scanf("%d %lf %lf",&n,&h,&r); Init();//初始化 for(int i=1;i<=n;++i) { scanf("%lf %lf %lf",&s[i].x,&s[i].y,&s[i].z); low=min(low,s[i].z),high=max(high,s[i].z);//记录最小和最大高度 } if(low-r>0 || high+r

方法2——UFS：

预处理时，如果两个球可以相连，就合并这两个球所在的UFS。

最终判断0和n+1两个球是否属于同一UFS，是则Yes，否则No。

并查集写法的代码更新于 2018.05.27，在一次水模拟赛中，原题写炸，遂重写，以前的代码风格是什么玩意！

#include 
    
     #include 
     
      #include 
      
       using std::max;using std::min;const int MAXN=1010;double h,r;int T,n;struct Ball{    double x,y,z;    void Read(void)    {        scanf("%lf %lf %lf",&x,&y,&z);    }    friend double Dist(const Ball &a,const Ball &b)    {        double x=a.x-b.x,y=a.y-b.y,z=a.z-b.z;        return sqrt(x*x+y*y+z*z);    }    bool operator <(const Ball &rhs) const    {        return z
       
        =h)                    Merge(i,n+1);            }            for(int i=1;i
        
         0 || high+r

/*想象一下我打完这篇文章后把文中所有的「点」一个个改成「球」*/

NOIP2017唯一AC的一道题啊。

转载于:https://www.cnblogs.com/Capella/p/7978928.html

你可能感兴趣的文章