首页 > 试题广场 >

小红的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}子序列：从字符串中删除任意个（可为零）字符后得到的字符串，保留剩余字符原有相对顺序。

输入描述:
\hspace{15pt}第一行输入两个整数 n,k\left(1\leqq n\leqq 2\times10^{5};\ 1\leqq k\leqq 10^{10}\right)——字符串长度与目标子序列数量。 
\hspace{15pt}第二行输入一个长度为 n 的 01 串 s（下标从 1 开始）。


输出描述:
\hspace{15pt}若不存在满足要求的区间，输出单独一行-1；否则输出两个整数 l,r\left(1\leqq l\leqq r\leqq n\right) 表示区间端点（输出任意一组均可）。
示例1

输入

4 2
0011

输出

1 3

说明

子串 s_{1..3}=\texttt{ 内的 01 子序列共有 2 个：s_1s_3、s_2s_3。
示例2

输入

4 2
1110

输出

-1
算法知识视频讲解
添加回答
Python3
牛客277605456号头像 牛客277605456号
//超时笨蛋
n, k = map(int, input().split())
s = input()
ans =[]
for i in range(len(s)):
    for j in range(i, len(s)):
        t=0
        t2 = 0
        st = s[i:j]
        for q in st:
            if q == '0':
                t+=1
            else:
                t2 = t2 + t
        if t2 == k:
            ans = [i+1, j]
            break
        elif t2 > k:
            break
        else:
            continue
    if ans != []:
        break
if ans == []:
    print(-1)
else:
    print(*ans)
       
发表于 2025-04-13 22:46:47 回复(0)
Python3
牛客534940159号头像 牛客534940159号
n,k=map(int,input().split())
s=input()
cnt0,cnt1=0,0
l,r=0,0
if s[0]=='0':cnt0+=1
if s[0]=='1':cnt1+=1
num=0
while l<n and r<n:
    if num==k:
        print(l+1,r+1)
        break
    elif num<k and r<n-1:
        r+=1
        if s[r]=='0':
            cnt0+=1
        else:
            num+=cnt0
            cnt1+=1
    elif num<k and r==n-1:
        print(-1)
        break
    else:
        if s[l]=='0':
            num-=cnt1
            cnt0-=1
        else:
            cnt1-=1
        l+=1
发表于 2025-03-31 14:48:27 回复(0)
提交观点

问题信息

双指针
难度：
2条回答 418浏览

热门推荐

相关试题

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

扫一扫，把题目装进口袋

求职之前，先上牛客

扫描二维码，进入QQ群

扫描二维码，关注牛客公众号