首页 > 试题广场 >

小红的01子序列构造（easy）

[编程题]小红的01子序列构造（easy）

热度指数：8227 时间限制：C/C++ 3秒，其他语言6秒空间限制：C/C++ 256M，其他语言512M
算法知识视频讲解

$\hspace{15pt}$ 给定一个仅由字符 $\tt 0,1$ 组成的字符串 $s$ ，长度为 $n$ 。小红想找到一个闭区间 $[l,r]$ 使得在子串 $s_{l..r}$ 中，恰好存在 $k$ 个严格等于 $01$ 的子序列（即选取下标 $i<j$ ，满足 $s_i=\texttt{0},\ s_j=\texttt{1}$ ）。
$\hspace{15pt}$ 请你输出任意一个满足条件的区间；若不存在，则输出 $-1$ 。

【名词解释】
$\hspace{15pt}$ 子序列：从字符串中删除任意个（可为零）字符后得到的字符串，保留剩余字符原有相对顺序。

输入描述:

第一行输入两个整数 ——字符串长度与目标子序列数量。 
第二行输入一个长度为  的 01 串 （下标从  开始）。

输出描述:

若不存在满足要求的区间，输出单独一行-1；否则输出两个整数  表示区间端点（输出任意一组均可）。

示例1

输入

4 2
0011

输出

1 3

说明

子串  内的  子序列共有  个：、。

示例2

输入

4 2
1110

输出

-1

算法知识视频讲解

Gooby114514

发表于 2024-12-24 14:16:34

D 小红的01子序列构造（easy）两种写法，这里都介绍一下：方法1:双指针先考虑一个区间内的子序列如何统计，我们只需要对于每个，看它之前有几个，就是它的贡献。例如对于序列，都是，他们的贡献依次为，所以最后的子序列数为。用双指针枚举区间的左右端点，假设当前区间展开全文

Gnomeshgh112

发表于 2025-03-26 13:44:33

假设最后的结果左边界为i，右边界为j，那么当左边界为i，右边界在j右边时，计算出的结果一定大于等于k，同样的，如果右边界在j左边，结果一定小于等于k。同理，固定j变化i可以得到相似的结论。所以，使用i和j两个位置，先将j一直向右移动，一旦i j超过了k，那么就将i向右移动。直到满足等于k为止，这样就展开全文

牛客856751393号

发表于 2025-03-07 14:56:24

while True: try: n, k = map(int, input().split()) s = input() cnt0 = cnt1 = 0 # 分别存储当前区间0和1的个数 l = r = 0 展开全文

佛系的青年

发表于 2025-03-17 17:57:25

解法参考评论区大佬，虽然用例全能pass，但有个小疑问，l++使num减少，r++使num增大，这样一来一回的过程会不会让num错过k值？ #include <iostream> #include <cmath> using namespace std; typedef lo 展开全文

TQ988

发表于 2025-07-08 16:47:30

import java.util.Scanner; public class Main { public static void main(String[] args) { Scanner in = new Scanner(System.in); int 展开全文

RogeAustine

发表于 2025-12-29 09:27:19

我们将使用滑动窗口来解决这个问题使用L，R两个变量来维护这个滑动窗口，使用cnt1与cnt0来记录窗口内部的0的个数以及1的个数由于区间左侧的1以及区间右侧的0都不会发挥作用，因此就根据是否有效来使用while循环选择性将他们移除 #include <bits/stdc++.h> us 展开全文

Jakeap

发表于 2025-12-29 20:28:31

双指针类型题目：共同特征，在一端区间内满足条件。这题要求在一段区间内满足k个01子序列，那么直接左右指针先指向起点都是s[0]位置。r指针负责往后扩大范围，再者我们分析何时达到k个01子序列，首先0肯定要在1前面才能满足01的要求，前面有多少个0那么在0之后的1都能和其组合，这样我们就要实时记录0和展开全文

冯飞宇

发表于 2025-08-31 19:27:07

#include <iostream> using namespace std; void answer(string str, long long int k) { int len = str.length(); int left = 0, right = 0; 展开全文

牛客754921490号

发表于 2025-12-19 11:09:20

#include <iostream> using namespace std; //每个1前面有几个0就能得到几个01子串 //i+1时如果data[i]为0则要减去后续1数量的子串，为1则不用处理 // k超过了int32的范围，使用cin读取的话，溢出会导致后续字符串读入失败 v 展开全文

垚offer多多

发表于 2025-05-23 12:05:36

import java.util.Scanner; // 注意类名必须为 Main, 不要有任何 package xxx 信息 public class Main { public static void main(String[] args) { Scanner sc = 展开全文

问题信息

双指针

难度：

13条回答 121收藏 554浏览

小红的01子序列构造（easy）

输入描述:

输出描述:

输入

输出

说明

输入

输出

问题信息

热门推荐

相关试题