Editorial for Khảo cổ học (THTA Sơn Trà 2023)

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.

Solution 1: DP digit

Solution 2: Toán

Để tính tổng các chữ số của các số nguyên từ 1 đến N, ta thực hiện chia thành các khoảng có thể tính tổng được.
Cụ thể: tách dần từ hàng có đơn vị cao nhất về hàng đơn vị thấp nhất:
Ví dụ với N = 5243, sẽ được chia thành các đoạn: (kí hiệu(1->a) là tổng các chữ số từ 1 tới a)

C++

(1->5243)
= (1->5000) + (5001->5200) + (5201->5240) + (5241->5243)
=             (1->5000)

 + 5*200     + (1->200)
 + (5+2)*40  + (1->40)
 + (5+2+4)*3 + (1->3)
=
              (1->4)*1000 + (1->999) * 5 + 5
 + 5*200     + (1->1)*100 + (1->99)  * 2 + 2
 + (5+2)*40  + (1->3)*10  + (1->9)   * 4 + 4
 + (5+2+4)*3 + (1->2)                    + 3

Việc còn lại là tính các tổng có dạng:
- Tổng của i chữ số đầu tiên của n
- (1->x) với x <= 9
- (1->10^i-1) (i chữ số 9)

Có thể dùng 2 mảng tiền xử lí như sau:

C++

void precalc() {
    sum[0] = 0; // sum[i]: tổng từ 1 đến i với i <= 9
    for (int i = 1; i <= 9; ++i)
        sum[i] = sum[i - 1] + i;

    // thay vì nhập số nguyên n thì sẽ nhập xâu kí tự s để dễ tính toán
    n = s.size();
    pre[0] = 0; // pre[i]: tổng của i chữ số đầu tiên của s
    for (int i = 0; i < n; ++i)
        pre[i] = pre[i - 1] + s[i - 1] - '0';

    s9[0] = 0; // s9[i]: tổng từ 1 đến 10^i - 1 (số có i chữ số 9)
    for (int i = 1, e = 1; i <= n; ++i, e *= 10)
        s9[i] = s9[i - 1] * 10 + e * 45;
}

Comments

There are no comments at the moment.