日记

今天也是不颓。

所以到底是颓还是不颓？

Blossom# Link to

没搞懂。

等洛谷上有题解了再去看一遍。

Roller Coaster# Link to

神 tm Adhoc。

考虑对于一个已经选好的路径，我们找到高度相差最大的两个点，显然有结论：在这俩点里转来转去肯定是比当前路径更优的。于是我们直接找到一对 $|h_u - h_v|$ 最大的 $u,v$，答案就是 $\frac{|h_u - h_v|}{2}$

只能说我太蠢了。

Big XOR Game# Link to

自己想到了 $75\%$，还是挺不错的。
下次能想到 $100\%$ 就更好了。

想到之前考试有道题。设所有的数异或和为 $sum$，当 $sum = 0$ 时肯定平局。否则一定在 $sum$ 的最高位决出胜负。问题转化为：有 $n$ 个数，里面有奇数个 $1$，先后手轮流取，取了奇数个 $1$ 的人获胜。

考虑分类讨论，设有 $cnt$ 个 $1$：

有偶数数个 $0$（$n$ 为奇数）

• 当 $cnt \equiv 1 \pmod 4$
  Alice 先取一个 $1$，之后都和 Bob 取相同的。Alice 取了奇数个 $1$，Alice 得了 MVP！！！
• 当 $cnt \equiv 3 \pmod 4$
  Bob 总和 Alice 取相同的，Bob 取了奇数个 $1$，Bob 得了 MVP！！！

有奇数个 $0$（$n$ 为偶数）

• 当 $cnt \equiv 1 \pmod 4$
  同上情况 1，必胜。
• 当 $cnt \equiv 3 \pmod 4$
  Alice 取了 $0$，变成上面的情况 2 的后手，必胜。

Bracket Sequence# Link to

唐题。

我们考虑 dp。$dp_i$ 表示到 $i$ 的 h 的数量（其实就是方案数啦）。考虑转移：$dp_i = dp_{i - 1} + \sum dp_j$。其中 $j$ 满足 $(j,i]$ 是一个合法的括号序列。

考虑如何快速求这个 $\sum dp_j$。我们想到记录一个 $bel_i$ 表示将 ( 视为 $1$，) 视为 $-1$ 的前缀和。维护一个 $sum_j$ 表示所有 $bel_i = j$ 的 $dp_i$ 之和。但是我们发现一个问题：这个括号序列：()()，第 $3$ 个会从第 $1$ 个转移而来。但是很显然，)( 并不是一个合法的括号序列。我们考虑如何 ban 掉这种情况。

我们发现出现这种情况当且仅当有 $k \in (j,i]$ 满足 $bel_k < bel_i$。我们考虑开一颗线段树。下标为 $i$ 的地方维护 $bel_i$ 出现的最后一个地方。对于每个 $bel$ 开一个队列。在线段树上查询 $lst$ 表示 $[1,bel_i - 1]$ 的区间最小值，把队列里在 $lst$ 之前的全扔出去，并从 $sum_{bel_i}$ 中减去。然后转移 $dp_i = dp_{i - 1} + sum_{bel_i}$。然后更新线段树，将 $i$ 压进队列并将 $sum_{bel_i}$ 加上 $dp_i$。

最后的答案就是 $dp_n$。

还是 赛格门特吹 好用。

Colourful Bottles# Link to

听 dpfs 讲的。

考虑 dp，设 $dp_i$ 表示以 $i$ 结尾，满足 $k$ 连续的最小代价。考虑转移：

其中 $sumw_i$ 表示 $w$ 的前缀和。$sumc_i$ 表示与 $i$ 颜色相同的前缀和。第二个方程具体来说就是：删掉 $[j,i]$ 之间的所有数，但是同色的不能删，于是把它加回来。而我们不知道 $j$ 的相同颜色的前驱是啥，于是直接减掉 $sumc_j - w_j$。$j$ 要满足 $[j,i]$ 之间至少有 $k$ 个同颜色的。

考虑优化。对于每个颜色开一个 $min$ 数组表示 $dp_j - sumw_{j - 1} - sumc_j + w_j$ 的最小值。又对于每个颜色开一个队列。当队列长度等于 $k - 1$ 时，就把对头取出，更新 $min$ 数组。然后转移 $dp_i = \min\{dp_{i - 1} + w_i,min_{c_i} + sumw_i + sumc_i\}$。转移完了扔进队列。

后日谈 # Link to 后日谈

明天的模拟赛和重庆八中联考。又可以丢 CW 的脸了。

每次一看到这个高达 $\color{#ff0000}16.7\%$ 的得分率我就头大。明明打的对的题，总是因为一些莫名其妙的愿因挂分。要么是实现太优秀，常数爆炸，要么是没注意细节。

There’s no time left.