首页 > 试题广场 >

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

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

热度指数：6179 时间限制：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 展开全文

冯飞宇

发表于 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 = 展开全文

番禺小韭菜

发表于 2025-03-04 17:34:22

#include <bits/stdc++.h> using namespace std; typedef long long LL; int main() { LL n, k; cin >> n >> k; string s; 展开全文

zy还能再战

发表于 2025-03-26 17:04:56

#牛客春招刷题训练营# + 链接首先要理解题意（过于简洁以至于刚开始愣了）01子序列指的就是 "01" 这样两位，那就很显然了计数数组辅助双指针，直接over #include <iostream> using namespace std; using ll = l 展开全文

问题信息

双指针

难度：

9条回答 101收藏 416浏览

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

输入描述:

输出描述:

输入

输出

说明

输入

输出

问题信息

热门推荐

相关试题