Hướng dẫn cho Series ℍ𝔾𝔹ℂ𝕡𝕡_'s - 2026 - Contest #1 - Bài dễ

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.

Tóm tắt đề bài

Cho một tháp ô vuông bậc \(n\) có hình dạng giống tam giác cân. Các hàng tính từ trên xuống dưới có số ô vuông lần lượt là \(1, 3, 5, \dots, 2n-1\). Hãy đếm tổng số hình vuông (kích thước \(1 \times 1, 2 \times 2, \dots\)) có thể tạo thành từ các ô vuông trong tháp. Kết quả được lấy dư cho \(10^9+7\).

Phân tích

  • Cấu trúc tháp:
    • Hàng 1: 1 ô vuông.
    • Hàng 2: 3 ô vuông.
    • ...
    • Hàng \(i\): \(2i-1\) ô vuông.
    • Hàng \(n\): \(2n-1\) ô vuông.
  • Quan sát: Các hàng được xếp chồng lên nhau và căn giữa. Điều này có nghĩa là hàng \(i\) sẽ dư ra về mỗi bên 1 ô so với hàng \(i-1\).
  • Điều kiện để có hình vuông \(k \times k\): Một hình vuông kích thước \(k \times k\) sẽ chiếm \(k\) hàng liên tiếp và \(k\) cột liên tiếp.
  • Ràng buộc: \(n \le 10^7\). Với \(n\) lớn như vậy, ta cần một thuật toán có độ phức tạp \(O(n)\) hoặc công thức toán học.

Cách làm đơn giản (Brute Force)

Ý tưởng

Duyệt qua từng kích thước hình vuông \(k\) từ \(1\) đến \(n\). Với mỗi \(k\), duyệt qua từng hàng \(i\) (hàng bắt đầu của hình vuông \(k \times k\)). Kiểm tra xem tại hàng đó và \(k-1\) hàng tiếp theo, có đủ độ rộng để chứa hình vuông \(k \times k\) hay không.

Độ phức tạp

  • Thời gian: \(O(n^2)\)
  • Đánh giá: Phù hợp cho \(n \le 1000\) (Subtask 1).

Code Brute Force

C++
C++
#include <bits/stdc++.h>
using namespace std;

const int MOD = 1e9 + 7;

int main() {
    int n;
    cin >> n;
    long long total_squares = 0;
    // Duyệt qua kích thước hình vuông k x k
    for (int k = 1; k <= n; k++) {
        // Duyệt qua hàng bắt đầu i của hình vuông
        for (int i = 1; i <= n - k + 1; i++) {
            // Hàng hẹp nhất trong k hàng liên tiếp (i, i+1, ..., i+k-1) là hàng i
            // Số ô vuông ở hàng i là 2*i - 1
            // Tuy nhiên, hình vuông k x k cần k hàng liên tiếp.
            // Để hình vuông k x k tồn tại bắt đầu từ hàng i, 
            // thì hàng i phải có đủ độ rộng để "phủ" được k ô ở các hàng dưới.
            // Do tháp mở rộng dần xuống dưới, ta chỉ cần quan tâm hàng i.
            // Số vị trí đặt hình vuông k x k bắt đầu từ hàng i là:
            // (Số ô hàng i) - (k - 1) * 2 (do mỗi hàng trên hụt 1 ô mỗi bên so với hàng dưới)
            // Cụ thể: số vị trí = (2*i - 1) - (k - 1) + 1 nếu tính theo cách khác.
            // Cách tính đúng: Số lượng hình vuông k x k bắt đầu tại hàng i là (2*i - k)
            if (2 * i - k > 0) {
                total_squares = (total_squares + (2 * i - k)) % MOD;
            }
        }
    }
    cout << total_squares << endl;
    return 0;
}
Python
Python
n = int(input())
MOD = 10**9 + 7
total_squares = 0
for k in range(1, n + 1):
    for i in range(1, n - k + 2):
        count = 2 * i - k
        if count > 0:
            total_squares = (total_squares + count) % MOD
print(total_squares)

Hướng giải quyết (Tối ưu)

Nhận xét

