2022.10.29每日一題

• 2022 年 10 月 30 日
• 筆記
• 雙指針, 模擬, 每日一題, 算法

Daimayuan Online Judge-01序列

題目描述

我們稱一個字符串為好字符串，指這個字符串中只包含 \(0\) 和 \(1\)。
現在有一個好字符串，求這個字符串中 \(1\) 恰好出現 \(k\) 次的子串有多少個。

輸入格式

第一行給出一個數字 \(k\)，表示子串中 \(1\) 的個數。
第二行給出好字符串。

輸出格式

輸出一個整數，表示好字符串中有多少個符合條件的子串。

數據範圍

\(0≤k≤10^6,|s|≤10^6\)

樣例輸入1

1
1010

樣例輸出1

6

樣例輸入2

2
01010

樣例輸出2

4

解題思路

我們考慮使用雙指針算法

• \(k=0\)：那麼我們只能取全為 \(0\) 的子串，比如我們有 \(00000\)，那麼子串的個數應該是 \(\frac{n*(n+1)}{2}\)，簡單推導一下就可以了
• \(k\ !=0\)：那麼我們考慮一個子串，如果其含有 \(k\) 個 \(1\)，那麼如果其兩頭有若干個 \(0\)，加上這些 \(0\)，仍然是符合要求的子串，從第一個 \(1\) 往前，也就是前導 \(0\) 的個數和最後一個 \(1\) 往後，後置 \(0\) 的個數的乘積就是符合要求的子串數，把所有的加起來就是答案

C++代碼

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

int k;
string s;

int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
    cout.tie(nullptr);
    cin >> k;
    cin >> s;
    int len = s.size();
    int cnt = 0;
    LL res  = 0;
    if(k == 0)
    {
        for(int i = 0; i < len; i ++)
        {
            if(s[i] - '0') continue;
            int j = i;
            while(s[j] - '0' == 0 && j < len)
            {
                j ++;
            }
            // cout << i << ' ' << j << endl;
            res += ((LL)(j - i + 1) * (LL)(j - i) / 2);
            i = j;
        }
        cout << res << endl;
        return 0;
    }
    for(int i = 0, j = 0; i < len; i ++)
    {
        while(j < len)
        {
            if(s[j] == '1')
                cnt ++;
            if(cnt == k)
                break;
            j ++;
        }
        if(cnt == k)
        {
            int ed = j + 1;
            while(ed < len && s[ed] != '1')
                ed ++;
            int c = ed - j; // 後置0
            while(i < len && s[i] != '1')
            {
                i ++;
                res += c;
            }
            res += c;
            j ++;
            cnt --;
        }
    }
    cout << res << endl;
    return 0;
}