Hướng dẫn cho Dãy Cuốm


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


\(\color{red}{\text{Spoiler Alert}_{{}_{{}^{{}^{v2.0}}}}}\)

\(\color{red}{\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{red}{\text{Sau đó từ phần bài giải và thuật toán trước đó mà đối chiếu, rút nhận xét với thuật của mình và thu được bài học (không lãng phí thời gian đâu).}}\)



\(\color{orange}{\text{Hướng dẫn}}\)

  • \(Mục tiêu:\)

A) Chọn vị trí đặt chữ

😎 Chọn chữ để đặt

C) Tính kết quả

D) Chọn kết quả tối ưu nhất


\(\color{goldenrod}{\text{Tiếp cận}}\)

  • Chọn vị trí đặt chữ và chọn chữ để đặt

Duyệt toàn tập: Thử từng vị trí và thử từng chữ để đặt, có \(n + 1\) vị trí và \(26\) kí tự nên có tất cả \(O(26^n)\) cách

Duyệt trâu: Thử từng vị trí và thử từng chữ để đặt, có \(n + 1\) vị trí và ta chỉ cần đặt chữ \(c\) và chữ \(u\) (những chữ khác không ảnh hưởng kết quả) nên có tất cả \(O(2^n)\) cách:

Duyệt tối ưu: Thử đặt chữ \(c\) ở đầu xâu để ghép với tất cả \(u\) ở sau hoặc thử đặt chữ \(u\) ở cuối để ghép với tất cả chữ \(c\) ở trước. Có tất cả \(O(2)\) cách

  • Tính kết quả và chọn kết quả tối ưu nhất

Thử từng xâu con và đếm xem có bao nhiêu xâu "\(cu\)". Nên có tất cả \(O(2^n)\) xâu

Thử từng xâu con độ dài 2 và đếm xem có bao nhiêu xâu "\(cu\)". Nên có tất cả \(O(n^2)\) xâu

Duyệt từng kí tự từ trái qua phải, nếu kí tự hiện tại là \(u\) thì cộng vào kết quả số lượng kí tự \(c\) bên trái nó băng quy hoạch động. Nên chỉ mất \(O(n)\)

Kết quả tối ưu nhất là max của các cách để đặt thêm một kí tự vào xâu


\(\color{green}{\text{Code tham khảo }}\): Approach

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

C++
#include <iostream>

using namespace std;

long long solve(const string &s)
{
    int cnt_c = 0;
    long long res = 0;
    for (char c : s)
    {
        if (c == 'c')
        {
            ++cnt_c;
        }

        if (c == 'u')
        {
            res += cnt_c;
        }
    }

    return res;
}

int main()
{
    int n;
    cin >> n;

    string s;
    cin >> s;

    cout << max(solve(s + 'u'), solve('c' + s));
    return 0;
}


Bình luận


  • 1
    quoc81bk    10:27 p.m. 13 Tháng 8, 2021

    Cho mình hỏi code này có nghĩa là gì ạ? (char c : s)


    • 2
      jumptozero    9:00 a.m. 14 Tháng 8, 2021

      Có nghĩa là duyệt qua từng phần tử của xâu \(s\) ấy bạn, bạn có thể code một đoạn nho nhỏ sau để hiểu nó nè:

      C++
      #include<bits/stdc++.h>
      using namespace std;
      string s;
      int main(){
          cin>>s;
          for(char c: s) cout<<c<<'\n';
          return 0;
      }
      

      • 3
        quoc81bk    9:24 a.m. 14 Tháng 8, 2021

        Mình cảm ơn bạn nhiều nghe.

      1 bình luận nữa