日记

补昨天晚上的 div.2。

Array Recoloring# Link to

猜结论：$ans$ 为最大的 $k + 1$ 个数相加。

证明：很简单，不用写。

注意：特判 $k = 1$ 和 $k = n$。

昨天晚上就是没有特判导致挂了 B 题。

Equalization# Link to

昨天晚上想的：想到了背包，但是因为有 $\sum_{i = 1}^{16} \approx 60 \times 2$，这个 $16$，我想到它可以放在指数上。于是就往状压上面想了。

正解：设 $dp_{i,j}$ 表示 $x$ 左移 $i$，$y$ 左移 $j$ 的最小代价。

[NOI2018] 归程# Link to

这里提供一个题解能过，我不能过的方法：

先 dijkstra 出 $1$ 开头的单源最短路，想到车在一个连通块内不用代价，考虑用并查集维护连痛块。如果不强制在线，我们可以通过海拔从大到小循环每个边，然后合并。但是这道题强制在线。并查集不能分离，考虑可持久化并查集。

但是可持久化并查集是 $O(m \log^2 n)$ 的。算了一下，大概是 $7.5 \times 10^7$。加上线段树的常数，跑不过。

[THUPC 2017] 天天爱射击# Link to

考虑击碎第 $i$ 块木板的子弹 $c_i$。那么 $c_i$ 一定是 $[l_i,r_i]$ 范围内第 $s_i$ 个出现的。这样就是一个静态区间 $k$ 小值。

后日谈 # Link to 后日谈

考虑在期中的时候将得分率提高至至少 $30\%$，在期末提高至 $60\%$。

然而现在都开学第 $5$ 周了，我还没有长进。