首页 > 魔法学院(hard version)
开通博客写题解
头像 kryptós°
发表于 2021-11-13 11:07:10
BC用优先队列做的（大概是数据不够强偷鸡了）。 思路比较好理解：提前对左端点排序，对于某个点保证所有可行的修改方法都在优先队列内。那么只要到一个新的点判断优先队列里的队头元素是否还适用于当前点，如果不行一直pop；可行就不管（贪就完事了）。 复杂度算不明白我就不算了。 #include <bi 展开全文
去ta的博客 赞 (4) 回复(0) 收起
头像 我是菜鸡小仙女
发表于 2021-11-13 08:15:37
题目描述 亚可喜欢上了收集不包括空格的可见字符(ASCII码为33~126)，在她眼中，一个字符的价值为其ASCII码大小，比如’a’的价值为97。 目前她已经收集了n个不包括空格的可见字符，第i个字符S[i]。可是她想要把自己收集的nn个字符的价值和最大化，因此去请求了戴安娜的帮助。戴安娜有m种魔 展开全文
去ta的博客 赞 (3) 回复(1) 收起
头像 小琢卷不动
发表于 2021-11-13 09:03:23
接着上一篇题解的分析过程，我们还是考虑把操作离线下来看看怎么搞一搞。 注意到我们可以更改排序的 cmp 顺序，原来是从小权值到大权值，这是为了方便进行区间推平。 现在我们换过来，从大权值到小权值，这样做的好处就是保证每个位置至多被修改一次，链表维护一下下一个被修改的位置就好了。 时间复杂度 O(n) 展开全文
去ta的博客 赞 (2) 回复(0) 收起
查看本题
查看本题讨论

相关比赛

等你来战

查看全部
牛客竞赛，专业的竞技算法训练平台

扫描二维码，进入QQ群

扫码关注“比赛自动姬”