Vote

题面

考场

一开始觉得应该是越靠近旁边的越容易被选上，但是写了一个小程序一看不太对。发现已选一定人之后怎么求出他们中的贡献是一定要求的所以开始推这个式子。

首先考虑 $f_i$ 表示前 $i$ 个是选上的，那么向下一个转移。然后可以插一对进去，可以两个赞成，两个反对或者一个赞成一个反对。一个赞成一个反对可以直接转移，但是另外两种情况就不行了，然后我开始走弯路，走了很远很远。。（ $f_{i,~j}$ 表示前 $i$ 个 $j$ 被选了没有之类的。。）

然后发现还是暴力吧。就打了暴力，当然前面是一个错的贪心，因为后来我不知道为什么就想着用靠近 $0.5$ 的数。（那样是最小吧。。）

出分： $20pt.$ 果然，数据大的点 $WA$ 了。

正解

没错，答案一定是一个前缀后缀，证明如下：

考虑一个数 $p_i$ 的贡献：$Pp_i+Q(1-p_i)=(P-Q)p_i+Q. $其中$ P,~Q$ 是之前的答案，发现它其实是一个一次函数，所以极致一定在左右两端取到。证完。

那么左右两端可以 $DP$ 一下了。右边同理所以考虑左边。

$f_{i,~j}$ 表示前 $i$ 个中 $j$ 个赞成的结果。那么转移就从上一个赞成还是反对转移。具体就是：

$\Large f_{i,~~j}=f_{i-1,~~j-1}\times p~~+f_{i - 1,~~j}\times (1-p_i).$

最后枚举一下 $k$ 个数里面有几个在左边，几个赞成就好，注意答案是对每种选法取 $\max.$

$code:$ https://paste.ubuntu.com/p/qpwqWxVhdk/

Point

题面

考场

没怎么看，随便想出来了一个 $n^2$ 的暴力，就是枚举答案在哪里，然后向左右扩展找到最远的地方更新答案。

出分： $30pt..RE$ 了。。数组开小了。

重开数组之后： $95pt..????$ 说好的 $5e5???$ 你让 $n^2$ 过？

正解

$n^3,n^2$暴力~~

数据水到一定程度。。。所谓的 $n^3$ 过 $5e5,~$ 暴力碾表算。。

题解给的正解

因为对于一段序列，如果能够是答案，那么最小的一个数一定就是那个关键数，也一定是序列中所有数的 $\gcd.$ 那么考虑用 $ST$ 表存 $\gcd$ 和 $\min$ ，二分答案判断就好，复杂度是 $O(n\log^2 n)$ 。

但是它 $T$ 了！！！这玩意没有暴力跑得快！！！

出题人在题解里面说要卡常才能过，但是暴力过了。。

唯一解释就是出题人卡了 $\gcd!!$ 如果所有的 $\gcd$ 卡满可能是更劣的。。

$upd…:$ 不。。其实我发现是 $math.h$ 里面的 $\log_2$ 这玩意跑的特别慢。

~~但是他放了暴力。。~~

$code:$ （ $T$ 了的，~~当然可能~~就是我写丑了。）https://paste.ubuntu.com/p/VvckND36vP/

优秀的线性做法真正的标算

记得最一开始的 $n^2$ 暴力吗？这个可以优化的。因为每次是向左扩展一些，向右扩展一些，那么记一个点 $i$ 向右扩展到的点为 $r_i$ ，向左是 $l_i$ ，那么在区间 $[l_i,~~r_i] $中间的点就不可能有更优的答案了，因此可以跳过他们。因此实现起来可以向两个方向扫一遍，每次向右扩展到$ r_i $的时候就把$ [i,~~r_i] $的$ r $都记成$ r_i $，然后从$ r_i + 1$ 继续找即可。这样每个点只会被扩展一次，所以就是线性的了。！

$code:$ https://paste.ubuntu.com/p/yKH42tkcpP/

Actor

题面

考场

$emm..$ 不会。。考虑暴力吧。

然后第一个点特别小，就打了个表，其他的点放弃了。

出分： $13pt.$

正解

神仙 $DP~+$ 优化。？咕。