首页 > AsubB
开通博客写题解
头像 Turgen
发表于 2026-01-28 04:04:08
实际上就是问我们，能找出多少对区间 ，使满足这一段被挖去后，剩余的字符串中有一个子序列是。 观察时间复杂度，大概是 的级别，我们考虑这样一件事： 如果 是合法答案，那么往里缩也一样合法，因为往里缩会减少字符数量。 如果 不是答案，那么扩大一样不合法，因为往外扩会额外增加字符负担 如果 ， 展开全文
去ta的博客 赞 (1) 回复(0) 收起
头像 Laiyiwen_01
发表于 2026-03-07 12:40:50
我们容易发现一个事实，假设 能够成为一个答案，那么 一定也是一个答案，也就是说，当我们固定 时，一定存在一个分界点 ，使得 到 都是答案，而 到 都不是答案。所以对每个 ，考虑二分这个分界点 ，每次只需要判断 是不是答案，然后缩小范围即可。 而判断 是不是答案是容易的，我们可以暴力 展开全文
去ta的博客 赞 (0) 回复(0) 收起
查看本题
查看本题讨论

相关比赛

等你来战

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

扫描二维码，进入QQ群

扫码关注“比赛自动姬”