1 条题解
-
0
题目分析
20 分
暴力搜索即可。
40 分
需要挖掘一些性质,注意到可以把 分成若干极长子段,每段的元素都相同。
容易知道,每段的元素是什么并不重要,只要知道划分方式就能推出唯一的 。
比较特殊的情况是除了开头的段与结尾的段,如果有长度为 的段,其等价于两个长度为 的段,对应的 都是
1 1,于是直接钦定除了开头和结尾不能出现长度为 的段。考虑直接 dp, 表示到了 划分出了 段,这样是 。
60 分
注意到划分出 段的方案是等价的,因为只要求 在 中都至少出现了一次。
所以第二位只需要 dp 到 ,这样是 。
正解
注意到转移是标准的求一个区间的和,前缀和优化即可。时间复杂度 。
- 1
信息
- ID
- 75
- 时间
- 1000ms
- 内存
- 256MiB
- 难度
- 5
- 标签
- 递交数
- 1
- 已通过
- 1
- 上传者