“范式杯”2023牛客暑期多校训练营1 – K – Subdivision
题目链接 链接 题目大意 给你一个无向图，n个点，m条边，你可以在任意一条边中间增加一个点，边的长度还是1，问你从1到各点距离小于等于k的点的个数最多是多少。 题解 比赛过程中只想到了这道题的一部分，想着将加点转换成断环和在叶子节点增加儿子，但是在对深度没有印…
Tag: BFS
Manthan, Codefest 18 (rated, Div. 1 + Div. 2) – D. Valid BFS? time limit per test2 seconds
题目 题目大意 给你一堆双向边，保证能够形成一个树，再给你一个一个序列，问你这个序列和给出的边形成的树一样不？ 题目链接 链接 题解 刚开始想的是先bfs，然后计算出下一层的儿子的位置在哪，然后这个这么太难写了，所以瞅了眼题解重新写一下。思路是把bfs的顺序重…
AcWing – 1488. 最短距离
题目链接 链接 题目大意 这道题问你，给你n个村庄，有些村庄有商店，有些村庄没商店，问你从某个村庄出发，找到一个商店最短距离是多少。 题解 这题一眼顶针。没看出来，本来想的是从询问的点开始每次spfa一次，但是，但是，肯定会超时的啦。然后就有一个很骚的操作，把…
AcWing – 1562. 微博转发
题目链接 题目链接 题解 DFS版本 因为搜索的时候会有一个问题，如果搜索的时候发现到达一个点的时候的步数，比前一次访问过这个点的步数还多，那么就不用往下搜索了，再搜只会增加时间复杂度。在写题过程中还有一个全局变量和局部变量问题。 函数中局部变量只会在这一层起…
拓扑排序
拓扑排序的定义 对一个有向无环图G进行拓扑排序，是将G中所有顶点排成一个线性序列，使得图中任意一对顶点u和v，若边(u,v)∈E(G)，则u在线性序列中出现在v之前。通常，这样的线性序列称为满足拓扑次序(Topological Order)的序列，简称拓扑序列…
Acwing – 1497. 树的遍历
题目链接 题目链接 solution 由于给出的是后序遍历与中序遍历，后续遍历的遍历顺序是左右根，中序遍历的顺序是根左右，所以我们先用后序遍历确定根节点，然后再在中序遍历里面找到该节点，然后该节点左边就是左子树，右边就是右子树，左子树的数量就是k - bl +…
AtCoder Beginner Contest 293 – D – Tying Rope
链接 题目链接 solution 这道题简化之后其实就是找图中的环和线，我们先进行并查集操作，把能连接成环的都连接成环，剩下的不能连接的放那，然后用BFS搜索一下连通块的个数，用连通块的个数减去已经成环的个数就是剩下没有成环的个数。怎么判断成没成环，在进行并查…
AcWing-1402. 星空之夜
solution 这道题的难点就是把形状相同的块算成一种，旋转对称都算是一种，如何识别块是形状相同。那就要用到hash,整体处理过程中用到了一个新的算法 洪水填充(Flood fill)算法：从一个起始节点开始把附近与其连通的节点提取出或填充成不同颜色颜色，直…