【VP 记录】ABC204

本文章由 WyOJ Shojo 从洛谷专栏拉取，原发布时间为 2024-06-05 16:17:50

记录

ABC 8min 切掉，D 30min罚了一发假做法切了，E 想了很久感觉是个单峰函数，好像要三分但不会（其实均值不等式能直接求），F想到是矩阵加速 + 状压但是不会转移，都没做出。

基本判断题，略过不表。

基本循环题，略过不表。

基本搜索题，以每个点为起点分别跑 dfs 记录即可，时间复杂度 $O(n^2)$ 可过。

直接贪心或排序后贪心显然都是错误的。发现数据范围不大，考虑用 dp 解决。

发现分出的两部分中，一定是不小于总和一半的那部分成为答案，考虑处理所有可能分出的部分和，找不小于总和一半的最小值即可，用可行性 $01$ 背包即可解决。

由于最终需要到达时间最小，考虑到达时间 $f_t$ 在 $c,d$ 固定时随 $t$ 的变化，有 $f_t=c+\lfloor\frac{d}{t+1}\rfloor$，根据均值不等式推出 $t=\sqrt d+1$ 时 $f_t$ 最小。

又由于 $f_t$ 先减后增，所以在该 $t$ 之前到达就等待至 $t$，否则直接出发一定最优，跑最短路即可。

矩阵快速幂加速 dp。

发现 $h$ 很小 $w$ 很大，考虑对 $h$ 状压并对 $w$ 进行矩阵加速。

同时每一列的状态跟上一列有关，所以设 $f_{i,j}$ 为前 $i-1$ 列全部填满，第 $i$ 行已填状态为 $j$ 的方案数，发现 $f_i$ 只与 $f_{i-1}$ 有关，考虑预处理所有状态之间的转移方式进行矩阵加速。

所以要解决从上一行为 $i$ 状态转移到这一行为 $j$ 状态的方案数。考虑设 $g_k$ 表示前 $k$ 位的方案数，且横向的 $1\times 2$ 的在后一列考虑，变为一个线性 dp。

若有某一位在上一列和这一列均空，则方案数为 $0$，否则若有一列上为空，则只有唯一填法，$g_k=g_{k-1}$；若两列上都有，则可以随意放。若这个和上一个都可以随意放，就可以竖着放 $2$ 的，$g_k=g_{k-2}+g_{k-1}$。

这样分别处理出所有状态之间转移的方案数，用矩阵加速转移即可。