普及23题解

A

读入的时候遍历检查一遍,看有多少个字符 .

B

暴力模拟即可。即 从第 项到第 项,每次 。就可求出 。复杂度

C

考虑倒推。如果当前最后一步向右走那么就相当于把这个字符插入到最前面,如果是向左走就相当于插入到最后面。直接用一个 维护一下即可。

D

​考虑按照 从小往大排序,考虑 表示前 个数,第 个数必须选最多能选多少个。转移为:

​考虑如何优化转移,我们维护表示:

​那么,

​考虑 都可以在 的时间内求得。

考虑

​所以时间复杂度是 的。

全部评论

相关推荐

点赞 评论 收藏
转发
点赞 收藏 评论
分享
牛客网
牛客企业服务