【题解】牛客IOI周赛23-普及组

 A

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

B

暴力模拟即可。即 i 从第 n 项到第 0 项,每次 。就可求出 f(x)。复杂度 O(nm)。

C

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

D

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



考虑如何优化转移,我们维护mx[z]表示:



那么,



考虑 mx 和 dp 都可以在 的时间内求得。

考虑

所以时间复杂度是 O(nlogn) 的。
全部评论

相关推荐

我是没经验的毕业生,这啥情况啊会不会是hr在刷kpi
JamesGosli...:字节boss属于是群发了,我都快入职字节了,其他部门还在和我boss打招呼
点赞 评论 收藏
分享
05-14 20:34
门头沟学院 Java
窝补药贝八股:管他们,乱说,反正又不去,直接说680
点赞 评论 收藏
分享
评论
3
1
分享

创作者周榜

更多
牛客网
牛客网在线编程
牛客网题解
牛客企业服务