【并查集专题】【蓝桥杯备考训练】：网络分析、奶酪、合并集合、连通块中点的数量、格子游戏【已更新完成】

2024-03-23 06:28
文章标签 训练 数量 更新 游戏 完成 蓝桥 合并 中点 集合 查集 连通 专题 备考 格子 网络分析 奶酪

本文主要是介绍【并查集专题】【蓝桥杯备考训练】：网络分析、奶酪、合并集合、连通块中点的数量、格子游戏【已更新完成】，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

目录

1、网络分析（第十一届蓝桥杯省赛第一场C++ A组/B组）

2、奶酪（NOIP2017提高组）

3、合并集合（模板）

4、连通块中点的数量（模板）

5、格子游戏（《信息学奥赛一本通》）

1、网络分析（第十一届蓝桥杯省赛第一场C++ A组/B组）

小明正在做一个网络实验。

他设置了 n 台电脑，称为节点，用于收发和存储数据。

初始时，所有节点都是独立的，不存在任何连接。

小明可以通过网线将两个节点连接起来，连接后两个节点就可以互相通信了。

两个节点如果存在网线连接，称为相邻。

小明有时会测试当时的网络，他会在某个节点发送一条信息，信息会发送到每个相邻的节点，之后这些节点又会转发到自己相邻的节点，直到所有直接或间接相邻的节点都收到了信息。

所有发送和接收的节点都会将信息存储下来。

一条信息只存储一次。

给出小明连接和测试的过程，请计算出每个节点存储信息的大小。

输入格式

输入的第一行包含两个整数 n,m，分别表示节点数量和操作数量。

节点从 1 至 n 编号。

接下来 m 行，每行三个整数，表示一个操作。

  • 如果操作为 1 a b，表示将节点 a 和节点 b 通过网线连接起来。当 a = b 时，表示连接了一个自环，对网络没有实质影响。
  • 如果操作为 2 p t，表示在节点 p 上发送一条大小为 t 的信息。
输出格式

输出一行，包含 n 个整数，相邻整数之间用一个空格分割，依次表示进行完上述操作后节点 1 至节点 n 上存储信息的大小。

数据范围

1≤n≤10000
1≤m≤1e5
1≤t≤100

输入样例1：
4 8
1 1 2
2 1 10
2 3 5
1 4 1
2 2 2
1 1 2
1 2 4
2 2 1
输出样例1：
13 13 5 3
思路：

连接的时候创建一个新的根节点，作为祖先（通过创建新节点，可以实现在之后的dfs中不会将之前的信息加到后连接的计算机上）

依次执行输入的指令，传达的信息都加到根节点上

dfs，把发送的信息全部累加到根节点上

遍历输出根节点的信息（如果对于节点i，p[i]==i则说明这是个根节点，不然说明这个根节点已经其点的子节点了）

