Hướng dẫn giải của Duyên Hải 2020 - Lớp 10 - Bài 1 - LED


Chỉ dùng lời giải này khi không có ý tưởng, và đừng copy-paste code từ lời giải này. Hãy tôn trọng người ra đề và người viết lời giải.
Nộp một lời giải chính thức trước khi tự giải là một hành động có thể bị ban.

Tác giả: SPyofgame


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

  • Truy vấn ~V = 1~: Tính tổng vạch led bật mỗi chữ số từ số ~n~

Tiền xử lí ~10~ chữ số ~0..9~ xem nó cần bao nhiêu vạch led bật

  • Truy vấn ~V = 2~: Với mỗi số ~x > n~ có cùng độ dài với ~n~. Tăng biến đếm nếu ~x~ có chứa các vạch led ~n~

Ta có thể thử xây từng chữ số cho ~x~, từ đó đưa ta đến thuật quy hoạch động chữ số


~\color{goldenrod}{\text{Tiếp cận truy vấn 1}}~

  • Gọi ~csl_x~ là số lượng đèn led cần bật để hiển thị số ~x~ (~x = 0 \rightarrow 9~)

~csl[] = ~ {~6, 2, 5, 5, 4, 5, 6, 3, 7, 6~}

  • Kết quả bài toán là ~res = \underset{x \in n}{\Sigma}(csl_x)~ (~x~ là các chữ số trong ~n~)

~\color{goldenrod}{\text{Tiếp cận truy vấn 2 đệ quy}}~

  • Thử xây từng chữ số với hàm đệ quy magic(int index, bool isGreater)

Với ~index~ là vị trí các chữ số của ~n~ từ trái sang phải

Với ~isGreater~ là biến kiểm tra xem số hiện tại lớn hơn ~n~ chưa

Ta thử xây chữ số tiếp theo là chữ số có chứa các vạch led bật sẵn

  • Ta có thể tiền xử lí xem với mỗi chữ số ~d = 0..9~ thì có những số ~nextd~ nào có vạch led ~d~ bật, tức những cách thỏa mãn

Nếu số hiện tại đã lớn hơn ~n~, thì mình có thể chọn mọi số ~nextd~ <=> ~lower_limit = 0~

Nếu số hiện tại chưa lớn hơn ~n~, thì mình chỉ có thể chọn mọi số ~nextd ≥ d~ <=> ~lower_limit = d~

Nếu số hiện tại đã lớn hơn ~n~ hoặc ~nextd > d~ thì ~isGreater = true~ (khởi tạo là False nhé)

Sau đó ta đệ quy chữ số tiếp theo: ~res = res + magic(index + 1, isGreater || (nextd > lower_limit))~


~\color{goldenrod}{\text{Tiếp cận truy vấn 2 vòng lặp}}~

  • Ta tính tích của (tổng số cách chọn tại ~i~) - (số cách chọn số bé hơn ~n~ tại ~i~)

Duyệt ~i~ từ trái sang phải

Gọi ~ctw = count_total_ways~ là số cách chọn chữ số tại vị trí ~i~

Gọi ~clw = count_less_ways~ là số cách chọn chữ số bé hơn tại vị trí ~i~

Gọi ~res~ là tổng số cách chọn trước đó

Dựa vào đó ta tính tổng số cách chọn bây giờ

  • Ta có thể tiền xử lí xem với mỗi chữ số ~d = 0..9~ thì số cách chọn ~ctw[d]~ và ~clw[d]~ là gì

Có ~ctw[d]~ là số lượng số ~x~ thỏa ~x~ chứa các vạch led ~d~ bật

Có ~clw[d]~ là số lượng số ~x < d~ thỏa ~x~ chứa các vạch led ~d~ bật

Từ đó suy ra công thức toán học ~res = res * ctw[d] - clw[d]~


~\color{purple}{\text{Độ phức tạp}}~

  • Truy vấn 1 mất ~O(log_{10}n)~

  • Truy vấn 2 mất ~O(log_{10}n)~ với hằng số ~O(1), O(2 \times 7), O(10 \times 10), \dots~ tùy cách cài


~\color{green}{\text{Code tham khảo }}~: Quy hoạch động chữ số, Đồ thị đỉnh kề

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

/// Tiền xử lí các vạch led bật
vector<int> cntled = {6, 2, 5, 5, 4, 5, 6, 3, 7, 6};
void solve1()
{
    /// Biểu diễn số dưới dạng xâu
    string s;
    cin >> s;

    /// Kết quả là tổng số lượng vạch led bật
    int res = 0;
    for (char c : s)
        res += cntled[c - '0'];

    cout << res;
}

/// Tiền xử lí
/// vector thứ n biểu diễn tất cả các đèn led mà các vạch led có trong n được bật
vector<vector<int> > G = {
    {0, 8},                 /// [0]
    {0, 1, 3, 4, 7, 8, 9},  /// [1]
    {2, 8},                 /// [2]
    {3, 8, 9},              /// [3]
    {4, 8, 9},              /// [4]
    {5, 6, 8, 9},           /// [5]
    {6, 8},                 /// [6]
    {0, 3, 7, 8, 9},        /// [7]
    {8},                    /// [8]
    {8, 9},                 /// [9]
};

int n;                  /// Độ dài của số nhận vào
vector<int> v;          /// vector chứa các chữ số
vector<vector<ll> > f;  /// vector 2 chiều quy hoạch động
/// hàm magic(i, ign)
/// tại vị trí (i) của số biểu diễn bởi vector (v)
/// đếm số cách mà xây dựng được số có (ign) = true
ll magic(int i = 0, bool ign = false) /// O(n * 2 * 7)
{
    /// Nếu đã duyệt hết vector
    if (i >= n) return ign;

    /// Dùng con trỏ để tiện tính toán
    ll &res = f[i][ign];
    if (res != -1) return res; /// Nếu đã được tính trước đó
    else res = 0;              /// Ngược lại thì reset giá trị

    /// Chúng ta chỉ đếm các số lớn hơn
    int lim = ign ? 0 : v[i];
    for (int d : G[v[i]])
        if (d >= lim)
            res += magic(i + 1, ign || (d > lim));

    /// Đừng quên trả về kết quả :D
    return res;
}

