NOIP 2017 Day2 T1 奶酪
2018-06-17 21:26:43来源:未知 阅读 ()
Luogu题面
两天中唯一的良心题,然而我在考场上蜜汁 RE 成70...
做法应该很多,朴素做法应该有 并查集 和 搜索 ;
我打的 并查集,不过好像 DFS 快的一批;
思路很简单,就是把能连在一起的洞并成同一个集合;
最后要查询一下底面和顶面是否在同一集合中;
就完了(好裸啊然而我就是没AC)。
复杂度 O(n2×T)
AC代码如下,个人感觉还比较清晰(244 ms 2183 kb):
#include<bits/stdc++.h> #define m(a,b) memset(a,b,sizeof(a)) // 懒.. #define ll long long using namespace std; int f[1002]; struct _{ // 表示点的结构体 int x,y,z; }a[1002]; 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,0),m(f,0); } int main(){ int n,t,h,r; scanf("%d",&t); while(t--){ init(); scanf("%d%d%d",&n,&h,&r); for(int i=1;i<=n+1;i++) f[i]=i; // 0是底面,n+1是顶面 for(int i=1;i<=n;i++) scanf("%d%d%d",&a[i].x,&a[i].y,&a[i].z); sort(a+1,a+n+1,cmp); // 按 z 排序,加快速度 for(int i=1;i<n;i++) for(int j=i+1;j<=n&&a[j].z-(r<<1)<=a[i].z;j++) if(dis(a[i],a[j])<=r<<1) bing(i,j); // 将距离小于 2*r 的洞合并 for(int i=1;i<=n;i++) if(a[i].z<=r) bing(0,i); // 把洞和顶面、 for(int i=n;i>0;i--) if(a[i].z>=h-r) bing(i,n+1); // 底面合并 if(find(0)==find(n+1)) printf("Yes\n"); else printf("No\n"); } return 0; }
%%% 写 扫描线 的 Dalao %%%
By The_Seventh
2017-12-23 18:08:34
标签:
版权申明:本站文章部分自网络,如有侵权,请联系:west999com@outlook.com
特别注意:本站所有转载文章言论不代表本站观点,本站所提供的摄影照片,插画,设计作品,如需使用,请与原作者联系,版权归原作者所有
上一篇:C++中this指针的用法详解
下一篇:今天起开始写博客啦!
- windows7 + Qt(MSVC2017) + VS2019安装配置 2020-04-25
- 2020年04月10日UCF Local Programming Contest 2017 2020-04-10
- 津津的储蓄计划 NOIp提高组2004 2020-04-01
- 【做题笔记】[NOIOJ,非NOIp原题]装箱问题 2020-02-14
- CSP(noip)中的简单对拍写法 2019-10-25
IDC资讯: 主机资讯 注册资讯 托管资讯 vps资讯 网站建设
网站运营: 建站经验 策划盈利 搜索优化 网站推广 免费资源
网络编程: Asp.Net编程 Asp编程 Php编程 Xml编程 Access Mssql Mysql 其它
服务器技术: Web服务器 Ftp服务器 Mail服务器 Dns服务器 安全防护
软件技巧: 其它软件 Word Excel Powerpoint Ghost Vista QQ空间 QQ FlashGet 迅雷
网页制作: FrontPages Dreamweaver Javascript css photoshop fireworks Flash