Xâu Con (HSG12'18-19)

Nguồn: HSG 12 năm 2018–2019 (LQDOJ) Độ khó: Trung bình Xâu ký tự Đếm – tổ hợp

Đề bài

Một xâu gọi là xâu nhị phân nếu chỉ chứa hai ký tự $0$ hoặc $1$.

Xâu $v$ gọi là xâu con của $w$ nếu xâu $v$ có độ dài khác 0 và gồm các ký tự liên tiếp trong xâu $w$.

Ví dụ: xâu 010 có các xâu con là: 0, 1, 0, 01, 10, 010.

Yêu cầu: Cho trước một giá trị $k$, hãy đếm xem có bao nhiêu xâu con chứa đúng $k$ ký tự $1$.

Input:

• Dòng 1: chứa một số nguyên $k$ $(0 \le k \le 10^6)$.
• Dòng 2: chứa một xâu nhị phân có độ dài $\le 10^6$.

Output:

• Ghi ra một số nguyên duy nhất là kết quả tìm được.

Scoring: $len(s)$ là độ dài xâu nhị phân.

• Subtask 1 (40% số điểm): $1 \le k \le len(s) \le 500$.
• Subtask 2 (30% số điểm): $1000 \le k \le len(s) \le 10000$.
• Subtask 3 (30% số điểm): $10^5 \le k \le len(s) \le 10^6$.

Ví dụ – input

2
01010

Ví dụ – output

4

Giải thích: có 4 xâu con chứa 2 ký tự 1 là: 101, 0101, 1010, 01010.

Lời mở đầu

Bài này mình được một em học viên hỏi và mình đã hướng dẫn chi tiết cách thức giải quyết cho em ấy. Tin rằng sẽ có giá trị với nhiều bạn nên mình chia sẻ đề bài để các bạn thử sức, kèm theo đó là nội dung mình đã hướng dẫn em ấy để bạn nào không giải quyết được thì có thể tham khảo nhen. Bài này bạn có thể nộp tại đây nha:

Link nộp bài

Bấm vào nút bên dưới để nộp bài và được hệ thống CLUE OJ chấm tự động.

Nộp bài trên CLUE OJ

Lộ trình lời giải, bấm vào từng phần để nhảy tới:

Cách 1Vét cạn O(N²)Ý tưởngVị trí số 1Minh hoạTừng nhómCách 2O(N)

Cách 1Vét cạn mọi xâu con – O(N²)

Ok anh sẽ cho em 1 gợi ý nhìn ra hướng xử lý của nó nha, hãy nhìn test này:

Ví dụ – input

2
010011001001

Ví dụ – output

17

Bài này nếu làm theo cách brute force (vét cạn) thì quá đơn giản: tại mỗi vị trí index $i$, xét tất cả các index $j \ge i$, đoạn con từ $i$ đến $j$ nào có đúng $k$ ký tự 1 thì tính. Ví dụ ta có chuỗi abcd thì sẽ có các xâu con:

aababcabcdbbcbcdccdd

Chuỗi dài $N$ có $\frac{N(N+1)}{2}$ xâu con – với $N = 4$ là 10 xâu con.

Mẹo nhỏ: khi cố định $i$ và cho $j$ chạy sang phải, ta đếm dồn số ký tự 1 trong biến cnt; một khi cnt > k thì kéo dài thêm cũng chỉ tăng chứ không giảm, nên break luôn. Code vét cạn mình viết thêm để các bạn tham khảo (và dùng để kiểm tra code tối ưu):

Code vét cạn O(N²) – chỉ qua Subtask 1

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

int main(){
    int k;
    string s;
    cin >> k >> s;
    int n = s.length();
    long long res = 0;
    for(int i = 0; i < n; ++i){
        int cnt = 0;
        for(int j = i; j < n; ++j){
            if(s[j] == '1') cnt++;
            if(cnt > k) break;
            if(cnt == k) res++;
        }
    }
    cout << res;
    return 0;
}

k = int(input())
s = input().strip()
n = len(s)
res = 0
for i in range(n):
    cnt = 0
    for j in range(i, n):
        if s[j] == '1':
            cnt += 1
        if cnt > k:
            break
        if cnt == k:
            res += 1
print(res)

C++▶ Chạy tay từng dòng codeCách 1: vét cạn mọi xâu con s[i..j], đếm dồn số ký tự 1, O(N²).

Dữ liệu vào (stdin) – sửa thoải mái2 01010

Dữ liệu mẫu:

1#include <bits/stdc++.h>

2using namespace std;

3

4int main(){

5 int k;

6 string s;

7 cin >> k >> s;

8 int n = s.length();

9 long long res = 0;

10 for(int i = 0; i < n; ++i){

11 int cnt = 0;

12 for(int j = i; j < n; ++j){

13 if(s[j] == '1') cnt++;

14 if(cnt > k) break;

15 if(cnt == k) res++;

16 }

17 }

18 cout << res;

19 return 0;

20}

ChậmVừaNhanhRất nhanh

Không gian$O(N)$ (lưu xâu)

Thời gian$O(N^2)$ – chỉ qua Subtask 1

Nhưng nếu làm vậy trước mắt là thấy độ phức tạp sẽ là $O(N^2)$ với $N$ là độ dài chuỗi, mà đề cho chuỗi độ dài tối đa $10^6$, thì $(10^6)^2 = 10^{12}$, đã vượt quá $10^8$ phép tính trong giới hạn 1 giây rồi nên sẽ bị TLE. Cách này chỉ qua được Subtask 1 (và may mắn thì Subtask 2), vì thế phải tìm ra một cách tốt hơn.

Ý tưởngNhìn vào vị trí các ký tự 1

Bài này có thể giải quyết trong $O(N)$ là cách tối ưu nhất nhé, sẽ làm được nếu em nhìn ra quy luật sau. Hãy nhìn lại test $k = 2$, $s$ = 010011001001: nghĩa là cần đếm xem có bao nhiêu xâu con liên tiếp có đúng 2 ký tự 1.

Đầu tiên ta hãy thử liệt kê ra tất cả các vị trí index (tính từ 0) của các ký tự 1 trong chuỗi, ta sẽ có mảng $a = [1, 4, 5, 8, 11]$. Bây giờ với $k = 2$ thì ta cứ xét từng cặp $k$ vị trí liên tiếp trong mảng này: start là số 1 đầu tiên, finish là số 1 cuối cùng của nhóm.

s = 010011001001 (số nhỏ phía trên là index)

00112030415160708190100111

Mảng vị trí các số 1: a = [1, 4, 5, 8, 11] · các cặp (k = 2): (1, 4), (4, 5), (5, 8), (8, 11)

Cặp 1: start = 1, finish = 4

2 phần tử đầu mảng $a$ là $1, 4$, nghĩa là từ index 1 đến index 4 trong chuỗi ban đầu chứa đúng 2 ký tự 1, em coi đúng không?

• Bên trái: trước start không có số 1 nào (đây là cặp đầu tiên), nên điểm bắt đầu của xâu con có thể chọn từ index 0 đến index start = 1 → có 2 cách.
• Bên phải: số 1 tiếp theo sau finish = 4 ở index 5, nên điểm kết thúc tối đa chỉ đến 5 − 1 = 4 chứ không đến 5 được, vì nếu không sẽ thành xâu con có 3 ký tự 1 → từ 4 đến 4 có 1 cách.

Tổng cộng ta có $2 \cdot 1 = 2$ xâu con: 01001 và 1001.

Cặp 2: start = 4, finish = 5

• Trước start, số 1 gần nhất ở index 1, nên điểm bắt đầu lấy từ sau vị trí đó đến start: từ index 2 đến 4 → 3 cách.
• Sau finish, số 1 tiếp theo ở index 8, nên điểm kết thúc từ 5 đến 7 → 3 cách.

Tổng cộng $3 \cdot 3 = 9$ xâu con: $2 \to 5$, $2 \to 6$, $2 \to 7$, $3 \to 5$, $3 \to 6$, $3 \to 7$, $4 \to 5$, $4 \to 6$, $4 \to 7$.

Cặp 2: điểm đầu chọn trong vùng xanh dương (3 cách), điểm cuối trong vùng xanh lá (3 cách)

00112030415160708190100111

3 × 3 = 9 xâu con

Cặp 3: start = 5, finish = 8

• Số 1 trước start ở index 4 → điểm bắt đầu từ 5 đến 5 → 1 cách.
• Số 1 sau finish ở index 11 → điểm kết thúc từ 8 đến 10 → 3 cách.

Tổng cộng $1 \cdot 3 = 3$ xâu con: $5 \to 8$, $5 \to 9$, $5 \to 10$.

Cặp 4: start = 8, finish = 11

• Số 1 trước start ở index 5 → điểm bắt đầu từ 6 đến 8 → 3 cách.
• Sau finish = 11 không còn số 1 nào nữa vì đây là số 1 cuối cùng, nên điểm kết thúc tối đa là index cuối của chuỗi. Chuỗi dài 12 nên index cuối là 11 → từ 11 đến 11 có 1 cách.

Tổng cộng $3 \cdot 1 = 3$ xâu con: $6 \to 11$, $7 \to 11$, $8 \to 11$.

Vậy tổng kết lại, số xâu con liên tiếp có đúng $k = 2$ ký tự 1 là $2 + 9 + 3 + 3 = \boxed{17}$. Đó là cách để chỉ cần 1 lần duyệt O(N) qua chuỗi là xử lý được nha em 😃

Công thức gọn

Với nhóm $k$ số 1 liên tiếp từ $a[start]$ đến $a[finish]$ (với $finish = start + k - 1$), đặt $x$ = vị trí số 1 ngay trước ($x = -1$ nếu không có) và $y$ = vị trí số 1 ngay sau ($y = len(s)$ nếu không có). Số xâu con nhận đúng nhóm này là $(a[start] - x) \cdot (y - a[finish])$. Cộng lại cho mọi nhóm là xong.

Trường hợp đặc biệt k = 0

Tất nhiên còn 1 số trường hợp đặc biệt, ví dụ khi $k = 0$ phải xét riêng ^^. Lúc này xâu con hợp lệ là xâu con chỉ gồm toàn ký tự 0. Các số 1 cắt chuỗi thành từng đoạn 0 liên tiếp; một đoạn gồm $cnt$ số 0 có $\frac{cnt \cdot (cnt + 1)}{2}$ xâu con (chọn 2 đầu mút trong đoạn). Cộng lại tất cả các đoạn (kể cả đoạn trước số 1 đầu tiên và đoạn sau số 1 cuối cùng). Nếu chuỗi không có số 1 nào thì cả chuỗi là 1 đoạn, đáp án là $\frac{len \cdot (len + 1)}{2}$. Ngoài ra nếu $k$ lớn hơn số lượng ký tự 1 thì đáp án là 0.

Minh hoạĐếm theo từng nhóm k số 1

Em nhập $k$ và xâu $s$ (tối đa 30 ký tự) rồi bấm Tiếp để xem từng nhóm: vùng chọn điểm đầu (xanh dương), nhóm $k$ số 1 (vàng), vùng chọn điểm cuối (xanh lá):

k = s =

Ví dụ nhanh:

Cách 2Code O(N) theo vị trí các số 1

Source code giải quyết theo tư tưởng anh đã trình bày ở trên và cũng đã nộp thành công trên web, em xem để được hiểu rõ hơn. Anh nói trước là code này anh code vội ra theo đúng tư tưởng đã chia sẻ đó với em chứ chưa có clean đâu nha, anh sợ clean lại mất công em đọc không hiểu. Em xem hiểu rồi clean lại sau nhé:

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

long long solve(const string &s, int k){
    vector<int> a;
    for(int i = 0; i < s.length(); ++i){
        if(s[i] == '1'){
            a.push_back(i);
        }
    }
    if(k > a.size()){
        return 0;
    }
    if(k == 0){
        if(a.size() == 0){
            long long l = s.length();
            return (l * (l + 1)) / 2;
        }
        else{
            long long res = 0, cnt = 0;
            int start = 0;
            for(int i = 0; i < a.size(); ++i){
                if(start <= a[i] - 1){
                    cnt = a[i] - start;
                    res += (cnt * (cnt + 1)) / 2;
                }
                start = a[i] + 1;
            }
            if(s.back() != '1'){
                cnt = s.length() - (a.back() + 1);
                res += (cnt * (cnt + 1)) / 2;
            }
            return res;
        }
    }
    long long res = 0;
    int start = 0, finish = k - 1;
    while(finish < a.size()){
        int x, y;
        if(start == 0){
            x = -1;
        }
        else{
            x = a[start - 1];
        }
        if(finish == a.size() - 1){
            y = s.length();
        }
        else{
            y = a[finish + 1];
        }
        long long s1 = a[start] - x;
        long long s2 = y - a[finish];
        res += s1 * s2;
        start++;
        finish++;
    }
    return res;
}

int main(){
    ios::sync_with_stdio(0);
    cin.tie(0);
    int k;
    string s;
    cin >> k >> s;
    cout << solve(s, k);
    return 0;
}

def solve(s: str, k: int) -> int:
    a = [i for i, ch in enumerate(s) if ch == '1']
    if k > len(a):
        return 0
    if k == 0:
        if len(a) == 0:
            l = len(s)
            return (l * (l + 1)) // 2
        else:
            res = 0
            start = 0
            for idx in a:
                if start <= idx - 1:
                    cnt = idx - start
                    res += (cnt * (cnt + 1)) // 2
                start = idx + 1
            if s[-1] != '1':
                cnt = len(s) - (a[-1] + 1)
                res += (cnt * (cnt + 1)) // 2
            return res
    res = 0
    start = 0
    finish = k - 1
    while finish < len(a):
        if start == 0:
            x = -1
        else:
            x = a[start - 1]
        if finish == len(a) - 1:
            y = len(s)
        else:
            y = a[finish + 1]
        s1 = a[start] - x
        s2 = y - a[finish]
        res += s1 * s2
        start += 1
        finish += 1
    return res

k = int(input())
s = input()
print(solve(s, k))

C++▶ Chạy tay từng dòng codeCách 2: gom vị trí các số 1 vào a, mỗi nhóm k số 1 liên tiếp đóng góp s1 × s2 xâu con, O(N).

Dữ liệu vào (stdin) – sửa thoải mái2 010011001001

Dữ liệu mẫu:

1#include <bits/stdc++.h>

2using namespace std;

3

4long long solve(const string &s, int k){

5 vector<int> a;

6 for(int i = 0; i < s.length(); ++i){

7 if(s[i] == '1'){

8 a.push_back(i);

9 }

10 }

11 if(k > a.size()){

12 return 0;

13 }

14 if(k == 0){

15 if(a.size() == 0){

16 long long l = s.length();

17 return (l * (l + 1)) / 2;

18 }

19 else{

20 long long res = 0, cnt = 0;

21 int start = 0;

22 for(int i = 0; i < a.size(); ++i){

23 if(start <= a[i] - 1){

24 cnt = a[i] - start;

25 res += (cnt * (cnt + 1)) / 2;

26 }

27 start = a[i] + 1;

28 }

29 if(s.back() != '1'){

30 cnt = s.length() - (a.back() + 1);

31 res += (cnt * (cnt + 1)) / 2;

32 }

33 return res;

34 }

35 }

36 long long res = 0;

37 int start = 0, finish = k - 1;

38 while(finish < a.size()){

39 int x, y;

40 if(start == 0){

41 x = -1;

42 }

43 else{

44 x = a[start - 1];

45 }

46 if(finish == a.size() - 1){

47 y = s.length();

48 }

49 else{

50 y = a[finish + 1];

51 }

52 long long s1 = a[start] - x;

53 long long s2 = y - a[finish];

54 res += s1 * s2;

55 start++;

56 finish++;

57 }

58 return res;

59}

60

61int main(){

62 ios::sync_with_stdio(0);

63 cin.tie(0);

64 int k;

65 string s;

66 cin >> k >> s;

67 cout << solve(s, k);

68 return 0;

69}

ChậmVừaNhanhRất nhanh

Đánh giá độ phức tạp của cách làm này:

Không gian$O(N)$ cho xâu và mảng vị trí $a$

Thời gian$O(N)$: 1 lần duyệt lấy vị trí số 1 + 1 lần duyệt các nhóm

Lưu ý kết quả có thể rất lớn: chuỗi $10^6$ ký tự 0 với $k = 0$ cho đáp án $500\,000\,500\,000$, vượt kiểu int, nên res, s1, s2 phải là long long.

Ghi chú của mình: code C++ và Python của Cách 2 là của anh, code vét cạn Cách 1 mình viết thêm. Tất cả đã được kiểm tra với 250 bộ test ngẫu nhiên (xâu dài đến 25 ký tự, có cả $k = 0$, $k$ lớn hơn số ký tự 1, xâu toàn 0 hoặc toàn 1), so với cách đếm trực tiếp mọi xâu con – khớp hết. Với xâu dài $10^6$, bản C++ của Cách 2 chạy khoảng 0.03 giây, bản Python khoảng 0.3 giây; còn vét cạn chạy hơn 10 giây.

Rất vui khi anh em nào đã đọc đến những dòng cuối cùng này. Anh em đọc chắc cũng mỏi mắt luôn chứ 😅 vậy anh em nghĩ người viết ra hết đống ở trên còn thế nào nữa 🤪. Vậy nên đừng tiếc gì cho mình một lời bình luận hoặc chia sẻ bài viết để động viên mình nè. Chúc anh em học tốt và gặt hái nhiều thành công 😇