let menu = ["Home", "Algorithms", "CodeHub", "VNOI Statistics"];

Overview

SEARCH - Dãy số

solution.md

Bài này ta có thể xây dựng thuật toán với độ phức tạp tuyến tính.

Xét ví dụ test đề bài:

A = 1, 2, 3
B = 5, 9
C = 1, 2, 9, 2, 2, 1, 4, 5, 3, 1, 2

Ta thấy các phần tử của dãy B sẽ chia dãy C thành các dãy con, cụ thể trong ví dụ trên, dãy C bị chia thành \(C_1 = (1, 2)\), \(C_2 = (2, 2, 1, 4)\), \(C_3 = (3, 1, 2)\) là những đoạn con liên tiếp không chứa phần tử nào của B.

Sau khi đã chia được C thành những đoạn con như trên, với mỗi đoạn con ta cần phải kiểm tra xem toàn bộ các phần tử của A có nằm trong đó không.

Cần cài đặt khéo để có thể đạt độ phức tạp tuyến tính như bên dưới.

main.cpp
Open in Github • Download 
#include <iostream>
#include <vector>
using namespace std;
#define N 100001

int main() {
    ios::sync_with_stdio(false); cin.tie(0);
    int m, n, p;
    cin >> m >> n >> p;
    vector<bool> a(N, false), b(N, false);
    vector<int> c(p);
    while (m--) {
        int x; cin >> x;
        a[x] = true;
    }
    while (n--) {
        int x; cin >> x;
        b[x] = true;
    }
    for (int &c: c) cin >> c;

    int count_a = 0;
    for (bool x: a) if (x) count_a += 1;

    int test = 1, len = 0, count = 0;
    int res = 0;
    vector<int> f(N, 0);

    for (int x: c) {
        if (b[x]) {
            test += 1;
            len = 0;
            count = 0;
        } else {
            len += 1;
            if (a[x] && f[x] != test) {
                f[x] = test;
                count += 1;
            }
            if (count == count_a) res = max(res, len);
        }
    }

    cout << res;
    return 0;
}
Comments