日记

我真的拥有思维吗？

Connecting the Graph# Link to

想到 $70\%$ 然后成功的被自己带偏了。

我们发现，如果没有那些乱七八糟的新边，肯定是把 $a$ 数组排序之后依次建边来的最优。于是我们先把这些边加进去，边权就是 $(a_{i + 1} - a_i)^2$。再把新的边加进去，边权为 $0$。最后跑 Kruskal 就是了。

这个故事告诉我们：最小生成树多半是要扯到 Kruskal 和 Prim 这俩上面的。

Disproportionate Tree# Link to

直觉告诉我这个题要从叶子节点往上处理。

说明在竞赛里，直觉还是很重要的。

我一开始以为两个一样的数连的边不会有贡献，然后就朝着这个方向想了。深度从小到大处理，如果需要这个点造成 $2^p$ 的贡献就把整颗子树都加上 $p$。

理想很丰满，现实很骨感。我发现两个一样的点也会造成 $1$ 的贡献。不过无伤大雅。先把 $k$ 减掉 $n - 1$ 就是了，造成的贡献也从 $2^p$ 变成了 $2^p - 1$。设当前在处理点 $u$，每次找到一个最大的 $p$，使得 $2^p - 1 \le k$，把 $k$ 减掉 $2^p - 1$，$u$ 的整颗子树加上 $p$ 就行了。子树加可以用差分实现。因为线段树太长了

Driveaway# Link to

我们考虑如何从 $k - 1$ 推到 $k$。我们发现 $k - 1$ 时选的点集一定是 $k$ 时的真子集。因为如果不是，那么一定有一个点，在 $k - 1$ 的时候被选但是在 $k$ 是没被选。此时我们一定可以在 $k$ 时选它使得更优。于是这么做就是了。我们把选走的都删掉，用链表维护。用一个大根堆堆维护选链表里的每对数造成的负贡献。选走一对数就把他的贡献从堆里删除。

后日谈 # Link to 后日谈

我拥有思维吗？也许吧。

我拥有直觉吗？也许吧。

我拥有码力吗？这喷不了这是真没有