蓝桥杯C++大学B组一个月冲刺记录2024/3/21
蓝桥杯C++大学B组一个月冲刺记录2024/3/20
规则：每日三题
今日的题很简单┗|｀O′|┛ 嗷~~
1.奶酪
现有一块大奶酪，它的高度为 h
，它的长度和宽度我们可以认为是无限大的，奶酪中间有许多半径相同的球形空洞。
我们可以在这块奶酪中建立空间坐标系，在坐标系中，奶酪的下表面为 z=0，奶酪的上表面为 z=h。
现在，奶酪的下表面有一只小老鼠 Jerry，它知道奶酪中所有空洞的球心所在的坐标。
如果两个空洞相切或是相交，则 Jerry 可以从其中一个空洞跑到另一个空洞，特别地，如果一个空洞与下表面相切或是相交，Jerry 则可以从奶酪下表面跑进空洞；如果一个空洞与上表面相切或是相交，Jerry 则可以从空洞跑到奶酪上表面。
位于奶酪下表面的 Jerry 想知道，在不破坏奶酪的情况下，能否利用已有的空洞跑到奶酪的上表面去?
并查集
dfs或者bfs暴搜也可以，我甚至觉得二维化，区间合并也有道理
#include<iostream>
#include<vector>using namespace std;const int N = 1e3 + 10;struct Node{int x,y,z;
}q[N];typedef long long LL;int f[N];int find(int x){if(f[x] != x) f[x] = find(f[x]);return f[x];
}int n,h,r;int main()
{int T;cin >> T;while(T--){cin >> n >> h >> r;for(int i = 0;i <= n + 1;++i) f[i] = i;for(int i = 1;i <= n;++i){int x,y,z;cin >> x >> y >> z;q[i] = {x,y,z};if(abs(z) <= r) f[find(i)] = find(0);if(abs(z - h) <= r) f[find(i)] = find(n + 1);}for(int i = 1;i <= n;++i){for(int j = 1;j < i;++j){LL dx = abs(q[i].x - q[j].x);LL dy = abs(q[i].y - q[j].y);LL dz = abs(q[i].z - q[j].z);if(dx * dx + dy * dy + dz * dz <= 4 * (LL) r * r) f[find(i)] = find(j);}}if(find(0) == find(n + 1)) cout << "Yes" << endl;else cout << "No" << endl;}return 0;}
2.合并集合
一共有 n个数，编号是 1∼n，最开始每个数各自在一个集合中。
现在要进行 m个操作，操作共有两种：
M a b，将编号为 a 和 b的两个数所在的集合合并，如果两个数已经在同一个集合中，则忽略这个操作；
Q a b，询问编号为 a和 b的两个数是否在同一个集合中；
（并查集模板题）
并查集
#include<iostream>using namespace std;const int N = 1e5 + 10;int f[N];int find(int x){if(f[x] != x) f[x] = find(f[x]);return f[x];
}int n,m;int main(){cin >> n >> m;for(int i = 1; i <= n;++i) f[i] = i;while(m--){char c;int x,y;cin >> c >> x >> y;if(c == 'M'){x = find(f[x]);y = find(f[y]);f[x] = y;}else{x = find(f[x]);y = find(f[y]);if(x == y) cout << "Yes" << endl;else cout << "No" << endl;}}return 0;
}
3. 连通块中点的数量
给定一个包含 n 个点（编号为 1∼n）的无向图，初始时图中没有边。
现在要进行 m 个操作，操作共有三种：
C a b，在点 a 和点 b 之间连一条边，a 和 b 可能相等；
Q1 a b，询问点 a 和点 b 是否在同一个连通块中，a 和 b 可能相等；
Q2 a，询问点 a 所在连通块中点的数量；
（并查集模板题2之查询连通块的数量）
并查集
#include<iostream>using namespace std;const int N = 1e5 + 10;int n,m;int f[N];
int cnt[N];int find(int x){if(f[x] != x) f[x] = find(f[x]);return f[x];
}int main(){cin >> n >> m;for(int i = 1;i <= n;++i){f[i] = i;cnt[i] = 1;}while(m--){string c;cin >> c;int x,y;if(c == "C"){cin >> x >> y;x = find(f[x]);y = find(f[y]);if(x != y){f[x] = y;cnt[y] += cnt[x];}}if(c == "Q1"){cin >> x >> y;x = find(f[x]);y = find(f[y]);if(x != y) cout << "No" << endl;else cout << "Yes" << endl;}if(c == "Q2"){cin >> x;x = find(f[x]);cout << cnt[x] << endl;}}return 0;}