【VP 记录】ABC204

KSCD_ · 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}。

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