Hướng dẫn cho Bội P

Chỉ sử dụng khi thực sự cần thiết như một cách tôn trọng tác giả và người viết hướng dẫn này.

Chép code từ bài hướng dẫn để nộp bài là hành vi có thể dẫn đến khóa tài khoản.

Authors: SPyofgame

<button style="text-align:center; font-size:30px; color:none; background:none; border:none; padding:0; position:relative; left:38.5%;">
$\color{#ff0000}{\text{Spoiler Alert}_{{}_{{}^{{}^{v2.95}}}}}$
</button>

$\color{#ff7500}{\text{Khuyến khích bạn đọc trước khi đọc phần lời giải xin hãy thử code ra thuật của mình dù nó có sai hay đúng}}$ $\color{#ff7500}{\text{Và sau đó từ phần bài giải và thuật toán trước đó mà đối chiếu với thuật của mình và thu được bài học cho mình}}$ $\color{#ff7500}{\text{Mình xin rút kinh nghiệm và chấn chỉnh bản thân nếu trong editorial có gì sai sót, và bạn có thể gửi feedback }}$ [ở đây](https://www.facebook.com/SPectiar2k/)

<button style="text-align:center; font-size:30px; color:none; background:none; border:none; padding:0; position:relative; left:38.5%;">
$\color{orange}{\text{Mục lục}}$
</button>

$\color{#300000}{\text{1. Hướng dẫn trường hợp: } P = 1}$

$\color{#903030}{\text{Mục tiêu:}}$ Tính xem số viên bi lấy được nhiều nhất sao cho không tồn tại cùng lúc 2 viên bi giống nhau ($\frac{x}{y} \neq 1 \Leftrightarrow x \neq y$)
$\color{#903030}{\text{<Duyệt toàn tập>}}$

Gọi $A[]$ là dãy số nhận vào, $A[] = \{a_1, a_2, \dots, a_n\}$

Thử mọi dãy con $S \subseteq A[]$ và kiểm tra nếu tồn tại $i \neq j$ để $S_i = S_j$ thì loại. Ngược lại trong số các tập con được chọn ta sẽ cập nhật kết quả tối ưu nhất: $res = max\{|S|\}$

Công thức: $res = max\{|S|\}$ với $S \subseteq A[], (\forall i \neq j \Leftrightarrow S_i \neq S_j)$

$\color{#903030}{\text{<Sắp xếp và loại bỏ>}}$

Ta sẽ sắp xếp mảng $A[]$ tăng (giảm) dần.

Gọi tập $S$ là tập kết quả. Cứ mỗi khi lấy một phần tử, ta loại tất cả các phần tử bằng nó, hoặc chặt nhị phân để nhảy tới vị trí đầu tiên có phần tử lớn (nhỏ) hơn tiếp theo.

Kết quả bài toán là $res = |S|$

$\color{#903030}{\text{<Cấu trúc dữ liệu>}}$

Gọi CTDL $S$ có thể tìm kiếm và chèn giá trị $x$ vào tập.

Ta duyệt từng phần tử $x \in A[]$. Nếu $x \notin S$ thì ta chèn $x$ vô $S$.

Kết quả bài toán là $res = |S|$

$\color{#903030}{\text{<Độ phức tap>}}$

$\color{#903030}{\text{<Duyệt toàn tập>}}$ Có tất cả $2^n$ tập con của $A[] (n = |A|)$ $\Rightarrow$ $\Theta(2^n)$ thời gian

$\color{#903030}{\text{<Sắp xếp và loại bỏ>}}$ Việc sắp xếp mất $O(n\ log\ n)$ và loại bỏ mất $O(n)$ $\Rightarrow$ $O(n\ log\ n)$ thời gian

$\color{#903030}{\text{<Cấu trúc dữ liệu>::<Cây nhị phân tìm kiếm>}}$ Việc tìm kiếm và chèn mất $O(log\ n)$ mỗi phần tử $\Rightarrow$ $O(n\ log\ n)$ thời gian

$\color{#903030}{\text{<Cấu trúc dữ liệu>::<Mảng băm>}}$ Việc tìm kiếm và chèn mất $O(1)$ mỗi phần tử $\Rightarrow$ $O(n)$ thời gian

$\color{#009933}{\text{1. Code tham khảo}}$: <Cấu trúc dữ liệu>::<Mảng băm>

$^{^{\color{#7f5f3f}{\text{Độ phức tạp : }} O(n)\ \color{#7f5f3f}{\text{thời gian}}\ ||\ O(n)\ \color{#7f5f3f}{\text{bộ nhớ}}}}$

C++

vector<ll> a;
int solve_p1()
{
    unordered_set<ll> S;
    for (ll x : a) S.insert(x);
    return S.size();
}

$\color{#300000}{\text{2. Hướng dẫn trường hợp: } a_i \leq 20}$

$\color{#7f5f3f}{\text{<Nhận xét tham lam>}}$ Nếu loại trường hợp $P = 1$ riêng ra, thì khi ta lấy $a_i$ thì mọi $a_j = a_i$ ta cũng lấy vì $\frac{a_i}{a_j} = 1 \neq P$
$\color{#903030}{\text{Mục tiêu:}}$ Tính xem số viên bi lấy được nhiều nhất qua việc chọn các giá trị để lấy sao cho không tôn tại 2 giá trị bất kì chênh nhau $P$ lần ($\frac{x}{y} \neq P\ \forall x, y \in S$)
$\color{#903030}{\text{<Duyệt toàn tập>}}$

Gọi tập các giá trị phân biệt trong $A[]$ là $T$

Gọi $f[x]$ là số lần $x$ xuất hiện trong mảng $A[]$

Gọi giá trị của một tập $S$ bất kì là $V_S = \underset{x \in S}{\Sigma{f[x]}}$

Ta sẽ thử từng tập $S \subseteq T$ sao cho $\forall x, y \in S\ \rightarrow x \neq P \times y$.

Kết quả bài toán sẽ là $res = max(V_S)$

$\color{#903030}{\text{<Quy hoạch động trạng thái>}}$

Xét trạng thái hiện tại bằng một dãy bit bằng số nguyên $mask$. Với việc không được chọn số $x$ tương ứng bit thứ $x$ của số $mask$ được bật

Gọi $g[mask]$ là giá trị tối đa khi không chọn các số được đánh dấu, ta sẽ xét 2 khả năng là chọn hoặc không chọn $a[i]$, với khởi tạo là $0$.

Kết quả bài toán là $res = max(g[mask])$

$\color{#903030}{\text{<Nhánh cận>}}$

Gọi tập $S$ là tập các giá trị không được chọn

Gọi đệ quy $trau(S, i)$ là giá trị tói đa lấy được xét từ vị trí $[i] \rightarrow [n]$ và không chọn các giá trị $x \in S$.

Kết quả bài toán là $res = trau(\emptyset, 1)$

$\color{#903030}{\text{<Độ phức tap>}}$ Nhìn chung thì đều vào khoảng $O(2^{20})$

$\color{#903030}{\text{<Duyệt toàn tập>}}$ Chậm hơn vì phải xét tất cả trường hơn: $O(f(x)) = O(2^{20})$

$\color{#903030}{\text{<Quy hoạch động trạng thái>}}$ Nhanh hơn nhưng tốn nhiều bộ nhớ không cần thiết. $O(f(x)) \approx O(2^{20})$

$\color{#903030}{\text{<Nhánh cận>}}$ Nhanh hơn, tốt ít bộ nhớ và có thể giải lớn hơn $O(f(x)) \leq O(2^k)$ với $k$ là số phần tử phân biệt

$\color{#c01515}{\text{2a. Tiếp cận quy hoạch động trạng thái}}$

$\color{#f03030}{\text{<Mảng quy hoạch động>}}$ Gọi $g[mask]$ là giá trị tối đa khi không chọn các số được đánh dấu. Số $x$ được đánh dấu khi bit thứ $x$ trong số nguyên $mask$ được bật. Ban đầu $g[mask] = 0$
$\color{#f03030}{\text{<Công thức tính>}}$ Duyệt từng giá trị $x \in \{1, 2, \dots, 20\}$.

Khi lấy $x$, ta có $g[mask] = g[mask | 2^{P \times x}] + f[x]$

Khi bỏ qua $x$, ta có $g[mask] = g[mask | 2^{P \times x}]$

Kết quả $g[mask]$ sẽ là max của 2 cách chon.

Kết quả bài toán sẽ là $res = max(g[mask])$

Ta chỉ cần quan tâm các trạng thái trong khoảng $[0 \dots 2^{20} - 1]$, nếu ta gọi các trạng thái lớn hơn ta sẽ coi nó là $0$.

$\color{#c01515}{\text{2b. Tiếp cận nhánh cận}}$

$\color{#f03030}{\text{<Hàm đệ quy>}}$ $trau(S, i)$ là giá trị tói đa lấy được xét từ vị trí $[i] \rightarrow [n]$ và không chọn các giá trị $x \in S$

Gọi $(v[i], f[i])$ là cặp (giá trị phân biệt $v[i]$) và ($f[i]$ là số lần xuất hiện $v[i]$ trong mảng $A[]$)

$\color{#f03030}{\text{<Công thức tính>}}$

Khi duyệt hết các mảng $v[]$ thì $trau(S, i) = 0$

Nếu ta chọn $a_i$

Gọi $x = P \times a_i$ là giá trị mình không được lấy khi lấy $a_i$

Nếu $x \in A[]$ thì ta thêm vào tập $S$

Để tránh tràn số, ta khẳng định được ngay khi $a[i] > \lfloor \underset{1..n}{max}(a[i])\ /\ P \rfloor$ thì $x \notin A[]$

Khi $x \in A[]$ Ta có $trau(S, i) = trau(S \cup x, i + 1) + f[a[i]]$

Khi $x \notin A[]$ Ta có $trau(S, i) = trau(S, i + 1) + f[a[i]]$

Nếu ta không chọn $a[i]$, ta giữ nguyên tập $S$. Nên ta có $trau(S, i) = trau(S, i + 1)$

$\color{#009933}{\text{2a. Code tham khảo}}$: Quy hoạch động trạng thái

$^{^{\color{#7f5f3f}{\text{Độ phức tạp : }} O(2^{20})\ \color{#7f5f3f}{\text{thời gian}}\ ||\ O(2^{20})\ \color{#7f5f3f}{\text{bộ nhớ}}}}$

C++

ll P;
const int lim = 20;
const int limmask = (1 << lim) - 1;

vector<int> f; /// f[x]    : So luong ai = x
vector<int> g; /// g[mask] : max so luong lay duoc & khong lay cac gia tri x co bit x duoc bat
int magic(int x = 1, int mask = 0)
{
    if (x > 20) return 0; /// Xet x trong doan [1..20]

    int &res = g[mask >> 1]; /// Bo qua bit thu [0]
    if (res != -1) return res;

    maximize(res, magic(x + 1, mask) + 0); /// Khong chon x
    if (mask >> x & 1) == false) /// Neu x chua duoc danh dau
    { 
        if (P * x <= 20) mask |= 1 << (P * x);    /// Chi quan tam cac gia tri < limmask
        maximize(res, magic(x + 1, mask) + f[x]); /// Chon x
    }

    return res;
}

int solve_p20()
{
    if (P == 1) return solve_p1();

    f.assign(lim, 0);
    for (ll x : a) ++f[x];

    g.assign(limmask + 1, -1);
    return magic();
}

$\color{#009933}{\text{2b. Code tham khảo}}$: Nhánh cận

$^{^{\color{#7f5f3f}{\text{Độ phức tạp : }} O(2^k \times log(k))\ \color{#7f5f3f}{\text{thời gian}}\ ||\ O(k)\ \color{#7f5f3f}{\text{bộ nhớ}}}}$

C++

ll P;
ll lim;
int k; 
vector<ll> v;
vector<int> f;
int trau(set<ll> &S, int i = 0)
{
    if (i >= k) return 0;

    int res = 0;
    if (v[i] <= lim || S.count(v[i])) res = trau(S, i + 1); /// Neu khong chon v[i]
    if (S.count(v[i]) == false) /// Neu chon duoc v[i]
    {
        if (v[i] <= lim) /// Co the ton tai x
        {
            ll x = v[i] * P;
            bool marking = binary_search(all(v), x); /// mark = true <=> x thuoc A[]
            if (marking) S.insert(x);             
            maximize(res, f[i] + trau(S, i + 1));
            if (marking) S.erase(x);
        }
        else maximize(res, f[i] + trau(S, i + 1));
    }

    return res;
}

int solve_p20()
{
    if (P == 1) return solve_p1();
    ll mx = *max_element(all(a));
    lim = mx / P;

    map<ll, int> M;
    map<ll, int>::iterator it;
    for (int i = 0; i < n; ++i)
        ++M[a[i]];

    for (it = M.begin(); it != M.end(); ++it)
    {
        v.push_back(it -> first);  /// Cac gia tri v[i] phan biet
        f.push_back(it -> second); /// So lan xuat hien v[i] = trong A[]
    }

    k = v.size();
    return trau();
}

$\color{#c01515}{\text{3. Hướng dẫn chia để trị}}$

$\color{#7f5f3f}{\text{<Nhận xét chia>}}$ Nếu loại trường hợp $P = 1$ ra, ứng với cách trên, có những giá trị sẽ không có liên quan và ảnh hưởng tới nhau. Ta sẽ chia dãy thành các nhóm để xử lí riêng. Trong đó giá trị $x, y$ có thể ảnh hưởng nhau khi tồn tại số mũ $k \in \mathbb{Z}$ để $x = P^k \times y$.
$\color{#7f5f3f}{\text{<Nhận xét trị>}}$ Xét một bài toán con là tập con $S \subseteq A[]$. Để tiện tính toán, hãy để dãy được sắp xếp giảm dần, và $\exists x \in A[]\ \rightarrow\ \forall y \in S \{y = P^k\times x | k \in \mathbb{Z}\}$. Khi này, số lượng tối đa ta lấy được là việc chọn tối ưu các giá trị không kề nhau trong tập $S$ (sau khi sắp xếp)
$\color{#f03030}{\text{<Phân tích độ phức tạp>}}$

Khi $P = 1$ thì $O(n)$

Lấy các cặp $(v_i, f_i)$ giảm dần: $O(n\ \log\ n)$

Phần chia: $O(\Sigma(|S|)) = O(n)$

Phần trị: $O(|S|) = O(log_p(n))$

Trường hợp chạy lâu nhất: Khi dãy phân biệt và có dạng $x \times 2^k$, với $x = 1..n$

$\color{#c01515}{\text{3. Tiếp cận}}$

$\color{#f03030}{\text{<Xử lí chia>}}$ Gọi cặp $(v_i, f_i)$ nghĩa là giá trị $v_i \in A[]$ xuất hiện đúng $f_i$ lần. Và đặt $F[v_i] = f_i$ và $F[x \notin A[]] = 0$

Ta sắp xếp mảng giảm dần theo $v_i$. Duyệt theo thứ tự từ lớn xuống bé (để khỏi xét các giá trị $\{x = v_i \times P^k\ |\ k \in \mathbb{N}^*\}$

Ta sẽ chọn $F[v_i], F[\frac{v_i}{P}], F[\frac{v_i}{P^2}], F[\frac{v_i}{P^3}], \dots$ vào tập mới để xử lí (chỉ chọn những kết quả $F[v] \in \mathbb{N}$). và loại các cặp được chọn ra

Lưu ý rằng nếu ta dùng phép nhân, hãy chú ý xử lí tràn số hoặc dùng phép tính bão hòa

$\color{#f03030}{\text{<Xử lí trị>}}$ Sau khi có tập $S$ là số lượng xuất hiện của các giá trị dạng $x = \frac{v_i}{P^k}$ sắp xếp giảm dần (theo $x$).

Ta sẽ dùng quy hoạch động xét $magic(i)$ là giá trị tối đa khi xét từ $[i] \rightarrow [n]$

Khi duyệt hết $(i = n + 1)$ có $magic(i) = 0$

Khi chọn $S_i$, ta không được chọn $S_{i + 1}$, nên $magic(i) = magic(i + 2) + S_i$

Khi không chọn $S_i$, ta được chọn $S_{i + 1}$, nên $magic(i) = magic(i + 1) + 0$

Kết quả của $magic(i)$ là max của 2 cách trên

Kết quả của bài toán là $res = magic(1)$

$\color{#009933}{\text{3a. Code tham khảo}}$: <Chia để trị>::Chia, <Cấu trúc dữ liệu>::Map

$^{^{\color{#7f5f3f}{\text{Độ phức tạp : }} O(n\ log\ n)\ \color{#7f5f3f}{\text{thời gian}}\ ||\ O(n)\ \color{#7f5f3f}{\text{bộ nhớ}}}}$

C++

int n;
ll P;
vector<ll> a;
vector<ll> S;
vector<ll> f;
int main()
{
    cin >> n >> P;
    a.resize(n);
    for (ll &x : a) cin >> x;

    if (P == 1)
    {
        unordered_set<ll> S;
        for (ll x : a) S.insert(x);
        cout << S.size();
        return 0;
    }

    map<ll, int, greater<ll> > M;
    map<ll, int, greater<ll> >::iterator it;
    for (ll x : a) ++M[x];

    ll res = 0;
    for (it = M.begin(); it != M.end(); ++it)
    {
        ll  v = it -> first;
        int f = it -> second;
        S.assign(1, f);

        while (v % P == 0)
        {
            v /= P;
            if (M.count(v) == false) break; /// Co the bo nhanh can
            S.push_back(M[v]);
            M.erase(v);
        }

        f.assign(S.size(), -1);
        res += solve();
    }
    cout << res;
    return 0;
}

$\color{#009933}{\text{3b. Code tham khảo}}$: <Chia để trị>::Trị, <Quy hoạch động>

$^{^{\color{#7f5f3f}{\text{Độ phức tạp : }} O(|S|)\ \color{#7f5f3f}{\text{thời gian}}\ ||\ O(|S|)\ \color{#7f5f3f}{\text{bộ nhớ}}}}$

C++

vector<ll> S;
vector<ll> f;
ll solve(int i = 0)
{
    if (i >= S.size()) return 0LL;

    ll &res = f[i];
    if (res != -1) return res;
    maximize(res, solve(i + 1) + 0);    /// Khong chon S[i]
    maximize(res, solve(i + 2) + S[i]); ///   Co  chon S[i]

    return res;
}

Bình luận

15

SPyofgame 10:32 p.m. 4 Tháng 11, 2020 ← đã chỉnh sửa →

Done UwU

-1

undertracked 6:56 a.m. 5 Tháng 11, 2020

bữa ngày 1 trường tui mất mạng, không thi được và tui phải đấm bằng điện thoại :)) ối dào, tui chép code từ màn hình máy tính sang điện thoại thiếu chữ này chữ nọ hoài luôn :v

0

undertracked 6:54 a.m. 5 Tháng 11, 2020

range based for loop chứ cần quái gì phải iterator :v mà này, tui viết editorial bài empires được không?

-2

SPyofgame 6:57 a.m. 5 Tháng 11, 2020

ok :v

-2

undertracked 7:37 a.m. 5 Tháng 11, 2020

này ông mà inline latex trên này làm sao vậy 😭😭

-2

SPyofgame 7:44 a.m. 5 Tháng 11, 2020

$ latex $

-1

À ông à, nãy giờ tui đấm mấy đấm liên tục luôn :V Cẩu thả quá mà, tui chỉ ngáo một chỗ mà do chủ quan chấm online nên tui cứ sửa vớ sửa vẩn :)) Chứ không lo sinh test để debug :)) Chứ bản thân tui thì cách làm thì tư tưởng cũng giống ông đấy, có điều là tui dựng đồ thị với lại chặt nhị phân thay vì dùng cây nhị phân cân bằng như ông.

C++

#include <bits/stdc++.h>
using namespace std;
#define int long long
signed main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);

    int n, p;
    cin >> n >> p;

    vector<int> input(n);
    for (int &x: input) cin >> x;
    sort(input.begin(), input.end());

    auto cloned = input;
    auto element_count = [&](int x) {
        return upper_bound(cloned.begin(), cloned.end(), x) - lower_bound(cloned.begin(), cloned.end(), x);
    };

    input.erase(
        unique(input.begin(), input.end()),
        input.end()
    );

    n = input.size();

    if (p == 1)
    {
        cout << n << "\n";
        return 0;
    }

    vector<vector<int>> graph(n);

    for (int i = 0; i < n; i++)
    {
        if (input[i] % p != 0) continue;
        auto opponent = lower_bound(input.begin(), input.end(), input[i] / p);
        if (opponent == input.end()) continue;
        if (*opponent != input[i] / p) continue;
        int index = opponent - input.begin();
        graph[i].push_back(index);
        graph[index].push_back(i);
    }

    vector<int> visited(n);

    int result = 0;

    for (int i = 0; i < n; i++)
    {
        if (visited[i]) continue;
        visited[i] = true;
        vector<int> component = { i };
        queue<int> vertices;
        vertices.push(i);
        while (!vertices.empty())
        {
            int top = vertices.front();
            vertices.pop();
            for (int adjacent: graph[top])
                if (!visited[adjacent])
                {
                    visited[adjacent] = true;
                    component.push_back(adjacent);
                    vertices.push(adjacent);
                }
        }

        vector<int> dp(component.size());

        for (int i = 0; i < component.size(); i++)
        {
            if (i == 0)
            {
                dp[i] = element_count(input[component[i]]);
                continue;
            }

            if (i == 1)
            {
                dp[i] = max(element_count(input[component[i]]), element_count(input[component[i - 1]]));
                continue;
            }

            dp[i] = max(dp[i - 1], dp[i - 2] + element_count(input[component[i]]));
        }

        result += dp.back();
    }

    cout << result << "\n";
}

-1

SPyofgame 4:01 p.m. 5 Tháng 11, 2020

Tui thắc mắc là sao ông không nhắn ở bài Empire :v

-2

undertracked 5:40 p.m. 5 Tháng 11, 2020

Code này là bài MULTM :v Còn editorial bài Empires tui không biết tạo mục thế nào nên tui comment cái editorial trên này.

P/S: tui là cái thằng Huỳnh Trần Khanh "không ai biết" trong From vnoi with love đấy :))

-1

3070RKH 12:54 a.m. 6 Tháng 11, 2020

> Huỳnh Trần Khanh

> không ai biết

bold assumption, đến cả anh ngfam còn nhận ra khi anh quay lại

-1

undertracked 7:54 a.m. 6 Tháng 11, 2020

read and downvoted uwu

i think it's time you practiced using the mighty segment tree, lol

-1

3070RKH 12:31 p.m. 6 Tháng 11, 2020

I actually had some ideas of processing things offline, but I've been extremely stupid these days so I got stuck, probably I need a bit more extreme practice

also, a bit personal but it's pretty hard to track you down nowadays, I suppose? as if, you vanished from the internet all of a sudden and came back xp

-1

undertracked 3:17 p.m. 6 Tháng 11, 2020

hey just a general reminder that you can always talk to me through email, responses may be delayed but it is the most reliable means to reach me

-1

undertracked 12:53 p.m. 6 Tháng 11, 2020 ← đã chỉnh sửa →

yeah you need extreme practice, to the point where you are physically unable to study normal subjects at school. competitive programming requires extreme persistence

the problems have been really easy but because of my stupid mind i couldn't solve most of them. i am stupid, stupid, stupid, stupid.

i need to work even harder to eradicate my stupidity, for good. there's still time left for me to rectify my stupidity

1 bình luận nữa

Hướng dẫn cho Bội P

\(\color{#300000}{\text{1. Hướng dẫn trường hợp: } P = 1}\)

\(\color{#009933}{\text{1. Code tham khảo}}\): <Cấu trúc dữ liệu>::<Mảng băm>

\(^{^{\color{#7f5f3f}{\text{Độ phức tạp : }} O(n)\ \color{#7f5f3f}{\text{thời gian}}\ ||\ O(n)\ \color{#7f5f3f}{\text{bộ nhớ}}}}\)

\(\color{#300000}{\text{2. Hướng dẫn trường hợp: } a_i \leq 20}\)

\(\color{#c01515}{\text{2a. Tiếp cận quy hoạch động trạng thái}}\)

\(\color{#c01515}{\text{2b. Tiếp cận nhánh cận}}\)

\(\color{#009933}{\text{2a. Code tham khảo}}\): Quy hoạch động trạng thái

\(^{^{\color{#7f5f3f}{\text{Độ phức tạp : }} O(2^{20})\ \color{#7f5f3f}{\text{thời gian}}\ ||\ O(2^{20})\ \color{#7f5f3f}{\text{bộ nhớ}}}}\)

\(\color{#009933}{\text{2b. Code tham khảo}}\): Nhánh cận

\(^{^{\color{#7f5f3f}{\text{Độ phức tạp : }} O(2^k \times log(k))\ \color{#7f5f3f}{\text{thời gian}}\ ||\ O(k)\ \color{#7f5f3f}{\text{bộ nhớ}}}}\)

\(\color{#c01515}{\text{3. Hướng dẫn chia để trị}}\)

\(\color{#c01515}{\text{3. Tiếp cận}}\)

\(\color{#009933}{\text{3a. Code tham khảo}}\): <Chia để trị>::Chia, <Cấu trúc dữ liệu>::Map

\(^{^{\color{#7f5f3f}{\text{Độ phức tạp : }} O(n\ log\ n)\ \color{#7f5f3f}{\text{thời gian}}\ ||\ O(n)\ \color{#7f5f3f}{\text{bộ nhớ}}}}\)

\(\color{#009933}{\text{3b. Code tham khảo}}\): <Chia để trị>::Trị, <Quy hoạch động>

\(^{^{\color{#7f5f3f}{\text{Độ phức tạp : }} O(|S|)\ \color{#7f5f3f}{\text{thời gian}}\ ||\ O(|S|)\ \color{#7f5f3f}{\text{bộ nhớ}}}}\)

Bình luận