Hai con trỏ và cửa sổ trượt

Mức độ: Cơ bản

Đề cho dãy 10⁵ số đã sắp xếp tăng dần, hỏi có hai số nào cộng lại bằng S không. Thử mọi cặp thì có khoảng 5 × 10⁹ cặp, quá chậm. Hai con trỏ đặt một “ngón tay” ở đầu dãy, một “ngón tay” ở cuối dãy, rồi mỗi bước dịch một ngón tay vào trong. Sau không quá n bước là có câu trả lời.

Ý tưởng chung của mọi bài trong trang này: hai vị trí trên dãy chỉ đi một chiều, không bao giờ lùi lại. Mỗi vị trí đi tối đa n bước, nên cả chương trình chỉ khoảng 2n bước.

Hai con trỏ đi ngược chiều: cặp có tổng bằng S

Dãy tăng dần a₁ ≤ a₂ ≤ … ≤ a_n. Đặt trai ở đầu dãy, phai ở cuối dãy, rồi xét tổng a_trai + a_phai:

• Tổng bằng S: tìm được cặp.
• Tổng nhỏ hơn S: tăng trai lên 1.
• Tổng lớn hơn S: giảm phai đi 1.

Vì sao được bỏ a_trai khi tổng nhỏ hơn S? Mọi số còn lại để ghép với a_trai đều nằm từ trai + 1 đến phai, nên đều không lớn hơn a_phai. Cộng a_trai với số lớn nhất trong đó còn chưa tới S, cộng với số nhỏ hơn thì càng không tới. Vậy a_trai không thuộc cặp nào cả, bỏ đi được. Trường hợp tổng lớn hơn S thì lý luận giống hệt: a_phai cộng với số nhỏ nhất còn lại đã vượt S, nên bỏ a_phai.

Chạy tay với dãy 1 3 4 6 8 11, S = 10:

Bước	trai	phai	atrai + aphai	So với 10	Việc làm
1	1	6	1 + 11 = 12	lớn hơn	giảm phai
2	1	5	1 + 8 = 9	nhỏ hơn	tăng trai
3	2	5	3 + 8 = 11	lớn hơn	giảm phai
4	2	4	3 + 6 = 9	nhỏ hơn	tăng trai
5	3	4	4 + 6 = 10	bằng	tìm được: 4 + 6

Mỗi bước, khoảng cách giữa trai và phai giảm đi 1. Hai con trỏ gặp nhau sau không quá n - 1 bước, nên cả bài chỉ khoảng n bước thay vì n × (n - 1) / 2 cặp.

Python

n, s = map(int, input().split())
a = list(map(int, input().split()))   # đã sắp xếp tăng dần
trai, phai = 0, n - 1
tim_duoc = False
while trai < phai:
    tong = a[trai] + a[phai]
    if tong == s:
        tim_duoc = True
        break
    if tong < s:
        trai += 1
    else:
        phai -= 1
print("YES" if tim_duoc else "NO")

C++

#include <iostream>
#include <vector>
using namespace std;

int main() {
    int n;
    long long s;
    cin >> n >> s;
    vector<long long> a(n);   // đã sắp xếp tăng dần
    for (auto &x : a) cin >> x;
    int trai = 0, phai = n - 1;
    bool timDuoc = false;
    while (trai < phai) {
        long long tong = a[trai] + a[phai];
        if (tong == s) {
            timDuoc = true;
            break;
        }
        if (tong < s) trai++;
        else phai--;
    }
    cout << (timDuoc ? "YES" : "NO") << "\n";
    return 0;
}

Lưu ý: cách này chỉ đúng khi dãy đã sắp xếp, vì lý luận “mọi số còn lại đều không lớn hơn a_phai” cần dãy tăng dần. Dãy chưa sắp xếp thì sắp xếp trước, mất khoảng n × log₂n bước, vẫn nhanh hơn rất nhiều so với thử mọi cặp.

Hai con trỏ đi cùng chiều: gộp hai dãy đã sắp xếp

