Hướng dẫn cho Khảo cổ học (THTA Sơn Trà 2023)

Chỉ sử dụng khi thực sự cần thiết như một cách tôn trọng tác giả và người viết hướng dẫn này.

Chép code từ bài hướng dẫn để nộp bài là hành vi có thể dẫn đến khóa tài khoản.

Authors: cuberlong

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;
}

Bình luận

Không có bình luận nào.