Chọn đội tuyển HSG quốc gia Ninh Bình 2025-2026 (ngày 2)

TỈNH NINH BÌNH ĐỀ GÕ LẠI

KỲ THI CHỌN ĐỘI TUYỂN DỰ THI HỌC SINH GIỎI QUỐC GIA THPT Năm học 2025 - 2026
Môn thi: Tin học - Ngày thi thứ hai

Bài 4. Dãy số đặc biệt

Hạn chế thời gian: 1 giây
Hạn chế bộ nhớ: 512 MB

Hoàng Hải muốn trở thành học sinh xuất sắc của lớp chuyên Tin học nên cậu cần luyện tập nhiều bài tập lập trình. Trong quá trình học dạng số học, cậu gặp một bài toán rất hay như sau:

Một dãy số A được gọi là đặc biệt nếu thỏa mãn các điều kiện sau:

Giá trị tất cả các phần tử của dãy A thuộc tập hợp {0, 1, …, n}, với n là số tự nhiên.
Dãy A gồm ít nhất 1 phần tử. Nếu A có từ 2 phần tử trở lên thì các phần tử từ phần tử thứ 2 trở đi phải thỏa mãn: giá trị của mỗi phần tử bằng giá trị của phần tử liền trước nó cộng với một số nguyên dương không đổi d.

Yêu cầu: Cho số tự nhiên n, với mỗi số n hãy đếm xem có bao nhiêu dãy số đặc biệt.

Dữ liệu: Dữ liệu vào từ file văn bản BAI4.INP:

Dòng đầu chứa một số nguyên q (1 ≤ q ≤ 10) là số lượng số tự nhiên n.
Mỗi dòng trong số q dòng tiếp theo chứa duy nhất một số nguyên n (1 ≤ n ≤ 10¹²).

Kết quả: Ghi ra file văn bản BAI4.OUT:

In ra q dòng, mỗi dòng một số nguyên là câu trả lời tương ứng.

Hạn chế:

40% số test ứng với 40% số điểm của bài có n ≤ 10³.
20% số test tiếp theo ứng với 20% số điểm của bài có n ≤ 10⁶.
40% số test còn lại ứng với 40% số điểm của bài không có ràng buộc gì thêm.

Ví dụ:

BAI4.INP	BAI4.OUT
`6` `2` `4` `1` `5` `7` `8`	`7` `22` `3` `33` `65` `86`

Giải thích: Với n = 2, ta có 7 dãy số đặc biệt: {0}, {1}, {2}, {0, 1}, {1, 2}, {0, 2}, {0, 1, 2}.

Bài 5. Gán trọng số

Hạn chế thời gian: 1 giây
Hạn chế bộ nhớ: 512 MB

Bạn được cho một cây (đồ thị vô hướng liên thông không có chu trình) gồm n đỉnh đánh số 1, 2, …, n và một dãy số nguyên dương a₁, a₂, …, aₙ.

Nhiệm vụ của bạn là tìm một hoán vị p₁, p₂, …, pₙ của {1, 2, …, n}. Sau đó với mỗi đỉnh i gán giá trị a_(pᵢ) cho đỉnh này.

Giá trị của một đường đi giữa hai đỉnh u và v được tính bằng tổng các giá trị đã gán cho các đỉnh trên đường đi này (gồm cả đỉnh u và v).

Yêu cầu: Tính giá trị lớn nhất của tổng giá trị các con đường từ một đỉnh lá đến một đỉnh lá khác (đỉnh lá là đỉnh chỉ nối duy nhất với một đỉnh khác). Do giá trị này có thể rất lớn nên chỉ cần lấy phần dư của nó khi chia cho 10⁹ + 7.

Dữ liệu: Dữ liệu vào từ file văn bản BAI5.INP.

Dòng đầu tiên chứa số nguyên dương T (T ≤ 1000) biểu diễn số lượng bộ dữ liệu.
Tiếp theo là T nhóm dòng, mỗi nhóm gồm n + 1 dòng mô tả một bộ dữ liệu có cấu trúc như sau:
- Dòng đầu tiên chứa số nguyên dương n (3 ≤ n ≤ 3 × 10⁵).
- Dòng thứ hai chứa n số nguyên dương a₁, a₂, …, aₙ (aᵢ ≤ 10⁹; 1 ≤ i ≤ n).
- Mỗi dòng trong n − 1 dòng cuối cùng chứa hai số nguyên dương u, v thể hiện có một cạnh nối giữa hai đỉnh u, v (1 ≤ u ≤ n; u ≠ v).
Các số trên cùng một dòng cách nhau bởi dấu cách.
Tổng giá trị n trong tất cả các bộ dữ liệu không vượt quá 5 × 10⁵.