Có hai dãy tăng dần A (n số) và B (m số), cần gộp thành một dãy tăng dần. Đặt i ở đầu A, j ở đầu B. Mỗi bước so a_i với b_j, lấy số nhỏ hơn đưa vào kết quả rồi tiến con trỏ của dãy đó lên 1.

Số nhỏ hơn trong hai số đang xét là số nhỏ nhất chưa được lấy: các số phía sau trong A đều không nhỏ hơn a_i, các số phía sau trong B đều không nhỏ hơn b_j. Vì vậy lấy nó ra trước là đúng thứ tự.

A	B	Lấy ra	Kết quả
1 4 7	2 3 9	1 (từ A)	1
4 7	2 3 9	2 (từ B)	1 2
4 7	3 9	3 (từ B)	1 2 3
4 7	9	4 (từ A)	1 2 3 4
7	9	7 (từ A)	1 2 3 4 7
(hết)	9	9 (từ B)	1 2 3 4 7 9

Mỗi bước lấy ra đúng một số, nên tổng cộng n + m bước.

Python

n, m = map(int, input().split())
a = list(map(int, input().split()))
b = list(map(int, input().split()))
i = j = 0
ket_qua = []
while i < n and j < m:
    if a[i] <= b[j]:
        ket_qua.append(a[i])
        i += 1
    else:
        ket_qua.append(b[j])
        j += 1
ket_qua += a[i:] + b[j:]   # một trong hai dãy còn dư thì nối nốt
print(*ket_qua)

C++

#include <iostream>
#include <vector>
using namespace std;

int main() {
    int n, m;
    cin >> n >> m;
    vector<long long> a(n), b(m);
    for (auto &x : a) cin >> x;
    for (auto &x : b) cin >> x;
    vector<long long> ketQua;
    int i = 0, j = 0;
    while (i < n && j < m) {
        if (a[i] <= b[j]) ketQua.push_back(a[i++]);
        else ketQua.push_back(b[j++]);
    }
    while (i < n) ketQua.push_back(a[i++]);
    while (j < m) ketQua.push_back(b[j++]);
    for (int k = 0; k < (int)ketQua.size(); k++) cout << ketQua[k] << (k + 1 < (int)ketQua.size() ? ' ' : '\n');
    return 0;
}

Đây chính là bước “trộn” của sắp xếp trộn (merge sort).

Cửa sổ trượt độ dài cố định

Tính tổng của mọi đoạn gồm k số liên tiếp. Cộng lại từ đầu cho từng đoạn thì mất k bước mỗi đoạn. Nhưng hai đoạn kề nhau chỉ khác nhau hai số: đoạn mới thêm một số ở bên phải và bỏ một số ở bên trái.

Hình dung một khung cửa sổ rộng k ô trượt trên dãy. Mỗi lần trượt sang phải một ô:

• cộng thêm số vừa vào cửa sổ,
• trừ đi số vừa ra khỏi cửa sổ.

Dãy 2 5 1 3 6 4, k = 3:

Cửa sổ	Số vào	Số ra	Tổng
2 5 1 3 6 4			2 + 5 + 1 = 8
2 5 1 3 6 4	3	2	8 + 3 - 2 = 9
2 5 1 3 6 4	6	5	9 + 6 - 5 = 10
2 5 1 3 6 4	4	1	10 + 4 - 1 = 13

Mỗi đoạn chỉ tốn 2 phép tính, cả dãy khoảng 2n phép tính thay vì k × n.

Python

n, k = map(int, input().split())
a = list(map(int, input().split()))
tong = sum(a[:k])
tong_cac_doan = [tong]
for phai in range(k, n):
    tong += a[phai] - a[phai - k]   # số a[phai] vào, số a[phai - k] ra
    tong_cac_doan.append(tong)
print(*tong_cac_doan)

C++

#include <iostream>
#include <vector>
using namespace std;

int main() {
    int n, k;
    cin >> n >> k;
    vector<long long> a(n);
    for (auto &x : a) cin >> x;
    long long tong = 0;
    for (int i = 0; i < k; i++) tong += a[i];
    cout << tong;
    for (int phai = k; phai < n; phai++) {
        tong += a[phai] - a[phai - k];   // số a[phai] vào, số a[phai - k] ra
        cout << ' ' << tong;
    }
    cout << "\n";
    return 0;
}

