Tài liệu trích xuất nội dung trang 1 từ đề thi chính thức chọn đội tuyển học sinh giỏi THPT cấp tỉnh môn Tin học (Buổi thi thứ hai) năm học 2026 - 2027 của Sở GD&ĐT Cà Mau. Đề thi gồm các bài toán cấu trúc dữ liệu và giải thuật nâng cao, bài 1 là Đồ thị sắc màu (KOLORING).
TỔNG QUAN ĐỀ THI
| Câu | Tên bài | File chương trình | File dữ liệu vào | File kết quả |
|---|---|---|---|---|
| Câu 4 | Đồ thị sắc màu | KOLORING.* | KOLORING.INP | KOLORING.OUT |
| Câu 5 | Giá thuê phòng | ARITHPR.* | ARITHPR.INP | ARITHPR.OUT |
| Câu 6 | Phân hoạch xor | XORPART.* | XORPART.INP | XORPART.OUT |
Dấu * được thay thế bởi PY hoặc CPP của ngôn ngữ lập trình sử dụng tương ứng là Python hoặc C++.
NỘI DUNG NGUYÊN BẢN (TRANG 1)
Câu 4 (7 điểm). Đồ thị sắc màu [KOLORING]
Cho một đa đồ thị vô hướng có \(n\) đỉnh, ban đầu chưa có cạnh nào. Mỗi cạnh được gắn một màu là một số nguyên từ \(1\) đến \(10^5\).
Có \(q\) truy vấn, mỗi truy vấn thuộc một trong hai loại sau:
- + v u c: thêm cạnh nối hai đỉnh \(v, u\) với màu \(c\). Bảo đảm trước đó chưa tồn tại cạnh màu \(c\) giữa \(v\) và \(u\).
- - v u c: xóa cạnh nối hai đỉnh \(v, u\) với màu \(c\). Bảo đảm cạnh đó đang tồn tại.
Một màu \(c\) được gọi là đẹp nếu với mọi đỉnh, số cạnh màu \(c\) kề với đỉnh đó không vượt quá 1.
Độ đẹp của một màu đẹp được định nghĩa là số cạnh có màu đó trong đồ thị.
Sau mỗi truy vấn, hãy tính tổng độ đẹp của tất cả các màu đẹp.
Dữ liệu (nhập vào từ file văn bản KOLORING.INP)
- Dòng 1: hai số nguyên \(n, q\) — số đỉnh và số truy vấn (\(2 \le n \le 10^5, 1 \le q \le 10^5\))
- \(q\) dòng tiếp theo, mỗi dòng mô tả một truy vấn theo một trong hai dạng trên
- Với mọi truy vấn: \(1 \le v, u \le n, v \ne u, 1 \le c \le 10^5\)
Kết quả (ghi ra file văn bản KOLORING.OUT)
- Gồm \(q\) dòng, dòng thứ \(i\) in ra tổng độ đẹp của đồ thị sau truy vấn thứ \(i\).
Subtasks
| # | Điểm | Ràng buộc bổ sung |
|---|---|---|
| 1 | 10% | \(n, q \le 100\) |
| 2 | 20% | \(n, q \le 1000\) |
| 3 | 10% | \(n, q \le 10000\) |
| 4 | 60% | Không có ràng buộc bổ sung |
Xem và tải tài liệu đầy đủ
Tài liệu trích xuất nội dung trang 1 từ đề thi chính thức chọn đội tuyển học sinh giỏi THPT cấp tỉnh môn Tin học (Buổi thi thứ hai) năm học 2026 - 2027 của Sở GD&ĐT Cà Mau. Đề thi gồm các bài toán cấu trúc dữ liệu và giải thuật nâng cao, bài 1 l…
Xem thêm »