Kết quả: Ghi ra file văn bản BAI5.OUT.

Với mỗi bộ dữ liệu in ra trên một dòng một số nguyên duy nhất là kết quả tìm được.

Hạn chế:

20% số test ứng với 20% số điểm của bài có T ≤ 10, n ≤ 10.
40% số test tiếp theo ứng với 40% số điểm của bài có T ≤ 10, n ≤ 1000.
40% số test còn lại không có ràng buộc bổ sung.

Ví dụ:

BAI5.INP	BAI5.OUT
`2` `4` `1 2 3 4` `1 2` `2 3` `2 4` `5` `1 2 3 4 5` `1 2` `2 3` `3 4` `4 5`	`24` `15`

Giải thích: Với test 1, hoán vị p thỏa mãn là: (1, 4, 3, 2); trọng số được gán cho các đỉnh trên cây (đỉnh 2 nối với các lá 1, 3, 4):

Giá trị đường đi từ đỉnh lá 1 đến đỉnh lá 3 là 1 + 4 + 3 = 8.
Giá trị đường đi từ đỉnh lá 1 đến đỉnh lá 4 là 1 + 4 + 2 = 7.
Giá trị đường đi từ đỉnh lá 3 đến đỉnh lá 4 là 3 + 4 + 2 = 9.

Tổng giá trị các đường đi là: 8 + 7 + 9 = 24.

Bài 6. Truy vấn

Hạn chế thời gian: 1 giây
Hạn chế bộ nhớ: 512 MB

Cho dãy số gồm n số nguyên dương a₁, a₂, …, aₙ. Độ đẹp của một đoạn từ vị trí L đến vị trí R được tính bằng công thức:

max_{L ≤ u ≤ R} ((aᵤ − a_L)(a_R − aᵤ))

Có tất cả m truy vấn. Mỗi truy vấn thuộc một trong hai loại sau:

1 u x: Gán giá trị aᵤ = x (1 ≤ u ≤ n).
2 L R: Tính độ đẹp của đoạn từ vị trí L đến vị trí R (1 ≤ L ≤ R ≤ n).

Yêu cầu: Với mỗi truy vấn loại 2, hãy tính độ đẹp của đoạn [L, R] tương ứng.

Dữ liệu: Dữ liệu vào từ file văn bản BAI6.INP:

Dòng đầu tiên chứa hai số nguyên dương n, m (1 ≤ n, m ≤ 5 × 10⁴).
Dòng thứ hai chứa n số nguyên dương a₁, a₂, …, aₙ (1 ≤ aᵢ ≤ 10⁹, 1 ≤ i ≤ n).
Mỗi dòng tiếp theo mô tả một truy vấn:
- Với truy vấn loại 1 u x: 1 ≤ u ≤ n, 1 ≤ x ≤ 10⁹.
- Với truy vấn loại 2 L R: 1 ≤ L ≤ R ≤ n.
Các số trên cùng một dòng cách nhau bởi dấu cách.
Dữ liệu đảm bảo có ít nhất một truy vấn loại 2 L R.

Kết quả: Ghi ra file văn bản BAI6.OUT:

Với mỗi truy vấn loại 2 L R, in ra một số nguyên trên một dòng là độ đẹp của đoạn [L, R] tương ứng.

Hạn chế:

20% số test ứng với 20% số điểm của bài có 1 ≤ n, m ≤ 5000.
40% số test tiếp theo ứng với 40% số điểm của bài thỏa mãn điều kiện aᵢ ≤ 100 với 1 ≤ i ≤ n.
40% số test còn lại không có ràng buộc bổ sung.

Ví dụ:

BAI6.INP	BAI6.OUT
`4 3` `2 1 4 3` `2 1 4` `1 2 3` `2 1 3`	`0` `1`

Giải thích:

Ban đầu dãy số là: {2, 1, 4, 3}. Với truy vấn 2 1 4: độ đẹp của đoạn [1, 4] là max_1≤i≤4 {(a₁ − aᵢ)(a₄ − aᵢ)} = 0.
Với truy vấn 1 2 3: gán giá trị a₂ = 3. Dãy số trở thành: {2, 3, 4, 3}.
Với truy vấn 2 1 3: độ đẹp của đoạn [1, 3] là max_1≤i≤3 {(a₁ − aᵢ)(a₃ − aᵢ)} = 1.

Th.S Trần Huy Phúc

Kỹ sư phần mềm @Adnovum & Bumbii Academy

Học Tiếng Anh với Bumbii English