qbxt Day2 on 19-7-25
——TGZCBY
上午
1. 矩阵乘法在图论上的应用
有的时候图论的转移方程可以用dp的方式转移
特别是两个数的乘积求和的时候
比如邻接矩阵中f[i][j]表示走了i条边之后到达j点的方案数
直接用最后的矩阵*邻接矩阵^p就基本OK
通常情况下能够用矩阵乘法解决的优化问题
都有这种情况出现
然而要注意：数据范围
因为矩阵乘法的复杂度几乎无法保证\(\leq O(n^2)\)
我们这时候还是需要尽量去合并范围更小的乘法项
去优化这个更加难受的优化
牢记矩阵乘法有结合律，没有交换律
2. 搜索的剪枝技巧
zhx：说实话，我无法教给你们万用的技巧
因为每一个题都有一个特定的剪枝技巧
真的！！每一个题都不一样的
但是一些通用的剪枝技巧还是有迹可循
比如我们先想：什么时候用bfs
bfs通常使用在计数的时候
这个时候我们不会让dfs去跑一遍作死
然后还有前后数据没有太大关联的时候
这个时候状态转移好转移啊
如果bfs炸了，我们还是回到一个dfs上
dfs的好处就是状态转移直观啊
但是dfs无法满足大量的转移
怎么办呢？
这里提供几个解决办法：
-
改变枚举顺序
通常出题人是不会让你过正常思维整出来的题目的
所以我们要换一种顺序去得到正确答案并且快速枚举
-
可行性剪枝
说白了就是往最好的方面去走，然后排除绝对不可能的选项
先走最有可能的选项
这样我们就有了一个更好的搜索树让可行性这个剪枝更加优秀
-
判重
有一些搜索的搜索树是相同的
可能 or 不可能都剪掉
然后有一部分填空的题目上下、左右有对称性
如果重复也可以直接剪掉
-
卡时
有的时候你已经算出正确的答案了
特别是你的枚举顺序特别好的时候
这个时候如果快要超时了（当然你不知道答案是否正确）
你就赶紧掐断这个搜索树
直接输出目前为止最好的答案
这也不失为一种暴力的好办法
毕竟有的时候确实是好用（Orz）
搜索就说这么多
下午
基础数据结构
- 单调栈
单调栈当然是比较高级的栈
其中的元素满足一定的单调性
当我们弹出其中元素的时候
我们还要进行状态的转移
- BST
二叉搜索树之所以还讲
是因为要为后面线段树做好铺垫
而且搜索树的性质、思想十分重要
所以讲了BST
- 树状数组
树状数组之所以还有用处
是因为代码短，常数小
而且用它的地方还有求逆序对
所以好处多多
但是局限性很大
只要元素不满足“可以相减来转移”的性质
树状数组就废了
- 线段树
线段树是一个好东西
在维护区间操作的时候十分的给力
注意tag的用法
有的时候还是要进行一波玄学操作的
- 左偏树
老师竟然不会普通堆！于是一波福利就来了。
这个左偏树我做了详细的介绍，可以 点这里 来查看。
今天的例题我先不放了......等我先都做完了再说qwq