Chọn đội tuyển HSG quốc gia Hải Phòng 2025-2026

THÀNH PHỐ HẢI PHÒNG Năm học 2025 - 2026

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

Bài 1

Cho n điểm có tọa độ x[i], y[i] trên mặt phẳng hai chiều, và q truy vấn, mỗi truy vấn là một hình chữ nhật trên mặt phẳng, có tọa độ từ ô x1, y1 đến x2, y2. Đếm số điểm trong n điểm nằm trên một trong các cạnh của hình chữ nhật.

Subtask 1: n, m ≤ 10³, x, y ≤ 1000
Subtask 2: n, m ≤ 10⁵, x, y ≤ 1000
Subtask 3: n, m ≤ 10⁵, x, y ≤ 10⁹

Bài 2

Cho đồ thị vô hướng n đỉnh, m cạnh, mỗi cạnh có độ nguy hiểm p[i] và trọng số là w[i].

Tìm ra đường đi có độ nguy hiểm lớn nhất là nhỏ nhất từ 1 đến n, nếu có nhiều đường đi như vậy thì tìm ra đường đi có tổng trọng số nhỏ nhất.

Subtask 1: n ≤ 6, m ≤ 15
Subtask 2: p = 1 với mọi cạnh
Subtask 3: w = 1 với mọi cạnh
Subtask 4: n, m ≤ 10⁴
Subtask 5: n, m ≤ 10⁵, p ≤ 10¹⁸, w ≤ 10¹²

Bài 3

Cho dãy n domino có hai giá trị a[i] và b[i] trên nó, và k truy vấn, mỗi truy vấn có dạng một số nguyên t[j], ta thực hiện thao tác: xét tất cả các domino, nếu domino có a[i] ≤ t[j], thì lật ngược domino lại (swap(a[i], b[i])).

Sau khi thực hiện hết tất cả k truy vấn, cần tính tổng các a[i] từ 1 đến n.

Subtask 1: n, k ≤ 500
Subtask 2: n, k ≤ 10⁴, trong k thao tác, không quá 100 số khác nhau
Subtask 3: Dãy t có giá trị không giảm
Subtask 4: n, k ≤ 10⁵, a[i], b[i], t[i] ≤ 10⁹.

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