日记 - 伊埃斯的博客站

今天是真的不颓。

T1

如果说有这样的 $a = \{1,2\}$ 和 $b = \{100,101\}$ ，显然我们不能先加 $a_1$ ，而应该先加 $a_2$ 。而后又看到 $x$ 可以为负，想到如果说将 $a_i$ 加上 $x$ 使得 $a_i = b_i$ 且 $a_i > a_{i + 1}$ ，我们就连一条 $i + 1 \to i$ 的边。可以证明这是一个有向无环图。因此我们一定有用 $\sum\limits_{i = 1}^{n}[a_i \ne b_i]$ 次的方法使得 $a = b$ 。

现在我们考虑使代价更小。考虑对于一个 $(a_i - b_i)^2$ ，要使它变小，我们考率分多次。显然等分最优。赛时想到了做背包 dp，复杂度 $O(nm^2)$ 。可以拿到 $\color{#5ec05e}{50}$ 的好成绩。~~看这个绿色就知道确实很好~~。

正解是整一个大根堆。将每个 $(a_i - b_i)^2$ 多分一个的负贡献插入，比如初始就放每个 $(a_i - b_i)^2$ 从 $1$ 次到 $2$ 次的负贡献。取 $m - \sum\limits_{i = 1}^{n}[a_i \ne b_i]$ 次就好。

没放代码是因为下次再做的时候希望能自己写出来。

T2

听 HD0X 讲的。

看到冒泡排序，想到逆序对。离线，从大到小枚举 $i$ ，并枚举每个 $x = i$ 的查询，计 $u$ 表示 $i$ 位置前面的比它大的数量， $v$ 表示 $i$ 位置后面的比它大的数量。让我们分类讨论一下（下文的 $k$ 都指查询的 $k$ ， $id$ 指查询编号， $pos_i$ 指 $i$ 的原位置）：

$k \le u$
这样的话， $i$ 前面的会在 $k$ 次冒泡后跑到 $i$ 后面去并把 $i$ 往前挤， $ans_{id} = pos_i - k$ 。
$k \le u + v$
从头开始考虑 $k$ 次冒泡。每次冒泡，一定会有一个比 $i$ 更大的数 $P_j$ 被一个更大的数 $P_{j + 1}$ 堵住，且位置比 $P_{j + 1}$ 左一个。
我们掏个样例出来： $\{4,3,5,1,2\}$ 。我们想要查询 $3$ 在第 $2$ 次冒泡后的位置。
第 $1$ 次冒泡： $\{3,4,1,2,5\}$ ， $4$ 被 $5$ 堵住，位置 $-1$ 。
第 $2$ 次冒泡： $\{3,1,2,4,5\}$ ， $3$ 被 $4$ 堵住，位置 $-1$ 。
这样我们看到 $3$ 在 $1$ 的位置。这个 $1$ 是由 $5$ 最初的位置经过 $2$ 次 $-1$ 后得到的。
我们再掏一个样例： $\{3,4,2,5,1\}$ 。我们想要查询 $2$ 在第 $3$ 次冒泡后的位置。
第 $1$ 次冒泡： $\{3,2,4,1,5\}$ ， $4$ 被 $5$ 堵住，位置 $-1$ 。
第 $2$ 次冒泡： $\{2,3,1,4,5\}$ ， $3$ 被 $4$ 堵住，位置 $-1$ 。
第 $3$ 次冒泡： $\{2,1,3,4,5\}$ ， $2$ 被 $3$ 堵住，位置 $-1$ 。
$2$ 在 $1$ 的位置。这个 $1$ 是由 $5$ 最初的位置经过 $3$ 次 $-1$ 得到的。
我们发现，因为在这 $k$ 次里会被堵 $k$ 次，所以最初的位置（就是上文的 $5$ 的最初的位置）一定是比 $i$ 大的数按照原序列的顺序的第 $k$ 个。而每次被堵会使得下标 $-1$ ，所以答案就是比 $i$ 大的数的第 $k$ 个的位置减 $k$ 。
$k > u + v$
显然这个时候 $i$ 归位了， $ans_{id} = n - u - v$ 。

实现可以这样：因为我们从大到小枚举 $i$ ，用线段树维护。每次算完 $i$ 都将线段树 $pos_i$ 的地方置为 $1$ 。 $u$ 就是 $[1,pos_i]$ 的区间和， $v$ 就是 $[pos_i,n]$ 的区间和。“比 $i$ 大的数按照原序列的顺序的第 $k$ 个”可以通过线段树上二分找到第 $k$ 个 $i$ 。因为只有 $k > u$ 时才会询问第 $k$ 个，所以第 $k$ 个一定在 $i$ 原位置的右边。

T3 & T4

补题速度还是太快了一点，没看。

后日谈

之前的考试挂分 $\color{#ff0000}{50}$ 起步，今天只挂了 $\color{#5ec05e}{10}$ 分，可喜可贺。

要是 T1 没有被背包误导的话就更好了。~~好歹有 50 分嘛~~

今天晚上有 div.3，打不打呢？

Thanks for reading!

日记

周二 4月 08 2025

995 字 · 4 分钟

life 日记