Contest 985

A

均移到黑色或白色即可。

时间复杂度 \(O\left(n\log n\right)\)。

B

枚举每种开关判断是否有灯只能靠该种开关控制。

时间复杂度 \(O\left(nm\right)\)。

C

最短的木板必然作为某一个木桶的容积，所以我们可以根据 \(l\) 找出可能作为容积的最长的木板。

若可能作为容积的木板总数不足木桶总数就无解。

然后优先将长的作为容积的木板和不可能作为容积的木板配掉，这个比较显然。

最后如果不可能作为容积的木板不足了就继续贪心配一下，每次在剩下的所有木板中取最长或最短的 \(k\) 个，这个更显然了。

时间复杂度 \(O\left(nk\right)\)。

D

首先发现起始高度尽可能大一定是对的，反正可以放相同的高度进行调整。

举个栗子，绿色代表原有的堆，红色代表新增的堆：

\(\color{green}{\texttt{1 2 3 4 3 2 1}}\\\color{green}{\texttt{2 3 4 3 2 1}}\color{red}{\texttt{ 1}}\\\color{green}{\texttt{3 4 3}}\color{red}{\texttt{ 3 }}\color{green}{\texttt{2 1}}\\\color{green}{\texttt{4 3 3}}\color{red}{\texttt{ 3}}\color{green}{\texttt{ 2 1}}\\\color{red}{\texttt{5 }}\color{green}{\texttt{4 3 2 1}}\color{red}{\texttt{ 1}}\)

先判掉最大高度（这里也是起始高度）\(top\) 小于 \(h\) 的情况，此时必定为一个不升序列，且必定为一个下降序列插入至多一堆。

接下来的情况起始高度必定为 \(h\)，此时先是一个不降序列，然后是一个不升序列。同样地，最大高度 \(top\) 越大越好。

可以先把不升序列中 \(1\sim h-1\) 这一段的贡献减掉，即 \(n\gets n-\frac{h\left(h-1\right)}{2}\)。

\[\left(h+top\right)\left(top-h+1\right)-top\leq n
\]

\[top^2-h^2+h\leq n
\]

\[top^2\leq n+h^2-h
\]

\[top=\left\lfloor\sqrt{n+h^2-h}\right\rfloor
\]

接下来要处理多出来的沙袋。注意，最坏情况可能要插入最多两堆，举个栗子：

x x+1 x

x x+1 x+1 x

x x+1 x+1 x+1 x

三堆及以上最大高度可以达到 \(x+2\)，具体可以手玩一下。

时间复杂度 \(O\left(1\right)\)。

E

简单 dp。

令 \(f_i\) 表示前 \(i\) 个数是否有满足条件的分组方案，转移的时候枚举当前组的开头即可，但直接这么做是 \(O\left(n^2\right)\) 的。

发现合法的第一个转移点单调不降，而我们又只关心是否，所以可以用一个普通队列来维护，时间复杂度 \(O\left(n\right)\)。

F

对于每个字母，如果前一个区间中它的哈希值和后一个区间中某个字母的哈希值一样，则这两个区间是匹配的。

至于区间 \(l\sim r\) 的哈希值，它等于 \(r\) 的哈希值减去 \(l-1\) 的哈希值与基数的 \(r-l+1\) 次幂的积，就和你某个进制的数取后面一段是一样的。

时间复杂度 \(O\left(n+m\right)\)。

G

鸽了。

巴特西

Contest 985

A

B

C

D

E

F

G

最新文章

热门文章