比赛地址

1D Reversi

按题意模拟即可。

代码

An Invisible Hand

设 $p_i$ 为 $[1,i-1]$ 中最小的数,那么最大收益显然为 $\max_{i=2}^n\{a_i-p_i\}$。

因为 $a_i$ 互不相同,所以我们只要统计有多少个最大值即可。

代码

Integers on a Tree

每次找到已经确定的最小的位置,然后把周围未确定的数设为它加 $1$ 即可。正确性不会证。

代码

Snuke's Coloring 2

显然答案的下界是 $2\left(\max\left\{W,H\right\}+1\right)$。那么要达到这个下界的话,矩形一定经过了 $x=\frac{w}{2}$ 或 $y=\frac{h}{2}$。两种情况是类似的,这里只考虑经过 $y=\frac{h}{2}$ 的情况。

先考虑暴力。枚举左右边界,那么上边界和下边界就是一段区间的最小值和最大值。这样子是 $\mathcal{O}(n^2)$ 的。

考虑优化。我们只从左往右枚举右边界,那么左边界一定是若干个上方的后缀最小值和下方的后缀最大值,可以用两个单调栈维护。我们再开一棵线段树,维护每个点作为左边界时的周长,那么在弹栈的时候我们需要修改一段区间的值,因此支持区间加、区间求最大值即可。

可以参考代码理解。

代码

最后修改:2020 年 08 月 27 日 08 : 05 PM