寒假day1 2.2

讲师：杨宁远，NOI2022Au，rk20，from 成都七中。

概括：基础算法。

6:30 起来和 bec 跑步，就跑了 5 min，还是很抽象的。

无调试网络，无qblt！

正题

枚举、搜索

方式：dfs bfs（迭代加深） 剪枝 A*

迭代加深：bfs的一种，每次所有 x 步在队列里，判断是否有终止局面，没有则进入下一层

A*：剪枝的一种，估价函数，判断是否有解/更优

loj537 DNA序列

发现字符集的大小只有 \(4\) ，所以所有合法的子串不超过 \(4^k\) 种，用桶记录一下即可。变成四进制压缩即可。（子串是连续的）

loj2148 栅栏

考虑对需要的木材排序，每次加进去搜，把提供的木材压缩。

k短路

先研究次短路

显然的结论：最短路和次短路是先一起走，后在一点分开的。

枚举 $(u,v),(u,v)\nin $ ，答案就是 \(\min(dis_{s,u}+w_{u,v}+dis_{v,t})\)。

我连 A* 都不会你让我听这个？？？

\(k+1\) 短路是通过 \(1\sim k\) 中的某一条路径修改一条边，后面最短路得到的。

loj2876 水筒

最小生成树：\(S\) 到 \(T\) 的路径上边权的最大值最小。

将城市之间的最短路视作边，做一棵最短路树即可。

定义一个城市 \(i\) 的区域 \(S\) 表示对于 \(j\in S\) ，\(j\) 最近的城市是 \(i\) ，且对于 \(k\nin S\) ，\(k\) 最近的城市不是 \(i\)。

后面听不懂。

骑士精神

枚举所有后继局面，如果当前步数+未还原白马数>=16 不合法。

分治

三维偏序

二维数点

考虑 x 排序，用树状数组求前缀和。

三维可以按照 x 排序后，用二维数点，\(O(n \log^2 n)\)。

\(k\) 维偏序：\(O(n\log^{k-1} n)\)。

loj2056 序列

变成三维偏序做，把三个的不等式变为两个不等式。

三维偏序：\(i\) \(a_i\) \(b_i\)。

直接对下标分治。

复杂度 \(O(n\log^2 n)\)。