菜鸡aaa

题解

/ 注册

全部文章 / 题解（共5篇）

题解 | #[NOIP2017]奶酪#

三种解法：bfs，dfs，并查集方法一：bfs 两个点之间的距离如果小于等于2*r，那么这两个点可以相互到达。将所有可以互相到达的两个点之间连一条边。将所有与下表面相交的点入队，从这些点开始进行bfs搜索，对于每个搜索到的点进行判断：该点是否与上表面相交，若能找到与上表面相交的点，则输出yes，若...

C++ 深度优先搜索广度优先搜索并查集

2023-08-13

2 634

题解 | #拆路#

思路： 1、维护每个集合的最大繁荣值，只需要将最大繁荣值的节点设置成根节点，每次查找x所在集合的最大繁荣值时只需要找到x的根节点，根节点的繁荣值即为最大繁荣值。每次合并两个集合时，让较小繁荣值的根节点指向较大繁荣值的根节点。 2、如果按照普通方法先进行m次建边操作，再遍历q次询问或删边操作，会发现并...

C++ 并查集

2023-08-11

5 461

题解 | #Parity game#

题目链接：https://ac.nowcoder.com/acm/problem/51097 知识点：并查集，维护每个节点到根节点的距离题目描述：一段长为n的由0和1组成的序列，依次给出q个回答，每个回答包括该序列的一个片段子序列的起点位置x，终点位置y，和该子序列【x，y】内有奇数个1还是偶...

C++ 并查集并查集

2023-08-06

3 493

题解 | #[NOIP2010]关押罪犯#

借鉴了别人的题解加上自己的理解 1、只有两座监狱，所以两个罪犯要么在同一个监狱要么在不同监狱 2、将影响力从大到小排序，从大到小枚举每个冲突，尽可能的让冲突避免（即将两个人分到不同监狱），直到出现无法避免冲突的情况，因为已经将冲突由大到小排序，之后的冲突都比这个冲突小，所以该冲突就是答案要求的。 3...

C++ 并查集

2023-08-05

2 591

题解 | #叠积木#

一、把每堆积木看作一个集合，最下方的积木是集合的根节点二、只需要维护集合中每个元素到根节点的距离d[x](这题和食物链那题基本相同）三、还需要维护每个集合中元素的数量s[x]，目的是为了方便后面维护d[x] 四、find(x)函数返回x的祖宗节点，同时更新从x节点到祖宗节点路径上所有的节点d[x...

C++ 并查集并查集

2023-08-05

4 583