Riêng với tổng, tổng tiền tố cũng làm được việc này. Cửa sổ trượt có lợi khi thứ cần theo dõi không tính được bằng phép trừ, ví dụ số giá trị khác nhau trong cửa sổ: số vào thì tăng số lần xuất hiện của nó, số ra thì giảm, số lần xuất hiện về 0 thì bớt đi một giá trị khác nhau.

Cửa sổ co giãn: đoạn dài nhất có tổng không quá S

Dãy gồm các số dương, tìm đoạn liên tiếp dài nhất có tổng không quá S. Lần này độ dài cửa sổ không cố định: phai đi dần từ đầu đến cuối, mỗi lần đưa a_phai vào cửa sổ. Nếu tổng vượt S thì tăng trai (bỏ số bên trái ra) cho đến khi tổng không quá S nữa. Lúc đó đoạn từ trai đến phai là đoạn dài nhất kết thúc tại phai.

Vì sao trai không bao giờ phải lùi lại? Khi đoạn từ trai đến phai đã có tổng vượt S, mọi đoạn bắt đầu trước trai và kết thúc tại phai hoặc xa hơn đều chứa đoạn đó, lại có thêm toàn số dương, nên tổng còn lớn hơn và cũng vượt S. Những đoạn đó không bao giờ cần xét nữa.

Dãy 3 1 2 1 4 2, S = 6:

phai	Số vào	Tổng sau khi vào	Bỏ ra bên trái	Cửa sổ	Độ dài
1	3	3		3	1
2	1	4		3 1	2
3	2	6		3 1 2	3
4	1	7	bỏ 3, tổng 4	1 2 1	3
5	4	8	bỏ 1, bỏ 2, tổng 5	1 4	2
6	2	7	bỏ 1, tổng 6	4 2	2

Đoạn dài nhất có độ dài 3. phai đi n bước, trai cũng chỉ đi tối đa n bước tổng cộng (không lùi), nên cả bài khoảng 2n bước.

Python

n, s = map(int, input().split())
a = list(map(int, input().split()))   # các số dương
trai = 0
tong = 0
dai_nhat = 0
for phai in range(n):
    tong += a[phai]
    while tong > s:
        tong -= a[trai]
        trai += 1
    dai_nhat = max(dai_nhat, phai - trai + 1)
print(dai_nhat)

C++

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

int main() {
    int n;
    long long s;
    cin >> n >> s;
    vector<long long> a(n);   // các số dương
    for (auto &x : a) cin >> x;
    int trai = 0, daiNhat = 0;
    long long tong = 0;
    for (int phai = 0; phai < n; phai++) {
        tong += a[phai];
        while (tong > s) {
            tong -= a[trai];
            trai++;
        }
        daiNhat = max(daiNhat, phai - trai + 1);
    }
    cout << daiNhat << "\n";
    return 0;
}

Khi một số đơn lẻ đã lớn hơn S, vòng while bỏ hết cửa sổ, trai vượt qua phai một ô và độ dài phai - trai + 1 bằng 0, đúng là không có đoạn nào kết thúc tại đó.

Đếm số đoạn có tổng không quá S cũng dùng đúng vòng lặp này: các đoạn kết thúc tại phai và thỏa mãn là các đoạn bắt đầu từ trai, trai + 1, …, phai, tức là có phai - trai + 1 đoạn. Cộng con số này qua mọi phai là được đáp số.

Khi nào dùng được cửa sổ co giãn?

Cửa sổ co giãn đúng khi bài có tính chất: đoạn thỏa mãn thì mọi đoạn con bên trong nó cũng thỏa mãn (hoặc ngược lại: đoạn không thỏa mãn thì mọi đoạn chứa nó cũng không thỏa mãn). Chính tính chất này cho phép trai chỉ đi tới. Một vài ví dụ:

Điều kiện của đoạn	Đoạn con có còn thỏa mãn?	Dùng được?
tổng không quá S (các số dương)	có, bỏ bớt số dương thì tổng giảm	được
không có giá trị nào lặp lại	có, bỏ bớt số thì không sinh thêm số lặp	được
có không quá k giá trị khác nhau	có	được
tổng không quá S (có số âm)	không, bỏ số âm đi thì tổng lại tăng	không

