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

1. 假设最后的结果左边界为i，右边界为j，那么当左边界为i，右边界在j右边时，计算出的结果一定大于等于k，同样的，如果右边界在j左边，结果一定小于等于k。同理，固定j变化i可以得到相似的结论。
2. 所以，使用i和j两个位置，先将j一直向右移动，一旦i j超过了k，那么就将i向右移动。直到满足等于k为止，这样就能找到所有可能等于k的区间。
3. 可以使用类似前缀和的思想，不停维护i j之间的0 1序列数量。

#include <bits/stdc++.h>
using namespace std;

int main() {
    int n;
    long long k;
    cin >> n >> k;
    string s;
    cin >> s;

    int i = 0, j = 0;
    int cnt0 = 0, cnt1 = 0;
    long long cnt = 0;
    int flag = 1;
    while (j != n) {
        // cout << i << ' ' << j << ' ' << cnt << '\n';
        // if (i > 40)
        //     printf("%d %d %lld\n", i, j, cnt);
        if (flag == 1) {
            if (s[j] == '1') {
                cnt1++;
                cnt += cnt0;
                if (cnt == k) {
                    cout << i + 1 << ' ' << j + 1 << '\n';
                    return 0;
                }
            } else if (s[j] == '0') {
                cnt0++;
            }
        } else if (flag == 2) {
            if (s[i - 1] == '1') {
                cnt1--;
            } else if (s[i - 1] == '0') {
                cnt -= cnt1;
                cnt0--;
                if (cnt == k) {
                    cout << i + 1 << ' ' << j + 1 << '\n';
                    return 0;
                }
            }
        }
        if (cnt < k) {
            j++;
            flag = 1;
        } else if (cnt > k) {
            i++;
            flag = 2;
        }
    }
    cout << -1 << '\n';
    return 0;
}