题解 | #小红的01子序列构造（easy）#

题目链接

题目描述

给定一个仅由字符 '0' 和 '1' 组成的字符串 $s$ ，长度为 $n$ 。小红想找到一个闭区间 $[l, r]$ （ $1 \le l \le r \le n$ ），使得在子串 $s[l..r]$ 中，恰好存在 $k$ 个严格等于 "01" 的子序列。请你输出任意一个满足条件的区间；若不存在，则输出 -1。

输入:

第一行输入两个整数 $n$ 和 $k$ ，分别代表字符串长度与目标子序列数量。( $1 \le n \le 2 \cdot 10^5$ , $1 \le k \le 10^{10}$ )
第二行输入一个长度为 $n$ 的 01 串 $s$ 。

输出:

若不存在满足要求的区间，输出一行 -1。
否则输出两个整数 $l$ 和 $r$ ，表示区间端点（1-based）。输出任意一组解即可。

解题思路

本题要求寻找一个子串，其 "01" 子序列的数量恰好为 $k$ 。注意到数据范围 $n \le 2 \cdot 10^5$ ，一个 $\mathcal{O}(n^2)$ 的解法（如暴力枚举所有子串）会超时。我们需要一个更高效的算法。

我们可以采用固定左端点，二分查找右端点的策略。对于一个固定的左端点 $l$ ，当右端点 $r$ 向右移动时，子串 $s[l..r]$ 中 "01" 子序列的数量是单调不减的。这个单调性让我们可以在 $\mathcal{O}(\log n)$ 的时间内为每个 $l$ 找到一个合适的 $r$ 。

为了在二分查找中快速计算任意子串的 "01" 子序列数，我们可以使用前缀和技巧。

算法步骤如下：

预处理前缀和：创建三个前缀和数组（长度为 $n+1$ ，0-based），在 $\mathcal{O}(n)$ 时间内计算：
- zeros[i]: 字符串前 $i$ 个字符（s[0...i-1]）中 '0' 的数量。
- ones[i]: 字符串前 $i$ 个字符中 '1' 的数量。
- pairs[i]: 字符串前 $i$ 个字符中 "01" 子序列的总数。pairs[i] 的递推式为 pairs[i] = pairs[i-1] + (s[i-1] == '1' ? zeros[i-1] : 0)。
$\mathcal{O}(1)$ 计算子串 "01" 数：利用前缀和数组，我们可以在 $\mathcal{O}(1)$ 时间内计算出任意子串 $s[l..r]$ （0-based index）的 "01" 子序列数量。公式为： count = (pairs[r+1] - pairs[l]) - zeros[l] * (ones[r+1] - ones[l]) 该公式的原理是：从前缀 s[0..r] 的总 "01" 数中，减去前缀 s[0..l-1] 的总数，再减去所有'0'在 s[0..l-1] 中而 '1' 在 s[l..r] 中的“跨界”子序列数。
主循环与二分查找：
- 外层循环遍历所有可能的左端点 $l$ (从 $0$ 到 $n-1$ ) 。
- 对于每个 $l$ ，在 $[l, n-1]$ 范围内对右端点 $r$ 进行二分查找。
- 在二分查找中，计算中间点 mid 对应的子串 s[l..mid] 的 "01" 子序列数。
  - 若数量等于 $k$ ，则找到答案 $[l+1, mid+1]$ ，输出并终止。
  - 若数量小于 $k$ ，则需要在右半部分 [mid+1, hi] 查找。
  - 若数量大于 $k$ ，则需要在左半部分 [lo, mid-1] 查找。
无解情况：如果遍历完所有 $l$ 仍未找到解，则输出 -1。

该算法的总时间复杂度为 $\mathcal{O}(n \log n)$ ，可以满足题目的时间要求。

代码

cpp
java
python

#include <iostream>
#include <string>
#include <vector>

