日记

誓死坚守 5 号机房

T1 # Link to T1

赛时想到：$h_i$ 一定取某些值是更优的，于是我们就可以优化掉那个 $10^9$。
但是都想到 $90\%$ 了啊啊啊啊啊啊啊啊啊啊啊

我们发现 $h'_i$ 一定是属于 $S = \{h_i + jd \mid i \in [1,n],j \in [-n,n]\}$。可以发现 $|S|$ 是 $O(n^2)$ 级别的。于是我们的状态就可以从 $O(nV)$ 优化到 $O(n^3)$。但是转移还是 $O(n^5)$ 的，但是我们可以用单调队列优化到 $O(n^3)$。

但是还有一个 $O(n \log n)$ 的做法。我们发现如果把 $dp_{i,j}$ 当作 $dp_i(j)$，一个关于 $j$ 的函数，那么 $dp_i(j)$ 一定是下凸的，且是许多一次函数组成的，有许多拐点。我们可以用对顶堆维护拐点，那么复杂度就是 $O(n \log n)$ 的了。

T2 # Link to T2

签到题，但是我犯唐啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊

我们发现，如果把原图分成 $k$ 分图，且 $k$ 最小，答案就是 $k - 1$ 了。这里想到了。然后看到数据范围想到状压，这也想到了。

那为啥不把他俩合起来？？？？

设 $f_s$ 表示点集为 $s$ 的导出子图是否是一个独立集。可以 $O(n2^n)$ 预处理。$dp_s$ 表示点集为 $s$ 的导出子图对应的最小的 $k$ 是多少。转移就是 $dp_s = \min_{f_t}dp_{s - t} + 1$。时间复杂度 $O(n2^n + 3^n)$，轻松跑。

Od deski do deski# Link to

我们发现在原序列合法的情况下，一定有方法使得删除的区间不交。所以可以 dp。我们称一个点配对表示它之前已经有点和他相同了。设 $dp_{i,j,0/1}$ 表示前 $i$ 个数，有 $j$ 个数还没有配对。转移如下：

我现在都不认识合法两个字了

后日谈 # Link to 后日谈

今天唐飞了。