Để đếm số hình vuông kích thước \(k \times k\), ta xét các hình vuông có cạnh dưới nằm ở hàng \(j\) (\(k \le j \le n\)).

  1. Một hình vuông \(k \times k\) kết thúc tại hàng \(j\) sẽ chiếm các hàng từ \(j-k+1\) đến \(j\).
  2. Để hình vuông này tồn tại, hàng trên cùng của nó (hàng \(j-k+1\)) phải có ít nhất \(k\) ô vuông.
  3. Số ô vuông tại hàng \(j-k+1\) là \(2(j-k+1) - 1\).

  4. Tuy nhiên, các hình vuông phải "khớp" với cấu trúc tháp. Số lượng hình vuông \(k \times k\) nằm trọn trong các hàng từ \(j-k+1\) đến \(j\) là:

    \[(2 \times \text{số ô hàng trên cùng}) - k + 1 \text{ (không đúng)}\]

    Thực tế, số lượng hình vuông \(k \times k\) có cạnh dưới nằm ở hàng \(j\) chính là:

    \[ (2 \times (j-k+1) - 1) - (k - 1) = 2j - 2k + 2 - 1 - k + 1 = 2j - 3k + 2 \]

    Nhưng điều kiện là hàng trên cùng phải đủ rộng. Một cách tiếp cận dễ hơn là cố định kích thước \(k\) và đếm xem có bao nhiêu vị trí đặt.

Công thức tối ưu

Với mỗi kích thước \(k\) (\(1 \le k \le n\)):

  • Hình vuông \(k \times k\) có thể bắt đầu từ hàng \(i\) nếu hàng \(i\) có đủ độ rộng để chứa phần đỉnh của hình vuông đó.
  • Số lượng hình vuông \(k \times k\) bắt đầu tại hàng \(i\) là \(2i - k\) (với \(2i - k > 0\)).
  • Điều kiện \(2i - k > 0 \Rightarrow i > k/2 \Rightarrow i \ge \lfloor \frac{k+2}{2} \rfloor\).
  • Hàng \(i\) có thể chạy từ \(L = \lfloor \frac{k+2}{2} \rfloor\) đến \(R = n - k + 1\).
  • Tổng số hình vuông kích thước \(k\) là tổng của cấp số cộng với các số hạng \((2i - k)\) khi \(i\) chạy từ \(L\) đến \(R\).
    • Số hạng đầu: \(u_1 = 2L - k\)
    • Số hạng cuối: \(u_m = 2R - k\)
    • Số số hạng: \(m = R - L + 1\)
    • Tổng: \(S_k = \frac{(u_1 + u_m) \times m}{2}\)

Ta duyệt \(k\) từ \(1\) đến \(n\), tính \(S_k\) và cộng dồn vào kết quả.

Độ phức tạp

  • Thời gian: \(O(n)\) - Duyệt một vòng lặp từ \(1\) đến \(n\).
  • Bộ nhớ: \(O(1)\) - Chỉ sử dụng các biến đơn giản.

Code tham khảo

C++
C++
#include <bits/stdc++.h>
using namespace std;

int main() {
    // Tối ưu nhập xuất
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);

    int n;
    cin >> n;
    long long MOD = 1e9 + 7;
    long long total_ans = 0;

    for (int k = 1; k <= n; ++k) {
        // L là hàng nhỏ nhất mà hình vuông k*k có thể bắt đầu
        long long L = (k + 2) / 2;
        // R là hàng lớn nhất mà hình vuông k*k có thể bắt đầu
        long long R = n - k + 1;

        if (L <= R) {
            long long num_terms = R - L + 1;
            long long first_term = 2 * L - k;
            long long last_term = 2 * R - k;

            // Tổng cấp số cộng: (đầu + cuối) * số số hạng / 2
            long long sum_k = (first_term + last_term) * num_terms / 2;
            total_ans = (total_ans + sum_k) % MOD;
        }
    }

    cout << total_ans << endl;
    return 0;
}
Python
Python
import sys

def solve():
    # Đọc n từ đầu vào
    try:
        line = sys.stdin.readline()
        if not line:
            return
        n = int(line.strip())
    except EOFError:
        return

    MOD = 10**9 + 7
    total_ans = 0

    for k in range(1, n + 1):
        # L là hàng nhỏ nhất mà hình vuông k*k có thể bắt đầu
        L = (k + 2) // 2
        # R là hàng lớn nhất mà hình vuông k*k có thể bắt đầu
        R = n - k + 1

        if L <= R:
            num_terms = R - L + 1
            first_term = 2 * L - k
            last_term = 2 * R - k

            # Tổng cấp số cộng: (đầu + cuối) * số số hạng / 2
            sum_k = (first_term + last_term) * num_terms // 2
            total_ans = (total_ans + sum_k) % MOD

    print(total_ans)

if __name__ == "__main__":
    solve()

Bình luận

Mới nhất
Tải bình luận...

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