using namespace std;

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);

    int n;
    long long k;
    cin >> n >> k;
    string s;
    cin >> s;

    vector<long long> zeros(n + 1, 0);
    vector<long long> ones(n + 1, 0);
    vector<long long> pairs(n + 1, 0);

    for (int i = 0; i < n; ++i) {
        zeros[i + 1] = zeros[i] + (s[i] == '0' ? 1 : 0);
        ones[i + 1] = ones[i] + (s[i] == '1' ? 1 : 0);
        pairs[i + 1] = pairs[i] + (s[i] == '1' ? zeros[i] : 0);
    }

    auto count_subsequences = [&](int l, int r) {
        if (l > r) return 0LL;
        // 0-based l, r
        return (pairs[r+1] - pairs[l]) - zeros[l] * (ones[r+1] - ones[l]);
    };

    for (int l = 0; l < n; ++l) {
        int low = l, high = n - 1;
        int ans_r = -1;
        while (low <= high) {
            int mid = low + (high - low) / 2;
            long long current_k = count_subsequences(l, mid);
            if (current_k == k) {
                ans_r = mid;
                break; 
            }
            if (current_k < k) {
                low = mid + 1;
            } else {
                high = mid - 1;
            }
        }
        if (ans_r != -1) {
            cout << l + 1 << " " << ans_r + 1 << endl;
            return 0;
        }
    }

    cout << -1 << endl;

    return 0;
}

import java.util.Scanner;

public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        long k = sc.nextLong();
        String s = sc.next();

        long[] zeros = new long[n + 1];
        long[] ones = new long[n + 1];
        long[] pairs = new long[n + 1];

        for (int i = 0; i < n; i++) {
            zeros[i + 1] = zeros[i] + (s.charAt(i) == '0' ? 1 : 0);
            ones[i + 1] = ones[i] + (s.charAt(i) == '1' ? 1 : 0);
            pairs[i + 1] = pairs[i] + (s.charAt(i) == '1' ? zeros[i] : 0);
        }

        for (int l = 0; l < n; l++) {
            int low = l;
            int high = n - 1;
            int ansR = -1;
            while (low <= high) {
                int mid = low + (high - low) / 2;
                long currentK = countSubsequences(l, mid, zeros, ones, pairs);
                
                if (currentK == k) {
                    ansR = mid;
                    break;
                }
                if (currentK < k) {
                    low = mid + 1;
                } else {
                    high = mid - 1;
                }
            }
            if (ansR != -1) {
                System.out.println((l + 1) + " " + (ansR + 1));
                return;
            }
        }

        System.out.println(-1);
    }

    private static long countSubsequences(int l, int r, long[] zeros, long[] ones, long[] pairs) {
        if (l > r) return 0;
        // 0-based l, r
        return (pairs[r + 1] - pairs[l]) - zeros[l] * (ones[r + 1] - ones[l]);
    }
}

def solve():
    n, k = map(int, input().split())
    s = input()

    zeros = [0] * (n + 1)
    ones = [0] * (n + 1)
    pairs = [0] * (n + 1)

    for i in range(n):
        zeros[i + 1] = zeros[i] + (1 if s[i] == '0' else 0)
        ones[i + 1] = ones[i] + (1 if s[i] == '1' else 0)
        pairs[i + 1] = pairs[i] + (zeros[i] if s[i] == '1' else 0)

    def count_subsequences(l, r):
        # 0-based l, r
        if l > r:
            return 0
        return (pairs[r + 1] - pairs[l]) - zeros[l] * (ones[r + 1] - ones[l])

    for l in range(n):
        low, high = l, n - 1
        ans_r = -1
        while low <= high:
            mid = (low + high) // 2
            current_k = count_subsequences(l, mid)
            if current_k == k:
                ans_r = mid
                break
            elif current_k < k:
                low = mid + 1
            else:
                high = mid - 1
        
        if ans_r != -1:
            print(l + 1, ans_r + 1)
            return

    print(-1)

solve()

算法及复杂度

算法：前缀和 + 二分查找
时间复杂度： $\mathcal{O}(n \log n)$ 。前缀和预处理需要 $\mathcal{O}(n)$ 。外层循环遍历 $n$ 个左端点，每次二分查找需要 $\mathcal{O}(\log n)$ 。
空间复杂度： $\mathcal{O}(n)$ ，用于存储三个前缀和数组。