模拟&递归

模拟

似乎没什么好说的，模拟就是出题人让你做什么，你就做什么，然后你就会WAAC

推荐例题：

  1. [CSP-S2020] 儒略日

  2. [SDOI2010]猪国杀

    光速逃

递归

​ 其实就是一个函数在求解过程中调用自己，然后你把最终值手算出来，当询问道直接返回

1
2
3
4
int func(传入数值) {
  if (终止条件) return 最小子问题解;
  return func(缩小规模);
}
递归其实比暴力要慢，所以还是费手写暴力吧

dfs&bfs

DFS

算法

DFS即depth first search 深度优先搜索，是搜索算法的一种也是考场骗分神器

即每次当一种情况无法延伸后返回父亲节点，换一个分支再次延伸

e.x.

对于一个这样的搜索树：

请你先手推一下dfs的顺序:

0->1->3->1->4->8->4->1->5->1->0->2->6->7->6->2->0

伪代码

1
2
3
4
5
6
7
8
DFS(v) // v 可以是图中的一个顶点，也可以是抽象的概念，如 dp 状态等。
  在 v 上打访问标记
  for u in v 的相邻节点
    if u 没有打过访问标记 then
      DFS(u)
    end
  end
end

BFS

算法

我们注意到，在上面的搜索树中，当答案在右侧时dfs搜索到的速度也很慢，如点2

所以我们可以使用BFS

BFS 全称是 Breadth First Search，中文名是宽度优先搜索，也叫广度优先搜索。

使用queue，每次从队首取出元素，把能到达的节点压入队尾。

因此，第一次访问某点一定是到当前点的最少步数。所以bfs常被用了求最值

对于这个搜索树

请你先手推一下bfs的顺序:

0 1 2 3 4 5 6 8 7

伪代码

1
2
3
4
5
6
7
8
9
10
11
12
13
bfs(s) {
  q = new queue()
  q.push(s), visited[s] = true
  while (!q.empty()) {
    u = q.pop()
    for each edge(u, v) {
      if (!visited[v]) {
        q.push(v)
        visited[v] = true
      }
    }
  }
}