日记

为什么不写？？！

T1 # Link to T1

不知道暴力为啥错了，反正 $95$ 分，不管他了。

T2 # Link to T2

我们发现代价式子里有个绝对值：$\sum\limits_{i = 1}^{n - 1}\sum\limits_{j = i + 1}^{n}|a_i - a_j|$，考虑把 $a$ 排序后变成 $b$，那么代价就变成了 $\sum\limits_{i = 1}^{n - 1}\sum\limits_{j = i + 1}^{n}(b_j - b_i)$。

再把贡献式子转换一下：$\sum\limits_{i = 1}^{\lfloor \frac{n}{2} \rfloor}(n - 2i + 1) \times (b_{n - i + 1} - b_i)$。我们发现要让 $(b_{n - i + 1} - b_i)$ 尽量小，于是把 $l$ 从大到小排序，把 $r$ 从小到大排序，然后让 $b_{n - i + 1} = l_i,b_i = r_i$ 就行了。

T3 # Link to T3

神秘小 dp。

我们发现，在左端点固定的情况下，右端点肯定是越大越优。于是我们设 $dp_{i,j}$ 表示在第 $i$ 轮，左端点为 $j$ 时右端点最大在哪里。

考虑转移：

• 取了个前缀：$dp_{i,j} = \max\limits_{k = 1}^{j - d}dp_{i - 1,k}$，条件：$j > d \land \min\limits_{k = j - d}^{j - 1} \ge s$。用一个前缀和优化。
• 取了个后缀：$dp_{i,j} = \max\limits_{k = 1}^{dp_{i - 1,j}}k$，条件 $\min\limits_{l = k}^{k + d - 1}a_l \ge s$。转移的时候记录一个变量就行。

时间复杂度 $O(n^2)$，常数有点大。

T4 # Link to T4

你说你都想到了为啥不写呢？

后日谈 # Link to 后日谈

下午不想改 C 于是打算去做网络流。但是网络流 $24$ 好像做不出来于是找了两道网络流水题做。做了半天发现太简单了，于是又回去做网络流 $24$ 题。

我发现我不缺知识也不缺思维。我甚至想得到别人想不到的东西。但是我缺自信啊！我想到了也不敢写，究其原因时码力实在是太强了。我写出来的代码：在大量的 bug 中发现少量代码。一个树剖都能硬控我一上午。

还是得练码力啊。