Editorial for Một bài tập thú vị về chữ số
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.
Subtask \(1\): \(1 \le l \le r \le 10^6\)
Hint
- Ta sẽ có thể tính trước kết quả.
Hướng tiếp cận
- Ta sẽ duyệt qua các số từ \(1\) tới \(10^6\). Với mỗi số, ta sẽ đếm số lần xuất hiện của các chữ số từ \(0\) tới \(9\). Mỗi lần xuất hiện của chữ số \(k\), ta sẽ lưu vào mảng thứ \(k\) (vậy sẽ có \(10\) mảng).
- Với mỗi câu hỏi, ta sẽ in kết quả trong \(O(1)\).
- Độ phức tạp của ý tưởng trên là \(O(10^6 + t)\).
Subtask \(2\): Không giới hạn gì thêm
Hint
- Chỉ có làm thì mới có ăn, không làm mà đòi có ăn thì ăn \(...\)
Hướng tiếp cận
- Dp-digit hoặc toán.
Comments