Ví dụ dãy 5 -4 3 với S = 4: cả đoạn có tổng 4, thỏa mãn, nhưng đoạn con 5 có tổng 5, không thỏa mãn. Gặp dãy có số âm thì phải dùng cách khác, ví dụ tổng tiền tố kết hợp với sắp xếp hoặc tìm kiếm nhị phân.

Luyện tập

Gồm 28 bài, chia thành 5 nhóm từ dễ đến khó. Mỗi bài có một dữ liệu kiểm tra: các bạn chạy chương trình của mình với dữ liệu đó rồi so với đáp số.

Nhóm 1. Hai con trỏ đi ngược chiều

Bài 1. Đếm cặp có tổng bằng S

Dòng đầu có n, S (2 ≤ n ≤ 10⁵, |S| ≤ 2 × 10⁹). Dòng thứ hai có n số nguyên tăng ngặt (|a_i| ≤ 10⁹). In ra số cặp chỉ số i, j với i đứng trước j và a_i + a_j = S.

Ví dụ:

Nhập	In ra
6 10 1 3 4 6 7 9	3

Kiểm tra: nhập

10 12
-5 -1 2 3 5 7 9 10 13 17

Xem đáp số

5

Hướng dẫn giải chi tiết: liên hệ tác giả.

Bài 2. Đếm cặp có tổng không quá S

Dòng đầu có n, S (2 ≤ n ≤ 10⁵, |S| ≤ 2 × 10⁹). Dòng thứ hai có n số nguyên (|a_i| ≤ 10⁹), chưa sắp xếp, có thể trùng nhau. In ra số cặp chỉ số i, j với i đứng trước j và a_i + a_j ≤ S.

Ví dụ:

Nhập	In ra
5 7 5 1 4 2 3	8

Kiểm tra: nhập

10 6
3 8 -2 5 1 7 4 0 6 2

Xem đáp số

21

Hướng dẫn giải chi tiết: liên hệ tác giả.

Bài 3. Tổng gần S nhất

Dòng đầu có n, S (2 ≤ n ≤ 10⁵, |S| ≤ 2 × 10⁹). Dòng thứ hai có n số nguyên (|a_i| ≤ 10⁹), chưa sắp xếp. Chọn hai số ở hai vị trí khác nhau sao cho tổng của chúng gần S nhất. In ra khoảng cách nhỏ nhất giữa tổng đó và S.

Ví dụ:

Nhập	In ra
5 20 4 15 9 2 12	1

Kiểm tra: nhập

8 -3
7 -10 4 -6 11 3 -1 8

Xem đáp số

0

Hướng dẫn giải chi tiết: liên hệ tác giả.

Bài 4. Câu đối xứng

Nhập một dòng gồm chữ cái tiếng Anh và dấu cách (dài không quá 10⁵ ký tự, có ít nhất một chữ cái). Bỏ qua dấu cách và không phân biệt chữ hoa, chữ thường, in ra YES nếu dòng đó đọc xuôi và đọc ngược như nhau, ngược lại in ra NO.

Ví dụ: nhập Never odd or even thì in ra YES.

Kiểm tra: nhập Was it a car or a cat I sat.

Xem đáp số

NO

Hướng dẫn giải chi tiết: liên hệ tác giả.

Bài 5. Xóa một ký tự để đối xứng

Nhập một xâu s gồm chữ cái thường (1 ≤ độ dài ≤ 10⁵). In ra YES nếu xóa nhiều nhất một ký tự thì s trở thành xâu đối xứng, ngược lại in ra NO.

Ví dụ: nhập abca thì in ra YES.

Kiểm tra: nhập abcdecbxa.

Xem đáp số

NO

Hướng dẫn giải chi tiết: liên hệ tác giả.

Bài 6. Bộ ba có tổng bằng 0

Dòng đầu có n (3 ≤ n ≤ 3000). Dòng thứ hai có n số nguyên đôi một khác nhau (|a_i| ≤ 10⁹), chưa sắp xếp. In ra số bộ ba vị trí khác nhau (không kể thứ tự) có tổng ba số bằng 0.