void solve2()
{
    /// Biểu diễn số dưới dạng xâu
    string s;
    cin >> s;

    /// Dùng vector (v) độ dài (n) để lưu trữ các chữ số
    n = s.size();
    for (char c : s) v.pb(c - '0');

    /// Khởi tạo -1 tức là chưa được tính trước đó
    f.assign(n + 1, vector<ll>(2, -1));
    cout << magic();
}

~\color{green}{\text{Code tham khảo }}~: Quy hoạch động chữ số, Đồ thị ma trận

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

/// Tiền xử lí các vạch led bật
vector<int> cntled = {6, 2, 5, 5, 4, 5, 6, 3, 7, 6};
void solve1()
{
    ll n = readLong();
    int res = 0;       /// Kết quả là tổng số lượng vạch led bật
    do res += cntled[n % 10]; while (n /= 10);
    cout << res;
}


/// Tiền xử lí
/// bit thứ (i) của vector thứ (n) biểu diễn có thể chuyển đổi từ (led-i) sang (led-n) hay không
vector<vector<bool> > G = {
    {1, 0, 0, 0, 0, 0, 0, 0, 1, 0}, /// [0] - 0, 8
    {1, 1, 0, 1, 1, 0, 0, 1, 1, 1}, /// [1] - 0, 1, 3, 4, 7, 8, 9
    {0, 0, 1, 0, 0, 0, 0, 0, 1, 0}, /// [2] - 2, 8
    {0, 0, 0, 1, 0, 0, 0, 0, 1, 1}, /// [3] - 3, 8, 9
    {0, 0, 0, 0, 1, 0, 0, 0, 1, 1}, /// [4] - 4, 8, 9
    {0, 0, 0, 0, 0, 1, 1, 0, 1, 1}, /// [5] - 5, 6, 8, 9
    {0, 0, 0, 0, 0, 0, 1, 0, 1, 0}, /// [6] - 6, 8
    {1, 0, 0, 1, 0, 0, 0, 1, 1, 1}, /// [7] - 0, 3, 7, 8, 9
    {0, 0, 0, 0, 0, 0, 0, 0, 1, 0}, /// [8] - 8
    {0, 0, 0, 0, 0, 0, 0, 0, 1, 1}, /// [9] - 8, 9
};

int n;                  /// Độ dài của số nhận vào
vector<int> v;          /// vector chứa các chữ số
vector<vector<ll> > f;  /// vector 2 chiều quy hoạch động
/// hàm magic(i, ign)
/// tại vị trí (i) của số biểu diễn bởi vector (v)
/// đếm số cách mà xây dựng được số có (ign) = true
ll magic(int i = 0, int ign = false) /// O(n * 2 * 9)
{
    /// Nếu đã duyệt hết vector
    if (i >= n) return ign;

    /// Dùng con trỏ để tiện tính toán
    ll &res = f[i][ign];
    if (res != -1) return res; /// Nếu đã được tính trước đó
    else res = 0;              /// Ngược lại thì reset giá trị

    /// Chúng ta chỉ chọn những chữ số có thể chuyển đổi được
    int lim = ign ? 0 : v[i];
    for (int d = 9; d >= lim; --d)
        if (G[v[i]][d] == true)
            res += magic(i + 1, ign || (d > lim));

    /// Đừng quên trả về kết quả :D
    return res;
}

void solve2()
{
    /// Biểu diễn số dưới dạng xâu
    string s;
    cin >> s;

    /// Dùng vector (v) độ dài (n) để lưu trữ các chữ số
    n = s.size();
    for (char c : s) v.pb(c - '0');

    /// Khởi tạo -1 tức là chưa được tính trước đó
    f.assign(n + 1, vector<ll>(2, -1));
    cout << magic();
}

~\color{green}{\text{Code tham khảo }}~: Quy hoạch động chữ số, Xử lí trực tiếp

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

             ///   0  1  2  3  4  5  6  7  8  9
vector<int> csl = {6, 2, 5, 5, 4, 5, 6, 3, 7, 6}; /// Đếm số vạch led bật
vector<int> ctw = {2, 7, 2, 3, 3, 4, 2, 5, 1, 2}; /// Số cách chọn chữ số tại vị trí i
vector<int> clw = {0, 1, 0, 0, 0, 0, 0, 2, 0, 1}; /// Số cách chọn chữ số bé hơn tại vị trí i
inline bool isDig(char c) { return '0' <= c && c <= '9'; } /// isDigit(char) ?
void solve1() /// O(log10 n)
{
    char c;
    while (c = getchar(), !isDig(c)); /// Bỏ các kí tự không phải chữ số

    int res = 0;
    do res += csl[c - '0']; 
    while (isDig(c = getchar())); /// Nhận chữ số (c) tiếp theo

    cout << res;
}

void solve2() /// O(log10 n)
{
    char c;
    while (c = getchar(), !isDig(c)); /// Bỏ các kí tự không phải chữ số

    ll res = 1;
    do res = res * ctw[c - '0'] - clw[c - '0']; 
    while (isDig(c = getchar()));  /// Nhận chữ số (c) tiếp theo

    cout << res - 1; /// Bỏ qua trường hợp bằng nhau
}

Bình luận

Hãy đọc nội quy trước khi bình luận.


Không có bình luận tại thời điểm này.