2018-team11-005

从 Trac 迁移的文章

这是从旧校内 Wiki 迁移的文章，可能存在一些样式问题，您可以向 memset0 反馈。

原文章内容如下：

 [[Image(hw7.png)]]
== 总结 ==
== 孙志博 ==
一共过了算3个题？
先是发现D题是一个推式子简单题，但是第一次推的时候出了点失误，一切推倒重来，导致D题一个小时才过。
过了D题接着自闭，觉得A题似乎自己做过，开始往分块或者莫队方向考虑，但是一个小时过去都没什么想打，然后突然想到了正解，俩个半小时A掉。
然后发现F就是个斜率优化dp，但是要动态加点，自己已经忘记了如何动态维护凸包，这个时候Heltion学长教了我姿势更高的斜率优化，1A掉F题~
== 题解 ==
A.Max Query
题意：多组询问区间mex
做法：用线段树维护每一个数最后一次出现的下标，查询最小的未出现过的数即可。
D.Short Enough Task
题意：求长度为n，字符集为k的期望回文子串个数。
做法：枚举回文串长度，列出式子直接运算即可。
F.Just Another Sequence Problem
题意：给定一个的序列，问如何划分成若干段，使相邻每段乘积之和最大。
做法：考虑dp，f[i][j]表示前i位，上一段以j结尾的最大值，观察转移方程是一个斜率优化的形式。
　　　f[i][j]=max{f[k][j]+(s[j]-s[k-1])*(s[i]-s[j-1])}，对于每一个k都对应一组k,b即一条直线，考虑某一x在哪条直线上取得最大值，维护一个下凸壳。

总结

孙志博

一共过了算3个题？

先是发现D题是一个推式子简单题，但是第一次推的时候出了点失误，一切推倒重来，导致D题一个小时才过。

过了D题接着自闭，觉得A题似乎自己做过，开始往分块或者莫队方向考虑，但是一个小时过去都没什么想打，然后突然想到了正解，俩个半小时A掉。

然后发现F就是个斜率优化dp，但是要动态加点，自己已经忘记了如何动态维护凸包，这个时候Heltion学长教了我姿势更高的斜率优化，1A掉F题~

题解

A.Max Query

题意：多组询问区间mex

做法：用线段树维护每一个数最后一次出现的下标，查询最小的未出现过的数即可。

D.Short Enough Task

题意：求长度为n，字符集为k的期望回文子串个数。

做法：枚举回文串长度，列出式子直接运算即可。

F.Just Another Sequence Problem

题意：给定一个的序列，问如何划分成若干段，使相邻每段乘积之和最大。

做法：考虑dp，f[i][j]表示前i位，上一段以j结尾的最大值，观察转移方程是一个斜率优化的形式。

　　　f[i][j]=max{f[k][j]+(s[j]-s[k-1])*(s[i]-s[j-1])}，对于每一个k都对应一组k,b即一条直线，考虑某一x在哪条直线上取得最大值，维护一个下凸壳。

附加文件