Ví dụ:

Nhập	In ra
6 -1 0 1 2 -2 3	3

Kiểm tra: nhập

12
5 -7 2 -3 8 0 -5 1 -1 4 -4 3

Xem đáp số

14

Hướng dẫn giải chi tiết: liên hệ tác giả.

Bài 7. Thuyền cứu hộ

Có n người, người thứ i nặng w_i kg. Mỗi thuyền chở nhiều nhất hai người với tổng cân nặng không quá W kg. Dòng đầu có n, W (1 ≤ n ≤ 10⁵, 1 ≤ w_i ≤ W ≤ 10⁹), dòng thứ hai có n số w_i. In ra số thuyền ít nhất để chở hết mọi người.

Ví dụ:

Nhập	In ra
4 100 70 50 80 50	3

Kiểm tra: nhập

10 120
60 40 100 75 30 80 55 45 90 20

Xem đáp số

5

Hướng dẫn giải chi tiết: liên hệ tác giả.

Nhóm 2. Hai con trỏ đi cùng chiều

Bài 8. Gộp hai dãy tăng

Dòng đầu có n, m (1 ≤ n, m ≤ 10⁵). Dòng thứ hai có n số nguyên tăng dần (không giảm), dòng thứ ba có m số nguyên tăng dần (không giảm), mọi số có giá trị tuyệt đối không quá 10⁹. In ra n + m số của hai dãy theo thứ tự tăng dần trên một dòng.

Ví dụ:

Nhập	In ra
3 4 1 4 7 2 3 4 9	1 2 3 4 4 7 9

Kiểm tra: nhập

6 5
-8 -3 0 0 6 12
-5 0 2 7 20

Xem đáp số

-8 -5 -3 0 0 0 2 6 7 12 20

Hướng dẫn giải chi tiết: liên hệ tác giả.

Bài 9. Số chung của hai dãy

Dòng đầu có n, m (1 ≤ n, m ≤ 10⁵). Dòng thứ hai có n số nguyên tăng ngặt, dòng thứ ba có m số nguyên tăng ngặt (giá trị tuyệt đối không quá 10⁹). In ra số giá trị có mặt ở cả hai dãy.

Ví dụ:

Nhập	In ra
5 4 1 3 5 7 9 2 3 7 10	2

Kiểm tra: nhập

8 7
-6 -2 0 4 5 9 13 20
-6 -1 0 5 8 13 21

Xem đáp số

4

Hướng dẫn giải chi tiết: liên hệ tác giả.

Bài 10. Dãy con của xâu

Nhập hai xâu s và t trên hai dòng, gồm chữ cái thường, mỗi xâu dài từ 1 đến 10⁵. In ra YES nếu có thể xóa một số ký tự của t (giữ nguyên thứ tự các ký tự còn lại) để được s, ngược lại in ra NO.

Ví dụ:

Nhập	In ra
ace abcde	YES

Kiểm tra: nhập

bumbii
bambooibiiu

Xem đáp số

NO

Hướng dẫn giải chi tiết: liên hệ tác giả.

Bài 11. Cặp có hiệu không quá D

Dòng đầu có n, D (2 ≤ n ≤ 10⁵, 0 ≤ D ≤ 10⁹). Dòng thứ hai có n số nguyên không giảm (0 ≤ a_i ≤ 10⁹). In ra số cặp chỉ số i, j với i đứng trước j và a_j - a_i ≤ D.

Ví dụ:

Nhập	In ra
5 3 1 2 4 6 9	5

Kiểm tra: nhập

10 5
0 1 1 4 6 7 10 12 12 20

Xem đáp số

18

Hướng dẫn giải chi tiết: liên hệ tác giả.

Bài 12. Đội nào cao hơn

Đội A có n bạn, đội B có m bạn, chiều cao (cm) mỗi đội được cho theo thứ tự không giảm. Dòng đầu có n, m (1 ≤ n, m ≤ 10⁵), dòng thứ hai có n số của đội A, dòng thứ ba có m số của đội B (mỗi số từ 1 đến 10⁹). In ra số cặp (một bạn đội A, một bạn đội B) mà bạn đội A thấp hơn bạn đội B.

