首页 > 试题广场 >

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

[编程题]小红的01子序列构造（easy）
  • 热度指数：8398 时间限制：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
佳162头像 佳162
def optimized_main():
    import sys
    input = sys.stdin.read().split()
    ptr = 0
    n = int(input[ptr])
    k = int(input[ptr+1])
    ptr +=2
    s = input[ptr] if ptr < len(input) else ""
   
    # 预处理前缀0（1-based）和后缀1（1-based）
    pre0 = [0]*(n+2)
    suf1 = [0]*(n+2)
    for i in range(1, n+1):
        pre0[i] = pre0[i-1] + (1 if s[i-1] == '0' else 0)
    for i in range(n, 0, -1):
        suf1[i] = suf1[i+1] + (1 if s[i-1] == '1' else 0)
   
    # 计算总01数量
    total = 0
    cnt0 = 0
    for c in s:
        if c == '0':
            cnt0 +=1
        else:
            total += cnt0
    if total < k:
        print(-1)
        return
   
    # 双指针核心逻辑
    l = 1
    current_cnt = 0
    cnt0_in = 0  # [l..r]内的0数量
    for r in range(1, n+1):
        c = s[r-1]
        if c == '0':
            cnt0_in +=1
        else:
            current_cnt += cnt0_in
       
        # 若当前数量超过k，移动左指针
        while current_cnt > k and l <= r:
            c_l = s[l-1]
            if c_l == '0':
                # 移除该0，需要减去后续所有1的数量（[l+1..r]的1）
                cnt1 = suf1[l+1] - suf1[r+1]
                current_cnt -= cnt1
                cnt0_in -=1
            l +=1
         
        # 找到目标
        if current_cnt == k:
            print(l, r)
            return
   
    print(-1)

if __name__ == "__main__":
    optimized_main()


发表于 2026-01-24 16:45:45 回复(0)
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)
提交观点

问题信息

双指针
难度：
3条回答 597浏览

热门推荐

相关试题

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

扫一扫，把题目装进口袋

求职之前，先上牛客

扫描二维码，进入QQ群

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