首页 > 小红的01子序列构造（hard）
开通博客写题解
头像 夏日之竹
发表于 2025-03-17 22:38:58
纯纯暴力解不等式，复杂度O(n+m)。只要你找到关系式，肯去算那一坨方程组和不等式组，剩下就都好办了。 """ 核心关系式: 若两个相邻区间:[a,b](有xa个0,ya个1,ka个01子序列), [b+1,c](有xb个0,yb个1,kb个01子序列) 则合成的新区间 展开全文
去ta的博客 赞 (8) 回复(0) 收起
头像 LBR_
发表于 2025-05-14 14:31:03
写起来很麻烦的一道题。不过思路还算简单。 首先不考虑套娃的情况。len的长度内有a个0和b=len-a个1，最多会产生a*b个01子序列。在范围内可以使用如下的策略进行填充。（对应代码中的fill函数）从左到右，记录当前剩余未填充的1数量cnt1，还需产生的01序列数量k。 如果k>=c 展开全文
去ta的博客 赞 (0) 回复(0) 收起
查看本题
查看本题讨论

相关比赛

等你来战

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

扫描二维码，进入QQ群

扫码关注“比赛自动姬”