Ví dụ:

Nhập	In ra
3 3 150 160 170 155 160 175	5

Kiểm tra: nhập

6 5
140 150 150 162 170 181
145 150 165 170 190

Xem đáp số

16

Hướng dẫn giải chi tiết: liên hệ tác giả.

Nhóm 3. Cửa sổ độ dài cố định

Bài 13. Tuần nắng nóng

Nhiệt độ n ngày liên tiếp là a₁, …, a_n. Dòng đầu có n, k, T (1 ≤ k ≤ n ≤ 10⁵, |T| ≤ 10¹⁴), dòng thứ hai có n số nguyên (|a_i| ≤ 10⁹). In ra số đoạn gồm đúng k ngày liên tiếp có tổng nhiệt độ ít nhất T.

Ví dụ:

Nhập	In ra
7 3 90 28 31 33 30 27 35 29	5

Kiểm tra: nhập

12 4 120
30 29 31 33 28 27 32 35 34 26 30 31

Xem đáp số

8

Hướng dẫn giải chi tiết: liên hệ tác giả.

Bài 14. Bật đèn

Một dãy n bóng đèn được cho bằng xâu gồm 0 (tắt) và 1 (bật). Dòng đầu có n, k (1 ≤ k ≤ n ≤ 10⁵), dòng thứ hai là xâu độ dài n. Cần chọn k bóng liên tiếp và bật hết các bóng đang tắt trong đó. In ra số bóng ít nhất phải bật thêm.

Ví dụ:

Nhập	In ra
8 3 10010110	1

Kiểm tra: nhập

15 5
001011000111010

Xem đáp số

1

Hướng dẫn giải chi tiết: liên hệ tác giả.

Bài 15. Số loại hàng trong mỗi khung

Băng chuyền có n món hàng, món thứ i có mã a_i. Dòng đầu có n, k (1 ≤ k ≤ n ≤ 10⁵), dòng thứ hai có n số a_i (1 ≤ a_i ≤ 10⁶). Với mỗi đoạn k món liên tiếp (từ trái sang phải), in ra số mã khác nhau trong đoạn đó, các số cách nhau một dấu cách.

Ví dụ:

Nhập	In ra
7 3 1 2 1 3 4 2 3	2 3 3 3 3

Kiểm tra: nhập

12 3
5 5 2 7 5 2 2 9 7 7 1 5

Xem đáp số

2 3 3 3 2 2 3 2 2 3

Hướng dẫn giải chi tiết: liên hệ tác giả.

Bài 16. Đoạn không lặp độ dài k

Dòng đầu có n, k (1 ≤ k ≤ n ≤ 10⁵), dòng thứ hai có n số nguyên (1 ≤ a_i ≤ 10⁶). In ra số đoạn gồm đúng k số liên tiếp mà các số trong đoạn đôi một khác nhau.

Ví dụ:

Nhập	In ra
6 3 1 2 3 1 2 2	3

Kiểm tra: nhập

12 4
3 1 4 1 5 9 2 6 5 3 5 8

Xem đáp số

5

Hướng dẫn giải chi tiết: liên hệ tác giả.

Bài 17. Tìm từ đảo chữ

Nhập xâu t trên dòng đầu và xâu p trên dòng thứ hai, cả hai gồm chữ cái thường, 1 ≤ |p| ≤ |t| ≤ 10⁵. In ra số vị trí trong t mà đoạn |p| ký tự liên tiếp bắt đầu từ đó là một cách đảo chữ của p (gồm đúng các chữ cái của p, mỗi chữ đúng số lần, thứ tự tùy ý).

Ví dụ:

Nhập	In ra
cbaebabacd abc	2

Kiểm tra: nhập

thetrathatheatherat
tea

Xem đáp số

1

Hướng dẫn giải chi tiết: liên hệ tác giả.

Nhóm 4. Cửa sổ co giãn

Bài 18. Đọc sách liền mạch

