日记

考逝。

totscore：$\huge \color{red}{40}$。

究其原因是 T2 的暴力爆炸了。

T1 # Link to T1

没看。

正解是这样的：对于每条边，有 $\frac{1}{2x + 1}$ 的概率使得连通块的数量 $+1$，剩下的会使同色的对数 $-1$。直接算就行。

T2 # Link to T2

爆炸了

不然不会只有 $40$ 分的呜呜呜。

正解：题目里没写对于硝硼铀数量的限制，我们考虑钦定一个数量限制。设 $dp_{i,j}$ 表示到了第 $i$ 个字符，一共选了 $j$ 个硝硼铀。用 pair<string,string> 存。转移有：dp[i][j] = max(dp[i][j],{dp[i - 1][j - 1].first + s[i - 1],dp[i - 1][j - 1].second + t[i - 1]。s[i - 1] 是因为 $s$ 和 $t$ 是 0-index。

就这个“没限制就钦定一个限制”这操作给我整懵了，这谁想得到啊？

没逝，这次见过了没准下次就想得到了呢？

T3 # Link to T3

神秘小算法。

我们把每次删掉一个数扔掉，因为处于最优性考虑你不会去选同样的一个数。那么先掏一个样例：4 7 3 6 1 2 5，最先取的肯定是 6，其次是 3 或者 1。经过一番暴力，我们发现，对于 $\forall i \in [1,n]$ 的每个 $a_i$ 可选次数形如 1 2 3 4 3 2 1。我们考虑答案是在值域上的一个区间，那么我们把 $b_i$ 设为 $i$ 的可选次数。那么 $b$ 就是 3 2 3 1 1 4 2。考虑 $[2,4]$，我们看到 4 的出现次数最小，首先选它。选完，$b$ 在 $[2,4]$ 上变成了 1 2 0。以此类推。

考虑一个 $pre_i = \sum_{j = l}^{r}[b_j \le i]$。很明显要有 $\forall i \in [1,n],i - b_i \ge 0$。用线段树维护这个 $i - pre_i$ 区间最小值。区间合法即为区间最小值 $>0$ 用双指针解决。

感谢每一位愿意为我讲题的人。

T4 # Link to T4

没看，考场骗了 40。

总而言之：T1 看到是概率与期望就怕了，没写。T2 的暴力都打挂了我是真的。。。T3 一点思路都没有。就 T4 骗了 40。还是得多练。

T2 那个“没限制就钦定一个限制”是真的没绷住。