题目描述 现有一块大奶酪，它的高度为 h，它的长度和宽度我们可以认为是无限大的，奶酪中间有许多半径相同的球形空洞。我们可以在这块奶酪中建立空间坐标系， 在坐标系中，奶酪的下表面为 z =
展开全文
Jerry只是一只小老鼠，他不懂并查集，他只知道搜索......我们假设Jerry有着超强的运动能力，它能够爬遍每个奶酪空洞，除非它已经到达了奶酪顶部。于是，我们可以先把所有的奶酪底部的空洞找出来，再从这些空洞开始广度优先搜索，直到搜到顶部的空洞为止。既然空间内两点距离可以求出，两个空洞是否相连就是
展开全文
想过使用深度优先遍历，但是用优先遍历每次遍历都需要遍历每一个洞去查看是否存在与其相切或者相交的洞，付出的时间复杂度也挺大的。后来也可以想到使用并查集去求解，但遍历总是逃不掉的。又看到n的范围是1 ≤ n ≤ 1,000，所以两种方法都行。
并查集：将所有能都通过的洞组合到一个树里面，保持树的根
展开全文
链接
【NOIP2017】奶酪
写题之前就知道这是一道用并查集来解决的问题，所以脑海中一直在思考怎样才能用并查集。
第一个想法是将所有相交或相切的洞都并起来，在判断是否连通上表面与下表面。然而在代码实现的过程中，一是意识到了会有很多的集合，需要判断很多次，其次，并没有想到如何进行判断是否连通。
所以
展开全文
三种解法：bfs，dfs，并查集
方法一：bfs
两个点之间的距离如果小于等于2*r，那么这两个点可以相互到达。将所有可以互相到达的两个点之间连一条边。将所有与下表面相交的点入队，从这些点开始进行bfs搜索，对于每个搜索到的点进行判断：该点是否与上表面相交，若能找到与上表面相交的点，则输出yes，若
展开全文
这个题一看就是并查集的板子题。 记得在合并的时候开，不要开根号就行。 我当年考的时候是拿跑过去的。。。 附代码： #include<iostream>
#include<algorithm>
#include<cstdio>
#include<cstring
展开全文
奶酪
链接：https://ac.nowcoder.com/acm/contest/23156/1012
来源：牛客网
题目描述
现有一块大奶酪，它的高度为 h，它的长度和宽度我们可以认为是无限大的，奶酪中间有许多半径相同的球形空洞。我们可以在这块奶酪中建立空间坐标系， 在坐标系中，奶酪的下表面为
展开全文
链接：https://ac.nowcoder.com/acm/problem/16417
来源：牛客网
题目描述
现有一块大奶酪，它的高度为 h，它的长度和宽度我们可以认为是无限大的，奶酪中间有许多半径相同的球形空洞。我们可以在这块奶酪中建立空间坐标系， 在坐标系中
展开全文
预处理出所有可以相连的圆心（他们的圆可以相交或相接），并设置起点和终点，以及起点和终点可以相连的圆心，将所有相连的路径存储在二维数组中，数组下标代表相连两点圆心编号，接着从起点到终点进行深度搜索即可
#include<bits/stdc++.h>
using namespace std;
展开全文
-
扫描二维码，关注牛客
- 意见反馈
-
下载牛客APP，随时随地刷题
- 牛客竞赛，专业的竞技算法训练平台
-
扫描二维码，进入QQ群
扫码关注“比赛自动姬”
- 公司地址：北京市朝阳区北苑路北美国际商务中心K1座一层-北京牛客科技有限公司
- 联系方式：010-60728802 投诉举报电话：010-57596212（朝阳人力社保局）
- 牛客科技© All rights reserved admin@nowcoder.com
- 京ICP备14055008号-4 增值电信业务经营许可证 营业执照 人力资源服务许可证
-
京公网安备 11010502036488号
