CF1037D - Valid BFS?

  被浏览

作为一道英文题,我们先解释一下题意:

给你一棵树和它的一个 BFS 序,让你判断这个 BFS 序是否是一个从节点 1 开始的合法 BFS 序。

接下来我们进入正题。

第一眼看到这题时,大部分人都会想到,既然是树,那么它一定是一层一层地向下 BFS。

也就是说,BFS 序中越后出现的节点,它树上的深度肯定是大于它前面的节点的。

于是照这个思想打完后,发现 Wrong Answer 了。

洛谷P1432 - 倒水问题

  被浏览

很容易看出这是宽度优先搜索,因为要求步数最少,且每个操作代价相同。

我们可以按操作类别分 6 种情况扩展,如果搜到最终状态就跳出 BFS(搜索顺序可以随意,因为 spj 已经配置好了,不像数据修改前要有特定的顺序)。

记得标记已经出现过的情况,不然会 TLE/MLE;