Bình luận

• 
  

  0

  SPyofgame    11:04 p.m. 12 Tháng 6, 2020 ← chỉnh sửa 4 →

  ---

  Spoiler Alert

  ---

  Hint 1

  • Query 1: Tính tổng vạch led bật mỗi chữ số từ số n

  • Query 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

  Hint 2

  • Query 1: Ta có thể tiền xử lí 10 chữ số 0..9 xem nó có bao nhiêu vạch led bật để tiện

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

  Hint 3

  • Query 1: vector<int> csl = {6, 2, 5, 5, 4, 5, 6, 3, 7, 6}; /// Count set-led

  • Query 2: 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

  Hint 4

  • Query 2:

  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

  Hint 5

  • Query 2: Recursive Formula: res = res + magic(index + 1, isGreater || (nextd > lower_limit))

  ---

  Reference AC code | \(O(log_{10} n)\) + \(O(log_{10} n * 2 * 7)\) time | \(O(1)\) auxiliary space | Brute-forces + DP_digit | Adjacency List Implementation

  C++

  /// 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();
  }
  

  Reference AC code | \(O(log_{10} n)\) + \(O(log_{10} n * 2 * 7)\) time | \(O(1)\) auxiliary space | Brute-forces + DP_digit

  C++

  /// 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();
  }
  

4 bình luận nữa