第六课

A - 环游世界

经典的状压DP。设状态为 $dp[mask][ed]$ 表示已经经过了的国家和最后一个经过的国家。

转移很简单了，注意判断枚举的最后一个国家是否经过，目的地是否未被经过。

统计答案需要额外加上回到起点的代价。

最后就是距离数组需要用 Floyd 计算最短距离

B - 数字重排

状压DP。

让我们最大化相邻元素之积，所以同样还是枚举插入的顺序，状态 $dp[mask][ed]$ 表示每个元素的使用情况，然后 $ed$ 表示最后一个放入卡组的元素。然后考虑转移。

这个状态的意思可以认为就是顺序的往空白位置里插入角色，所以压缩的状态还有一层隐藏含义就是插入到第几个元素了。

认清这个事实以后就非常好转移了，如果这个位置已经有了数字，我们就看枚举的这个数字是不是那个；否则看看这个数字有没有被固定，且这个位置有没有被固定的情况下可以转移。

另外这道题还有一个亮点是初始化。

如果第一个位置有东西放了，那么可以直接定义状态。否则就是找到所有自由节点放在第一个格子。

除此之外应该没有什么细节了。

C - 开门迷宫

状压入门。

记录走到每一步钥匙的状态，广搜即可。

D - 简单环计数

状压DP。

状态可以这样定义：$dp[mask][ed]$ 表示环中有点 $mask$，且最后一个加入环中的点是 $ed$，第一个加入环的点是 $mask$ 中编号最小的点。

这样布局的好处是可以快速的知道我们有没有回到起点。并且正确性是显然的，因为环他就是一个环，应该是没有起点的区分的。

转移的时候注意，接下来连到环里的节点编号都得大于等于起点，不然的话状态正确性不能保证。

答案统计就是每一次转移回起点就可以统计答案。

除此之外应该没有什么注意的地方了。

E - 回文子序列删除

枚举子集。

设 $dp[mask]$ 表示对于子序列 $mask$ 需要多少步清空，转移就是枚举一个 $mask$ 的子集看看是不是回文。

判断回文的 $O(n)$ 可以预处理，这样复杂度就从 $O(3^n\times n)$ 降到了 $O(3^n)$。

这题没有任何的细节。

F - 任务安排

状压DP。

因为我们这一次任务的选择和上一个选择的任务没有关联，所以可以直接把状态设为 $dp[mask]$ 表示已经完成的任务为 $mask$ 的情况下，扣的最少分数。转移都很正常，大力额外维护一个答案每次比较字典序小的即可。

G - 直线刷点

每次可以沿着一个直线刷去一排点。

设状态为 $dp[mask]$ 表示已经被清除的点。那么预处理 $flag[i][j]$ 表示与 $i,j$ 在同一条直线上的所有点的集合。这里的预处理需要特判 $i,j$ 表示同一个点的情况，然后也别忘了处理 $flag[i][i]$ 的情况。

转移非常常规，直接枚举一条直线即可。

以为这样就大功告成了？看看复杂度 $O(2^n\times n^2)$ 这道题还是多测，很显然不行。

考虑优化。

优化就需要直接大改状态，把状态设为 $dp[mask]$ 表示还没有被清除的点。这样有什么好处吗？

我们可以从没有被清除的点中编号最小的那一个点往外连一条边，这样转移就可以优化掉一个 $n$ 。

但是这样不会漏状态吗？并不会，因为最小的那一个点一定是会被转移掉的，也就是说不管动不动他最终都会消除，所以不妨直接把它消除了，毕竟同一个划线方案的话划线顺序不重要。

这样就可以AC这道题了。

H - 移动皇后

深搜找出所有皇后的最终状态，然后考虑DP算出步数。

设状态 $dp[mask][row]$ 表示 $mask$ 个皇后归为并正在处理 $row$ 皇后的最小步数。

转移就枚举让 $row$ 皇后去哪里即可。

这里移动是可以忽略皇后阻挡的。

这里讨论一下：

如果要移动该子到相应位置时，有一个还没有移动到相应位置的棋子卡位了，那么就让那个卡位的棋子先移动，再移动该棋子，步数不变
如果要移动该子到相应位置时，有一个已经移动到相应位置的棋子卡位了，那么就交还一下移动顺序，让该子先移动，然后再移动另一个
如果被上述两种情况卡位了，这种情况是不存在的，因为N皇后的性质，不在同行同列同斜线，假设存在了，那交换一下移动位置就可以了，步数还是不会变的

第七课

A - 静态区间最小值查询

ST表模板题。

注意多判断防止访问非法内存。

B - 众数查询

一个尝试混入ST表中的分块题。

直接处理出所有相同数字的块，对于首尾特判，中部ST表求最大值即可。

C - 区间查询

设 ST 表表示的是 $st[i][j]$ 从 $i$ 点开始往右取 $2^j$ 个区间后最靠左的右端点。

这里往后取一个需要双指针，然后就正常倍增即可。

接下来对于每个区间计算答案就是正常倍增思路。

别忘了离散化。

维护 $st[i][0]$ 的初始值时可以从后往前维护，因为如果仅仅是按照优先左端点升序、然后右端点升序的顺序排序，然后找到某个点之后最小的 $l$ 中最小的 $r$，实际上是错误的，因为 $l$ 优先最小不代表 $r$ 小。如果是按照这个排序规则你需要从后往前维护。

如果优先按照右端点升序、然后左端点升序的话似乎并不太好计算 $st[i][0]$ 。

D - 区间覆盖

感觉和上题没区别，这次维护的是 $st[i][j]$ 表示能够覆盖 $i$ 点并往右取 $2^j$ 个区间的最大右端点。

这样处理 $st[i][0]$ 就是所有小于 $i$ 的 $l[i]$ 中 $r[i]$ 最大的。

对于答案的统计就是正常的去找小于 $r$ 的点，最后看看再往右跳一个能不能覆盖 $r$ 即可，别忘了多跳的这一步会让答案加一。

E - 子矩阵查询

二维倍增的模板题。

没有任何细节。