2024-08-17 18:37:04 星期六

一言: 吾道本无我，未曾嫌世人。如今到尘世，弥觉此心真.

上午

教了栈：stack与深搜

• 一、stack的定义
  stack 变量名
• 二、stack库函数
  1 . empty() 判断栈是否为空
  2 . pop() 弹出栈顶部的元素
  3 . push() 向栈顶部添加元素
  4 .size() 返回栈中元素个数
  5 . top() 返回栈顶的元素
• 三、栈例题
  1 .https://www.luogu.com.cn/problem/P1739
  2 .https://www.luogu.com.cn/problem/P1944
  3 .https://www.luogu.com.cn/problem/P1981
  附：栈和队列的区别
  栈是先进后出(FILO，First In Last Out)；
  队列是先进先出(FIFO，First In First Out)；
• 一、深搜的概念
  深度优先搜索（Depth First Search，简写DFS），简
  称深搜，其状态“退回一步”的顺序符合“后进先
  出”的特点，所以采用“栈”存储状态。深搜的空
  间复杂度较小，因为它只存储了从初始状态到当前
  状态的一条搜索路径。但是，深搜找到的第一个解
  不一定是最优解，要找最优解必须搜索整棵“搜索
  树”。
• 二、深搜的模板

void dfs(int dep，参数表){
    自定义参数；
    if(当前是目标状态) {
        输出解或者作计数、评价处理;
    } else
        for(i = 1; i <= 状态的拓展可能数; i++)
            if(第i种状态拓展可行) {
                维护自定义参数;
                dfs(dep+1,参数表);
            }
}

• 三、深搜例题
  1 .https://www.luogu.com.cn/problem/P2404
  2 .https://www.luogu.com.cn/problem/P1135
  3 .https://www.luogu.com.cn/problem/P1219
  附：今日PPT:arrow_down:
  网址：file:///C:/Users/Lenovo/Downloads/%E6%A0%88%E4%B8%8E%E6%B7%B1%E6%90%9C.pdf （内有系统栈的大小限制及许多题目:eyes:）
  :point_up:

2024-08-17 19:52:13 星期六