文章

20

粉丝

146

获赞

10

访问

41.5k

头像
解题思路:找有多少个连续1
P1916 清华大学2022年机试题
发布于2023年3月17日 18:12
阅读数 2.1k

这个题数据量比较大,是1e5,

题目要求找有多少个全为1长度至少为M的子串,

其实本质就是找连续1的数量,

假设M是3

如果找到一段连续1的长度小于3,那么答案就是0

如果找到一段连续1的长度是3,那么答案就是1

如果找到一段连续1的长度是4,那么答案就是2+1=3

如果找到一段连续1的长度是5,那么答案就是3+2+1=6

...

推导出

如果找到一段连续1的长度是k,那么答案就是1+2+3+....+(n-3+1)

这是一个累加和公式,ans = (n-3+1) * (n-3+1 + 1) / 2

换成M就是ans = (n-M+1) * (n-M+2) / 2

最终把所有的ans全部加起来,也就是所有的不同长度的连续1的结果和。

时间复杂度是线性的,也就是O(1e5)

登录查看完整内容


登录后发布评论

暂无评论,来抢沙发