∆ Craft

Prob. 1

Desc. & Link.

有想法。

printf( "nan" );

Prob.2

Desc. & Link.

没读懂

Prob. 3

Desc. & Link.

定义 $f_{i,j,0/1}$ 表示个寂寞。

$$f_{i,i,0/1}=|a_{i}|\times I$$ $$f_{i,j,0}=\min\{f_{i+1,j,0}+(a_{i+1}-a_{i})\times(I-j+i),f_{i+1,j,1}+(a_{j}-a_{i})\times(I-j+i)\} \\f_{i,j,1}=\min\{f_{i,j-1,1}+(a_{j}-a_{j-1})\times(I-j+i),f_{i,j-1,0}+(a_{j}-a_{i})\times(I-j+i)\}$$ $$\mathrm{ANS}=\max\{i\times m-\min\{f_{l,r,0/1}\}\}$$

Over.

Prob. 4

Desc. & Link.

转化一下，把 $\texttt{C,T}$ 换成左括号和右括号。

把左括号赋值为 $1$，右括号 $-1$。

把这个 $1/-1$ 序列设为 $A$

那么所有前缀中 $\texttt{C}$ 的个数大于等于 $\texttt{T}$ 的个数即要求前缀和不能出现负数。

询问即求：定义 $P_{i}=\sum_{j=1}^{i}A_{j},S_{i}=\sum_{j=i}^{n}A_{j}$，对于每次询问回答：

$$\begin{cases}0,\min\{\min\{P_{l,l+1,\cdots,r}\},\min\{S_{l,l+1,\cdots,r}\}\}\ge0 \\ |\min\{\min\{P_{l,l+1,\cdots,r}\},\min\{S_{l,l+1,\cdots,r}\}\}|,\texttt{otherwise}\end{cases}​$$

这个东西 $\texttt{has been hacked by the Big Sample.}$

一个可能的死亡原因：前缀后缀都要判断可能会引起一些错误。

处理方法：那么先处理前缀，后缀减一下再处理。

（这不是问题）

另一个可能的死亡原因：$\min\{\min\{P_{l,l+1,\cdots,r}\},\min\{S_{l,l+1,\cdots,r}\}\}$ 可能取到多处。

处理方法：。

（这也不是问题）

Algo. 0

W·violence·gy

Algo. 1

莫队，时间复杂度 $\Theta(n\sqrt{n}\log_{2}n)$。

Algo. 2

晓求不得。

∆ Solution

Prob. 4

转化一下成最大子段和，化式子过程懒得写了。