祝馀宫

第六课A - 环游世界经典的状压DP。设状态为 $dp[mask][ed]$ 表示已经经过了的国家和最后一个经过的国家。 转移很简单了，注意判断枚举的最后一个国家是否经过，目的地是否未被经过。 统计答案需要额外加上回到起点的代价。 最后就是距离数组需要用 Floyd 计算最短距离 B - 数字重排状压DP。 让我们最大化相邻元素之积，所以同样还是枚举插入的顺序，状态 $dp[mask][ed]$ 表示每个元素的使用情况，然后 $ed$ 表示最后一个放入卡组的元素。然后考虑转移。 这个状态的意思可以认为就是顺序的往空白位置里插入角色，所以压缩的状态还有一层隐藏含义就是插入到第几个元素了。 认清这个事实以后就非常好转移了，如果这个位置已经有了数字，我们就看枚举的这个数字是不是那个；否则看看这个数字有没有被固定，且这个位置有没有被固定的情况下可以转移。 另外这道题还有一个亮点是初始化。 如果第一个位置有东西放了，那么可以直接定义状态。否则就是找到所有自由节点放在第一个格子。 除此之外应该没有什么细节了。 C - 开门迷宫状压入门。 记录走到每一步钥匙的状态，广搜即可。 D - 简单环计数状压 ...

第四课A - 点到线段的距离三分经典题，带点计算几何，也可以纯数学解法。 设一个线段 $AB$ 上的动点 $C$，那么一般来说 $C$ 与 $P$ 的距离是先减小后增大的，这显然是一个单峰函数，所以我们直接三分 $C$ 点的位置即可。 如果三分的是 $C$ 至 $A$ 的长度在整个线段中的占比，那么可以直接用缩放向量的方式求出 $C$ 点坐标；如果是直接三分了 $C$ 至 $A$ 的长度，那么可以考虑转化成比例来计算。 另外就是一个小常识，在一个三维空间中两点的距离满足： \operatorname{distance}(A,B)=\sqrt{(A.x-B.x)^2+(A.y-B.y)^2+(A.y-B.y)^2}B - 三角形与四边形一看就不是三分题。因为随着 AD 的增大，ADE 与 BDEC 的面积比也会越来越大。 所以直接二分 AD 长度，用海伦公式计算面积并求出比例即可。 另外细节：浮点二分的判断条件是 $lr$ 。 C - 最大比例01分数规划模板题。 首先我们考虑一个最大比例 $ans$，则其应该满足要求： \frac{\sum_{i=1}^n v_i\times x_ ...

第一课A - 按钮变色注意到数据范围极小，所以可以状态压缩整个矩阵然后用 BFS 计算答案。 B - 最短连续子序列经典的双指针练习题，注意双指针的条件。 12345678int l = 1, r = 0, tot = 0, ans = 1e9;while(r <= n) { while(r <= n && tot + a[r] < S) { tot += a[r++]; } ans = min(ans, r - l + 1); tot -= a[l++];} 在上面的这段双指针代码中，因为第二个判断条件的错误，使得 $r$ 在跳出循环的时候永远保证着 $tot < S$ 的性质，与题目要求不符。并且从代码的内容和变量名声明中可以看出，这里表示的区间 $[l,r]$ 应该是一个左闭右开的区间，计算长度直接用 $r-l$ 。 123456int tot = 0, ans = 1e9;for(int l = 1, r = 0; l <= n; l++) { ...