代码：
#include<bits/stdc++.h>using namespace std;const int N=2e4+10,M=N<<1;int p[N];int h[M],e[M],ne[M],idx;int add(int a,int b)
{e[idx]=b;//值存到e里（idx是e的编号） ne[idx]=h[a];//d的编号的下一个指向h【a】指向的编号 h[a]=idx++;//h【a】指向b的编号 
}int f[N];//存储信息 int n,m;int find(int x)
{if(x!=p[x])p[x]=find(p[x]);return p[x];
}void merge(int a,int b,int &root)
{a=find(a);b=find(b);if(a!=b){p[a]=p[b]=root;add(root,a);add(root,b);root++;}
}void dfs(int son,int father)
{f[son]+=f[father];for(int i=h[son];i!=-1;i=ne[i]){int j=e[i];dfs(j,son);}
}int main()
{memset(h,-1,sizeof h);cin>>n>>m;for(int i=1;i<=n*2;i++){p[i]=i;}int root=n+1; while(m--){int t,a,b;cin>>t;cin>>a>>b;//cout<<"yes";//cout<<m<<endl;if(t==1){merge(a,b,root);}else{a=find(a);f[a]+=b;}//cout<<m<<endl;}//cout<<"yes1";for(int i=n+1;i<root;i++)if(p[i]==i)dfs(i,0);//把每个根节点的值传递到每个计算机上for(int i=1;i<=n;i++)cout<<f[i]<<" ";return 0;
}
/*4 8
1 1 2
2 1 10
2 3 5
1 4 1
2 2 2
1 1 2
1 2 4
2 2 113 13 5 3*/

2、奶酪（NOIP2017提高组）

现有一块大奶酪，它的高度为 h，它的长度和宽度我们可以认为是无限大的，奶酪中间有许多半径相同的球形空洞。

我们可以在这块奶酪中建立空间坐标系，在坐标系中，奶酪的下表面为 z=0，奶酪的上表面为 z=h。 

现在，奶酪的下表面有一只小老鼠 Jerry，它知道奶酪中所有空洞的球心所在的坐标。

如果两个空洞相切或是相交，则 Jerry 可以从其中一个空洞跑到另一个空洞，特别地，如果一个空洞与下表面相切或是相交，Jerry 则可以从奶酪下表面跑进空洞；如果一个空洞与上表面相切或是相交，Jerry 则可以从空洞跑到奶酪上表面。

位于奶酪下表面的 Jerry 想知道，在不破坏奶酪的情况下，能否利用已有的空洞跑到奶酪的上表面去? 

空间内两点 P1(x1,y1,z1)、P2(x2,y2,z2)的距离公式如下：

输入格式

每个输入文件包含多组数据。  

输入文件的第一行，包含一个正整数 T，代表该输入文件中所含的数据组数。  

接下来是 T组数据，每组数据的格式如下：

第一行包含三个正整数 n，h，和 r，两个数之间以一个空格分开，分别代表奶酪中空洞的数量，奶酪的高度和空洞的半径。  

接下来的 n 行，每行包含三个整数 x、y、z，两个数之间以一个空格分开，表示空洞球心坐标为 (x,y,z)。

输出格式

输出文件包含 T 行，分别对应 T 组数据的答案，如果在第 i 组数据中，Jerry 能从下表面跑到上表面，则输出 Yes，如果不能，则输出 No。

数据范围

1≤n≤1000
1≤h,r≤1e9
T≤20
坐标的绝对值不超过1e9

输入样例：
3 
2 4 1 
0 0 1 
0 0 3 
2 5 1 
0 0 1 
0 0 4 
2 5 2 
0 0 2 
2 0 4
输出样例：
Yes
No
Yes
思路：

多源dfs（推荐）

或者并查集

代码：

多源bfs

#include <bits/stdc++.h>
using namespace std;
int t, n, h, r, f[1010];
double x[1010], y[1010], z[1010];inline double dist(double X1, double X2, double Y1, double Y2, double Z1, double Z2) {return sqrt((X1 - X2) * (X1 - X2) + (Y1 - Y2) * (Y1 - Y2) + (Z1 - Z2) * (Z1 - Z2));
}int main() {scanf("%d", &t);while (t--) {scanf("%d%d%d", &n, &h, &r);for (int i = 1; i <= n; i++) scanf("%lf%lf%lf", &x[i], &y[i], &z[i]), f[i] = 0;queue<int> q; bool ok = 0;for (int i = 1; i <= n; i++) if (z[i] <= r) q.push(i), f[i] = 1;while (q.size()) {int p = q.front(); q.pop();if (ok) break;if (z[p] + r >= h) {ok = 1; puts("Yes"); break;}for (int i = 1; i <= n; i++) {if (f[i]) continue;if (dist(x[p], x[i], y[p], y[i], z[p], z[i]) <= 2 * r) {q.push(i), f[i] = 1;if (z[i] + r >= h) {ok = 1; puts("Yes"); break;}}}}if (!ok) puts("No");}return 0;
}

并查集：

#include <bits/stdc++.h>
using namespace std;
int t, n, h, r;
int t1, s1[1010], t2, s2[1010], fa[1010];
pair<long long, pair<long long, long long> > a[1010];int get(int x) {if (fa[x] != x) fa[x] = get(fa[x]);return fa[x];
}
double dist(double X1, double X2, double Y1, double Y2, double Z1, double Z2) {return sqrt(pow(X1 - X2, 2) + pow(Y1 - Y2, 2) + pow(Z1 - Z2, 2));
}int main() {scanf("%d", &t);while (t--) {scanf("%d%d%d", &n, &h, &r); t1 = 0, t2 = 0;for (int i = 1; i <= n; i++) fa[i] = i;for (int i = 1; i <= n; i++) {scanf("%lld%lld%lld", &a[i].second.first, &a[i].second.second, &a[i].first);if (a[i].first + r >= h) s1[++t1] = i;if (a[i].first - r <= 0) s2[++t2] = i;}if (t1 == 0 || t2 == 0) {puts("No"); continue;}for (int i = 1; i <= n; i++)for (int j = i + 1; j <= n; j++) {if (get(i) == get(j)) continue;double d = dist(a[i].second.first, a[j].second.first, a[i].second.second, a[j].second.second, a[i].first, a[j].first);if (d <= 2 * r) fa[get(i)] = get(j);}int b = 0;for (int i = 1; i <= t1; i++) {if (b) break;for (int j = 1; j <= t2; j++)if (get(s1[i]) == get(s2[j])) {puts("Yes"); b = 1; break;}}if (!b) puts("No");}return 0;
}

3、合并集合（模板）

一共有 n 个数，编号是 1∼n，最开始每个数各自在一个集合中。

现在要进行 m 个操作，操作共有两种：

  1. M a b，将编号为 a和 b的两个数所在的集合合并，如果两个数已经在同一个集合中，则忽略这个操作；
  2. Q a b，询问编号为 a 和 b 的两个数是否在同一个集合中；
输入格式

第一行输入整数 n 和 m。

接下来 m 行，每行包含一个操作指令，指令为 M a b 或 Q a b 中的一种。

输出格式

对于每个询问指令 Q a b，都要输出一个结果，如果 a 和 b 在同一集合内，则输出 Yes，否则输出 No。

每个结果占一行。

数据范围

1≤n,m≤1e5

输入样例：
4 5
M 1 2
M 3 4
Q 1 2
Q 1 3
Q 3 4
输出样例：
Yes
No
Yes
思路：

写好find函数和merge函数

代码：
#include<bits/stdc++.h>using namespace std;const int N=1e5+5;int n,m;int p[N];int find(int x)
{if(x!=p[x])p[x]=find(p[x]);return p[x];
}void merge(int a,int b)
{p[find(a)]=find(b);//a的祖先添加到b的祖先下面 
}int main()
{cin>>n>>m;for(int i=1;i<=n;i++)p[i]=i;while(m--){char op;int a,b;cin>>op;cin>>a>>b;if(op=='M'){merge(a,b);}else{if(find(a)==find(b))cout<<"Yes"<<endl;else cout<<"No"<<endl; }}//Yes Noreturn 0;
}

4、连通块中点的数量（模板）

给定一个包含 n 个点（编号为 1∼n）的无向图，初始时图中没有边。

现在要进行 m 个操作，操作共有三种：

  1. C a b，在点 a 和点 b之间连一条边，a 和 b 可能相等；
  2. Q1 a b，询问点 a 和点 b是否在同一个连通块中，a 和 b 可能相等；
  3. Q2 a，询问点 a 所在连通块中点的数量；
输入格式

第一行输入整数 n 和 m。

接下来 m 行，每行包含一个操作指令，指令为 C a b，Q1 a b 或 Q2 a 中的一种。

输出格式

对于每个询问指令 Q1 a b，如果 a和 b 在同一个连通块中，则输出 Yes，否则输出 No。

对于每个询问指令 Q2 a，输出一个整数表示点 a 所在连通块中点的数量

每个结果占一行。

数据范围

1≤n,m≤1e5

输入样例：
5 5
C 1 2
Q1 1 2
Q2 1
C 2 5
Q2 5
输出样例：
Yes
2
3

思路：

cnt数组统计连通块中点的数量（注意数量全放在祖先节点），合并函数（merge）中进行累加

代码：
#include<bits/stdc++.h>using namespace std;const int N=1e5+10;int n,m;int p[N];
int cnt[N];int find(int x)
{if(x!=p[x])p[x]=find(p[x]);return p[x];
}void merge(int a,int b)
{cnt[find(b)]+=cnt[find(a)];p[find(a)]=find(b);
}int main()
{cin>>n>>m;for(int i=1;i<=n;i++){p[i]=i;cnt[i]=1;}while(m--){char op[5];cin>>op;if(op[0]=='C'){int a,b;cin>>a>>b;if(find(a)==find(b))continue;merge(a,b);}else if(op[1]=='1'){int a,b;cin>>a>>b;if(find(a)==find(b))cout<<"Yes"<<endl;else cout<<"No"<<endl;}else{int t;cin>>t;cout<<cnt[find(t)]<<endl;}}return 0;
}

5、格子游戏（《信息学奥赛一本通》）

Alice和Bob玩了一个古老的游戏：首先画一个 n×n的点阵（下图 n=3 ）。

接着，他们两个轮流在相邻的点之间画上红边和蓝边：

1.png

直到围成一个封闭的圈（面积不必为 1）为止，“封圈”的那个人就是赢家。因为棋盘实在是太大了，他们的游戏实在是太长了！

他们甚至在游戏中都不知道谁赢得了游戏。

于是请你写一个程序，帮助他们计算他们是否结束了游戏？

输入格式

输入数据第一行为两个整数 n 和 m。n表示点阵的大小，m 表示一共画了 m 条线。

以后 m 行，每行首先有两个数字 (x,y)，代表了画线的起点坐标，接着用空格隔开一个字符，假如字符是 D，则是向下连一条边，如果是 R 就是向右连一条边。

输入数据不会有重复的边且保证正确。

输出格式

输出一行：在第几步的时候结束。

假如 m 步之后也没有结束，则输出一行“draw”。

数据范围

1≤n≤200
1≤m≤24000

输入样例：
3 5
1 1 D
1 1 R
1 2 D
2 1 R
2 2 D
输出样例：
4
思路：

注意审题，"轮流在相邻的点之间画上红边和蓝边"表示不存在有孤立的线的情况

可以把每个点进行转换，变成一个独特的数，然后我们就可以把每个点存起来，如果新的两个点转化后，发现有共同祖先那就表示封圈了

代码：
#include<bits/stdc++.h>using namespace std;const int N=4e4+9;//因为二维转化为一维了，所以一维空间必须开N的平方级 （200*200） 
int p[N];int find(int x)
{if(x!=p[x])p[x]=find(p[x]);return p[x];
}void merge(int a,int b)
{p[find(a)]=find(b);
}int main()
{int n,m;cin>>n>>m;for(int i=1;i<=n*n;i++)p[i]=i;int cnt=1;for(int i=1;i<=m;i++){int a,b;char c;cin>>a>>b>>c;int p=(a-1)*n+b;//p表示原来的坐标 int q;//q表示另一端（向下或者向右） if(c=='D')q=a*n+b;else q=(a-1)*n+b+1;//cout<<find(p)<<" "<<find(q)<<endl;if(find(p)==find(q)){cout<<i;return 0;}merge(p,q);}cout<<"draw";return 0;
}

这篇关于【并查集专题】【蓝桥杯备考训练】：网络分析、奶酪、合并集合、连通块中点的数量、格子游戏【已更新完成】的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！


http://www.chinasem.cn/article/837428。

相关文章

Java 的ArrayList集合底层实现与最佳实践

Java 的ArrayList集合底层实现与最佳实践

《Java的ArrayList集合底层实现与最佳实践》本文主要介绍了Java的ArrayList集合类的核心概念、底层实现、关键成员变量、初始化机制、容量演变、扩容机制、性能分析、核心方法源码解析、... 目录1. 核心概念与底层实现1.1 ArrayList 的本质1.1.1 底层数据结构JDK 1.7
阅读更多...
C++中unordered_set哈希集合的实现

C++中unordered_set哈希集合的实现

《C++中unordered_set哈希集合的实现》std::unordered_set是C++标准库中的无序关联容器,基于哈希表实现,具有元素唯一性和无序性特点,本文就来详细的介绍一下unorder... 目录一、概述二、头文件与命名空间三、常用方法与示例1. 构造与析构2. 迭代器与遍历3. 容量相关4
阅读更多...
一文详解Python如何开发游戏

一文详解Python如何开发游戏

《一文详解Python如何开发游戏》Python是一种非常流行的编程语言,也可以用来开发游戏模组,：本文主要介绍Python如何开发游戏的相关资料,文中通过代码介绍的非常详细,需要的朋友可以参考下... 目录一、python简介二、Python 开发 2D 游戏的优劣势优势缺点三、Python 开发 3D
阅读更多...
Redis中的有序集合zset从使用到原理分析

Redis中的有序集合zset从使用到原理分析

《Redis中的有序集合zset从使用到原理分析》Redis有序集合(zset)是字符串与分值的有序映射,通过跳跃表和哈希表结合实现高效有序性管理,适用于排行榜、延迟队列等场景,其时间复杂度低,内存占... 目录开篇：排行榜背后的秘密一、zset的基本使用1.1 常用命令1.2 Java客户端示例二、zse
阅读更多...
Java集合之Iterator迭代器实现代码解析

Java集合之Iterator迭代器实现代码解析

《Java集合之Iterator迭代器实现代码解析》迭代器Iterator是Java集合框架中的一个核心接口,位于java.util包下,它定义了一种标准的元素访问机制,为各种集合类型提供了一种统一的... 目录一、什么是Iterator二、Iterator的核心方法三、基本使用示例四、Iterator的工
阅读更多...
Java JUC并发集合详解之线程安全容器完全攻略

Java JUC并发集合详解之线程安全容器完全攻略

《JavaJUC并发集合详解之线程安全容器完全攻略》Java通过java.util.concurrent（JUC）包提供了一整套线程安全的并发容器,它们不仅是简单的同步包装,更是基于精妙并发算法构建... 目录一、为什么需要JUC并发集合？二、核心并发集合分类与详解三、选型指南：如何选择合适的并发容器？在多
阅读更多...
python语言中的常用容器(集合)示例详解

python语言中的常用容器(集合)示例详解

《python语言中的常用容器(集合)示例详解》Python集合是一种无序且不重复的数据容器,它可以存储任意类型的对象,包括数字、字符串、元组等,下面：本文主要介绍python语言中常用容器(集合... 目录1.核心内置容器1. 列表2. 元组3. 集合4. 冻结集合5. 字典2.collections模块
阅读更多...
SpringBoot分段处理List集合多线程批量插入数据方式

SpringBoot分段处理List集合多线程批量插入数据方式

《SpringBoot分段处理List集合多线程批量插入数据方式》文章介绍如何处理大数据量List批量插入数据库的优化方案：通过拆分List并分配独立线程处理,结合Spring线程池与异步方法提升效率... 目录项目场景解决方案1.实体类2.Mapper3.spring容器注入线程池bejsan对象4.创建
阅读更多...
C#实现一键批量合并PDF文档

C#实现一键批量合并PDF文档

《C#实现一键批量合并PDF文档》这篇文章主要为大家详细介绍了如何使用C#实现一键批量合并PDF文档功能,文中的示例代码简洁易懂,感兴趣的小伙伴可以跟随小编一起学习一下... 目录前言效果展示功能实现1、添加文件2、文件分组（书签）3、定义页码范围4、自定义显示5、定义页面尺寸6、PDF批量合并7、其他方法
阅读更多...
MySQL 数据库表操作完全指南:创建、读取、更新与删除实战

MySQL 数据库表操作完全指南:创建、读取、更新与删除实战

《MySQL数据库表操作完全指南:创建、读取、更新与删除实战》本文系统讲解MySQL表的增删查改（CURD）操作,涵盖创建、更新、查询、删除及插入查询结果,也是贯穿各类项目开发全流程的基础数据交互原... 目录mysql系列前言一、Create(创建)并插入数据1.1 单行数据 + 全列插入1.2 多行数据
阅读更多...

Copyright China编程 23002807@qq.com

沪ICP备2023033072号-2