日记 - 伊埃斯的博客站

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

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

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

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

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

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

没改。

后日谈

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

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

Thanks for reading!

日记

周五 7月 11 2025

531 字 · 2 分钟

life 日记