开始复习
本周开始复习之前所学知识点，尝试刷些历年题目，加强对所学知识的理解。
历经磨难，终成正果
- 这是一道最近刷的最崩溃的一道题；
- 这是一道经过3天连续奋战终于AC的题；
- 这是一道历经7小时战斗才AC的题；
- 这是一道让我感受到作为OIer选手坚持与执着，永不放弃的精神, 向优秀的OIer选手学习！ 2017-chess01
历经磨难原因分析
- 最早是思路有一半是错误，不能单独计算洞连通起来的高度，因为如果没有洞通向底面和顶面一定是会输出No的
- 后来每个节点的根节点没有初始化，故错误
- 最后提醒一句：不开long long见祖宗！
题目：[NOIP2017 提高组] 奶酪
题目原文请移步下面的链接
- https://www.luogu.com.cn/problem/P3958
- 参考题解：https://www.luogu.com.cn/problem/solution/P3958
- 标签：
并查集、DFS、BFS
题解
思路
- 题解大家可移步看这里，很多童鞋写了各种解法
- https://www.luogu.com.cn/problem/solution/P3958
代码：并查集
代码语言：javascript复制#include <bits/stdc .h>
using namespace std;
#define endl 'n';
struct edge {
long long k, x, y, z;
};
struct UF {
vector<edge> fa;
vector<int> c;
vector<int> s;
UF(int n) :
fa(n 1), c(n 1), s(n 1) {}
bool dis(edge a, edge b, long long r) {
if (pow(a.x - b.x, 2) pow(a.y - b.y, 2) pow(a.z - b.z, 2) <= 4 * r * r) {
return true;
} else {
return false;
}
}
long long Find(long long a) {
if (a != fa[a].k) { //如果a的父节点不是本身，就往前找到其祖宗节点
fa[a].k = Find(fa[a].k); //往回返的时候把路上遍历过的所有节点更新为祖宗节点
}
return fa[a].k;
}
void Union(edge x, edge y, long long r) {
long long a = Find(x.k);
long long b = Find(y.k); //找到两个数的祖宗节点
if (a != b && dis(x, y, r)) {
fa[b].k = a; //合并时只改其祖宗节点
}
}
bool tf(int b, int d) {
for (int i = 1; i <= b; i) {
for (int j = 1; j <= d; j) {
if (Find(c[i]) == Find(s[j])) {
return true;
}
}
}
return false;
}
};
void best_coder() {
int t;
cin >> t;
for (int i = 0; i < t; i) {
int n, h;
long long r;
cin >> n >> h >> r;
UF uf(n);
int cnt_1 = 0;
int cnt_2 = 0;
for (int j = 1; j <= n; j) {
uf.fa[j].k = j;
cin >> uf.fa[j].x >> uf.fa[j].y >> uf.fa[j].z;
if (uf.fa[j].z r >= h) {
cnt_1 ;
uf.c[cnt_1] = j;
}
if (uf.fa[j].z - r <= 0) {
cnt_2 ;
uf.s[cnt_2] = j;
}
for (int k = 1; k <= j; k) {
if (!uf.dis(uf.fa[j], uf.fa[k], r)) {
continue;
}
if (uf.dis(uf.fa[j], uf.fa[k], r)) {
uf.Union(uf.fa[j], uf.fa[k], r);
}
}
}
if (uf.tf(cnt_1, cnt_2)) {
cout << "Yes" << 'n';
} else {
cout << "No" << 'n';
}
}
}
void happy_coder() {
}
int main() {
// 提升cin、cout效率
ios::sync_with_stdio(false);
cin.tie(nullptr);
cout.tie(nullptr);
// 小码匠
best_coder();
// 最优解
// happy_coder();
// 返回
return 0;
}
END
