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”.
Dữ liệu vào: Từ tệp văn bản SUBSTR.INP có cấu trúc:
Dòng 1 chứa một số nguyên K (0 ≤ K ≤ 106);
Dòng 2 chứa một xâu nhị phân có độ dài không quá 106.
Kết quả : Ghi ra tệp văn bản SUBSTR.OUT gồm một số nguyên duy nhất là kết quả tìm được.

Question

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”.
Dữ liệu vào: Từ tệp văn bản SUBSTR.INP có cấu trúc:
	Dòng 1 chứa một số nguyên K (0 ≤  K ≤  106);
	Dòng 2 chứa một xâu nhị phân có độ dài không quá 106.
Kết quả :  Ghi ra tệp văn bản SUBSTR.OUT gồm một số nguyên duy nhất là kết quả tìm được.

halilao · Accepted Answer

ĐỢi chút

Timi · Answer

Để giải bài toán này, ta có thể sử dụng thuật toán quét xâu. Ta duyệt qua từng ký tự trong xâu và đếm số lượng ký tự "1" liên tiếp. Nếu số lượng ký tự "1" liên tiếp bằng K thì tăng biến đếm lên 1. Cuối cùng, ghi biến đếm ra file SUBSTR.OUT.

Dưới đây là mã giả của thuật toán:

1. Đọc dữ liệu từ file SUBSTR.INP
2. Gán biến K bằng giá trị đọc được từ dòng 1
3. Gán biến xâu nhị phân bằng giá trị đọc được từ dòng 2
4. Khởi tạo biến đếm là 0
5. Khởi tạo biến count là 0 (đếm số lượng ký tự "1" liên tiếp)
6. Duyệt qua từng ký tự trong xâu:
   - Nếu ký tự là "1", tăng biến count lên 1
   - Nếu ký tự là "0", kiểm tra nếu count bằng K, tăng biến đếm lên 1 và đặt count về 0
7. Ghi biến đếm ra file SUBSTR.OUT

Sau khi thực hiện thuật toán, ta sẽ có kết quả tìm được là số lượng xâu con chứa đúng K ký tự "1".

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...