Trên giá có n cuốn sách xếp thành hàng, đọc cuốn thứ i mất a_i phút. Bạn Minh có S phút, chọn một cuốn để bắt đầu rồi đọc lần lượt các cuốn kế tiếp bên phải, không bỏ cuốn nào, và chỉ tính các cuốn đọc xong. Dòng đầu có n, S (1 ≤ n ≤ 10⁵, 1 ≤ S ≤ 10¹⁴), dòng thứ hai có n số a_i (1 ≤ a_i ≤ 10⁹). In ra số cuốn nhiều nhất Minh đọc xong.

Ví dụ:

Nhập	In ra
6 10 3 1 2 1 4 6	4

Kiểm tra: nhập

12 25
7 3 8 2 4 1 9 5 6 2 3 10

Xem đáp số

6

Hướng dẫn giải chi tiết: liên hệ tác giả.

Bài 19. Đoạn ngắn nhất có tổng ít nhất S

Dòng đầu có n, S (1 ≤ n ≤ 10⁵, 1 ≤ S ≤ 10¹⁴), dòng thứ hai có n số nguyên dương (a_i ≤ 10⁹). In ra độ dài ngắn nhất của một đoạn liên tiếp có tổng ít nhất S. Nếu không có đoạn nào thì in ra -1.

Ví dụ:

Nhập	In ra
6 7 2 3 1 2 4 3	2

Kiểm tra: nhập

12 30
4 9 2 7 1 8 6 3 10 2 5 9

Xem đáp số

6

Hướng dẫn giải chi tiết: liên hệ tác giả.

Bài 20. Đếm đoạn có tổng không quá S

Dòng đầu có n, S (1 ≤ n ≤ 10⁵, 1 ≤ S ≤ 10¹⁴), dòng thứ hai có n số nguyên dương (a_i ≤ 10⁹). In ra số đoạn liên tiếp (khác rỗng) có tổng không quá S.

Ví dụ:

Nhập	In ra
4 5 2 1 3 2	7

Kiểm tra: nhập

10 12
5 2 6 1 4 3 8 2 2 7

Xem đáp số

24

Hướng dẫn giải chi tiết: liên hệ tác giả.

Bài 21. Xâu con không lặp ký tự

Nhập một xâu s gồm chữ cái thường (1 ≤ |s| ≤ 10⁵). In ra độ dài lớn nhất của một đoạn ký tự liên tiếp của s mà không có ký tự nào xuất hiện hai lần.

Ví dụ: nhập abcabcbb thì in ra 3.

Kiểm tra: nhập bumbiiacademy.

Xem đáp số

6

Hướng dẫn giải chi tiết: liên hệ tác giả.

Bài 22. Sửa đường

Một con đường gồm n đoạn, mỗi đoạn tốt (1) hoặc hỏng (0). Đội sửa đường sửa được nhiều nhất k đoạn hỏng. Dòng đầu có n, k (1 ≤ n ≤ 10⁵, 0 ≤ k ≤ n), dòng thứ hai là xâu n ký tự 0/1. In ra độ dài lớn nhất của một quãng đường liên tiếp toàn đoạn tốt sau khi sửa.

Ví dụ:

Nhập	In ra
10 2 1101001110	6

Kiểm tra: nhập

20 3
10011010001110100110

Xem đáp số

9

Hướng dẫn giải chi tiết: liên hệ tác giả.

Bài 23. Giỏ trái cây

Hàng cây có n cây, cây thứ i cho loại quả a_i. Bạn có k cái giỏ, mỗi giỏ chỉ đựng một loại quả. Chọn một đoạn cây liên tiếp và hái mỗi cây đúng một quả, mọi quả phải vào giỏ. Dòng đầu có n, k (1 ≤ k ≤ n ≤ 10⁵), dòng thứ hai có n số a_i (1 ≤ a_i ≤ 10⁶). In ra số quả nhiều nhất hái được.

Ví dụ:

Nhập	In ra
7 2 1 2 1 3 3 2 3	4

Kiểm tra: nhập

15 3
4 1 4 2 5 5 2 1 1 3 1 3 3 6 1

Xem đáp số

8

Hướng dẫn giải chi tiết: liên hệ tác giả.

