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:

  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ờ

  Hint 4

  • Query 2:

  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

  Hint 5

  • Query 2: Multiplicative Formula: res = res * ctw[d] - clw[d]

  ---

  Reference AC code | \(O(log_{10} n)\) + \(O(log_{10} n)\) time | \(O(1)\) auxiliary space | Brute-forces + DP_digit | Online Solving Implementation

  C++

               ///   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)
  {
      int res = 0;
      char c;
      while (c = getchar(), !isDig(c));
      do res += csl[c - '0']; while (isDig(c = getchar()));
      cout << res;
  }
  
  void solve2() /// O(log10 n)
  {
      ll res = 1;
      char c;
      while (c = getchar(), !isDig(c));
      do res = res * ctw[c - '0'] - clw[c - '0']; while (isDig(c = getchar()));
      cout << res - 1; /// Bỏ qua trường hợp bằng nhau
  }
  

5 bình luận nữa