2022年6月26日,”理实交融”——勇攀程序竞赛之巅团队正式开始了社会实践的第二天,大家开始了第二天的训练,今天也是四道比较简单题目,有二分查找、递推、并查集,队员们都能够积极去做题,完成任务。
今天学习的有并查集,并查集是一种树形的结构,这种数据结构是把一些元素按照一定的关系组合在一起。比如在亲戚关系的场景下,并查集是由一个跟节点(根节点指向自己)和所有他的子节点(可能是他的孩子节点或者子孙节点)组成。在信息学竞赛中,并查集是一种不可忽视的一部分内容,把最近几年的NOI和NOIP复赛题目大致浏览了一遍,发现有好几道应用并查集的题目,因此本文由浅入深的介绍并查集在编程中的巧妙应用。什么是并查集?并查集是一种树型的数据结构,用于处理一些不相交集合(DisjointSets)的合并及查询问题。常常在使用中以森林来表示。集就是让每个元素构成一个单元素的集合,并就是按一定顺序将属于同一组的元素所在的集合合并。并查集的主要操作:
1、初始化:把每个点所在集合初始化为其自身;
2、查找:查找元素所在的集合即根节点;
3、合并:将两个元素所在的集合合并为一个集合,合并两个不相交集合判断两个元素是否属于同一集合。并查集进行n次查找的时间复杂度是O(n)(执行n-1次合并和m≥n次查找)。其中是一个增长极其缓慢的函数,它是阿克曼函数(AckermannFunction)的某个反函数。它可以看作是小于5的。所以可以认为并查集的时间复杂度几乎是线性的。今天学的知识我们要学会去运用,去应用在我们的生活当中,来处理解决一些实际问题。
http://www.dxswb.com/shijian/448632.html
点此复制本页地址
7月22日,交通学院“圆梦”暑期社会实践团的志愿者们在荷韵小学组织了一场特别的活动,让学生们为父母写一封感恩信。通过这个活动,实践团成员们希望让学生们更加深刻地体会到父母对他们……
潘佳鑫 山东理工大学交通与车辆工程学院查看全文 >>
7月22日,“圆梦”暑期社会实践团采用线上线下方式调研支教学生对红色文化的了解情况,旨在评估青少年对中国革命历史和红色文化的认知程度,以促进红色文化的传承和弘扬。在本次调研中,……
陈佳兴 山东理工大学交通与车辆工程学院查看全文 >>
7月22日,“圆梦”实践团在荷韵小学举行了一场别开生面的放飞梦想活动。在活动开始前,实践团成员鼓励学生们在纸上写下自己的梦想或者烦恼,然后在操场上放飞梦想,大声说出自己的烦恼。……
石正杰 山东理工大学交通与车辆工程学院查看全文 >>
7月21日,“圆梦”暑期社会实践团在荷韵小学的支教活动接近尾声,为了给大家留下更美好的回忆,实践团成员举办了一次盛大的欢送会。欢送会涵盖了歌曲大合唱和游戏互动活动等众多有趣的环……
夏彬 郭俊杰 山东理工大学交通与车辆工程学院查看全文 >>
7月20日,交通学院“圆梦”暑期社会实践团的团队成员走进荷韵小学,为这里的孩子带来一堂不一样的科学实验课,为学生们带来了先进的科学知识。在这场课程中,“圆梦”暑期社会实践团成员……
王娟娟 山东理工大学交通与车辆工程学院查看全文 >>
7月20日,交通学院“圆梦”暑期社会实践团在微山县荷韵小学组织同学们在国旗下进行宣誓活动并开展红色教育课堂。此次活动由团队负责人夏彬组织。首先,实践团成员先组织同学们到操场上国……
陈佳兴 山东理工大学交通与车辆工程学院查看全文 >>
7月20日,“圆梦”暑期社会实践团在荷韵小学开展了一堂精彩的书法课。旨在向学生们介绍中国书法的悠久历史和艺术魅力,激发他们对书法的兴趣,并传承中华文化艺术。在这堂书法课中,实践……
潘佳鑫 山东理工大学交通与车辆工程学院查看全文 >>
7月20日,交通学院“圆梦”暑期社会实践团在荷韵小学开展了美术课+摄影课+手工课课堂新模式,通过多角度开展拓展课堂。此次拓展课堂是美术、摄影、手工课的新组合。首先,实践团成员通过视……
郭俊杰 山东理工大学交通与车辆工程学院查看全文 >>