AcWing – 1562. 微博转发
题目链接 题目链接 题解 DFS版本 因为搜索的时候会有一个问题，如果搜索的时候发现到达一个点的时候的步数，比前一次访问过这个点的步数还多，那么就不用往下搜索了，再搜只会增加时间复杂度。在写题过程中还有一个全局变量和局部变量问题。 函数中局部变量只会在这一层起…
Tag: DFS
四川大学第五届SCUACM新生赛（同步赛）- K – 简单题
题目链接 题目链接 solution 通过拆解公式，可以得出当a[i] < x时候，进行公式变换后也还是原来的数值，所以我们只用处理大于等于的情况。首先想到的方法是搜索。 #include<map> #include<set> #…
Acwing – 1497. 树的遍历
题目链接 题目链接 solution 由于给出的是后序遍历与中序遍历，后续遍历的遍历顺序是左右根，中序遍历的顺序是根左右，所以我们先用后序遍历确定根节点，然后再在中序遍历里面找到该节点，然后该节点左边就是左子树，右边就是右子树，左子树的数量就是k - bl +…
AtCoder Beginner Contest 293 – D – Tying Rope
链接 题目链接 solution 这道题简化之后其实就是找图中的环和线，我们先进行并查集操作，把能连接成环的都连接成环，剩下的不能连接的放那，然后用BFS搜索一下连通块的个数，用连通块的个数减去已经成环的个数就是剩下没有成环的个数。怎么判断成没成环，在进行并查…
AtCoder Beginner Contest 292- E – Transitivity
solution 这道题目的大意是给一个有向图，然后问你从a-b,b-c且a-c连一条边且距离等于1的条数，正面来做这道题有一定的难度，这个数起来太麻烦，可以转换思路，例如，把他所有的从当前点到可以到达的点的数目全部数出来，那么，我们就得到了从a-b距离为1，…
AcWing-1402. 星空之夜
solution 这道题的难点就是把形状相同的块算成一种，旋转对称都算是一种，如何识别块是形状相同。那就要用到hash,整体处理过程中用到了一个新的算法 洪水填充(Flood fill)算法：从一个起始节点开始把附近与其连通的节点提取出或填充成不同颜色颜色，直…