Bài 24. Đếm đoạn có đúng k giá trị khác nhau

Dòng đầu có n, k (1 ≤ k ≤ n ≤ 10⁵), dòng thứ hai có n số nguyên (1 ≤ a_i ≤ 10⁶). In ra số đoạn liên tiếp có đúng k giá trị khác nhau.

Ví dụ:

Nhập	In ra
5 2 1 2 1 2 3	7

Kiểm tra: nhập

12 3
1 2 1 3 4 2 2 3 1 1 4 2

Xem đáp số

14

Hướng dẫn giải chi tiết: liên hệ tác giả.

Bài 25. Sưu tầm đủ bộ thẻ

Có n gói bánh xếp thành hàng, gói thứ i có thẻ số a_i (1 ≤ a_i ≤ m). Cần mua một dãy gói liên tiếp sao cho có đủ cả m loại thẻ 1, 2, …, m. Dòng đầu có n, m (1 ≤ m ≤ n ≤ 10⁵), dòng thứ hai có n số a_i. In ra số gói ít nhất phải mua, hoặc -1 nếu không thể.

Ví dụ:

Nhập	In ra
8 3 2 1 1 3 2 1 1 2	3

Kiểm tra: nhập

15 4
1 2 2 1 3 3 2 4 4 1 1 2 3 1 4

Xem đáp số

4

Hướng dẫn giải chi tiết: liên hệ tác giả.

Nhóm 5. Vận dụng

Bài 26. Đếm đoạn có tổng đúng bằng S

Dòng đầu có n, S (1 ≤ n ≤ 10⁵, 1 ≤ S ≤ 10¹⁴), dòng thứ hai có n số nguyên dương (a_i ≤ 10⁹). In ra số đoạn liên tiếp có tổng đúng bằng S.

Ví dụ:

Nhập	In ra
6 5 1 4 1 3 1 2	3

Kiểm tra: nhập

12 10
3 2 5 1 4 5 2 3 5 6 4 1

Xem đáp số

6

Hướng dẫn giải chi tiết: liên hệ tác giả.

Bài 27. Trạm phát sóng

Có n ngôi nhà trên một con đường thẳng, nhà thứ i ở tọa độ x_i (các tọa độ chưa sắp xếp, có thể trùng nhau). Một trạm phát sóng phủ được mọi nhà trong một đoạn đường dài L (gồm cả hai đầu đoạn). Dòng đầu có n, L (1 ≤ n ≤ 10⁵, 0 ≤ L ≤ 10⁹), dòng thứ hai có n số x_i (0 ≤ x_i ≤ 10⁹). In ra số nhà nhiều nhất một trạm phủ được.

Ví dụ:

Nhập	In ra
6 4 7 1 3 9 2 12	3

Kiểm tra: nhập

12 10
25 3 14 8 40 17 21 9 33 12 5 30

Xem đáp số

5

Hướng dẫn giải chi tiết: liên hệ tác giả.

Bài 28. Hai số gần nhau nhất của hai dãy

Dòng đầu có n, m (1 ≤ n, m ≤ 10⁵). Dòng thứ hai có n số nguyên của dãy A, dòng thứ ba có m số nguyên của dãy B (chưa sắp xếp, giá trị tuyệt đối không quá 10⁹). Chọn một số x trong A và một số y trong B. In ra giá trị nhỏ nhất của |x - y|.

Ví dụ:

Nhập	In ra
4 4 1 3 15 11 23 127 8 19	3

Kiểm tra: nhập

7 6
-20 45 3 88 -7 61 30
100 -12 52 17 70 -40

Xem đáp số

5

Hướng dẫn giải chi tiết: liên hệ tác giả.

Lời giải chi tiết các bài luyện tập

Đáp số của từng bài ở ngay dưới đề để các bạn tự kiểm tra. Lời giải chi tiết (phân tích, chạy tay, chương trình Python và C++, lưu ý khi làm bài) có trong bộ tài liệu có phí của chuyên đề.

Thầy cô và các bạn muốn mua bộ tài liệu vui lòng liên hệ tác giả qua Zalo 0972465159 hoặc Facebook.