Editorial for Duyên Hải 2020 - Lớp 10 - Bài 1 - LED
Remember to use this editorial only when stuck, and not to copy-paste code from it. Please be respectful to the problem author and editorialist.
Submitting an official solution before solving the problem yourself is a bannable offence.
Submitting an official solution before solving the problem yourself is a bannable offence.
Author:
~\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
}
Comments