本文会统计一些做过的绿题及以上，总结一些解法，写一些简短的题解，学习何竺凌。

2024.1

AT_abc271_e

可以用 DP 来解决。\(dp_{i,j}\) 代表着第 \(i\) 条边，点 \(1\) 到 \(j\) 最短距离。考虑转移方式：如果需要这个边 \((u,v,w)\) 那么，\(dp_{i,j} = dp_{i-1,u} + w\)。不需要这个边：\(dp_{i,j}=dp_{i-1,j}\)。\(j\) 其实就是 \(v_i\)。空间的限制，所以我们没法开二维数组来存储。发现 \(i\) 从 \(i-1\) 转移来，所以说，我们可以压维。因此就得到了正解。

AT_abc271_f

常见的meet in the middle 典题由于 \(n \le 20\) 所以最多走 \(40\) 步，那么直接折半搜索解决

CF1006F

AT_abc271_f的双倍经验，需要小修改即可。

AT_abc268_e

首先，对于每一个人 \(i\) 都有自己想要匹配的 \(i\) 餐桌。于是想到，转动餐桌会使得餐盘离这个人出现两种情况：先递减再递增或先递增再递减。很容易想到，这其实可以看作一个很多条一次函数的直角坐标系。我们需要手推一下每一个点的地方，然后跑两遍前缀和就可以解决。由于奇偶的情况不一样，所以要分讨。其实，就是偶数一个峰值，奇数两个峰值，手推即可知道。但其实我们只需要建立顶点 \(i+\dfrac{n}{2}+1\) 和 \(i+\dfrac{n+1}{2}+1\) 即可。因为我们想要把直线直接延伸到比 \(n\) 大的地方以免发生取模错误。所以直接 \(+n\) 地套上去。