日记

我觉得我也不算大常数选手啊？

T1 # Link to T1

神秘小结论题。

我们设选的数是 $\{a_1,a_2,\dots,a_k\}$，那么开门的概率就是 $\sum_{i = 1}^{k}(9 - a_i) \times 10^{-i}$。我们发现 $9 - a_i$ 一定不会大于 $9$。这是一个非常好的性质啊，这意味着对于 $i < j$，$a_j$ 做的贡献怎么都不会比 $a_i$ 大。所以我们要优先取 $a_1$ 小的，再取 $a_2$ 小的，以此类推。每次取一个前缀最小值就行了。

T2 # Link to T2

我终于调出来淀粉质了 qwq。

就是点分治，然后顺序枚举每颗子树。把点权离散化之后用树状数组维护值域上的后缀 $dis$ 最大值。我们在计算当前子树里这个点 $[u,dis]$ 的时候，直接上树状数组查询 $[a_u,V]$ 的最大值，有 $ans_u \gets dis + que(a_u)$。对于整个子树查询完了之后再依次往树状数组里插入。

但是我们发现这样会算漏，所以我们需要把子树顺序反一遍再来一次。

T3 # Link to T3

我的常数也不大啊？

设 $b_i = |a_i - a_{i - 1}|,c_i = |a_i + a_{i - 1}|$。我们发现在什么操作都不做的情况下 $a_i$ 的值是 $b_i$，反之如果 $a_i$ 操作过就是 $c_i$，所以我们可以最小费用流。将 $b_i,c_i$ 离散化后建图：$s \to b_i$ 建一条 $(1,0)$ 的边，表示它能够选 $1$ 次且没有代价。$b_i \to c_i$ 建一条 $(1,1)$ 的边，表示它能够花费 $1$ 的代价从 $b_i$ 变成 $c_i$。对于值域里 $[1,V]$ 里的每个点 $i$，从 $i \to t$ 建一条 $(1,0)$ 的边，表示每个值只能出现一次。

最后判断一下最大流是否是 $n - 1$，不是就无解。答案就是 $\lceil \frac{cost}{2} \rceil$，因为每次翻转能做出两次操作。

T4 # Link to T4

没改。

后日谈 # Link to 后日谈

所以我拼尽全力打出来的 $200$ pts算什么呢？算个 rnk18？

所以以后还是要再拼尽全力打个部分分的，一分都骗不到的 debuff 太坐牢了。