Kỳ thi: NOI Trung Quốc 2026 - Ngày 2
Tóm tắt: Kỳ thi Ngày 2 của CCF NOI 2026 mang đến bộ ba bài toán điển hình về tư duy biến đổi điều kiện: từ kỹ thuật chặt nhị phân kết hợp quy hoạch động kiểm tra tính khả thi, bài toán cấu trúc dữ liệu truy vấn quan hệ kề trên cây qua mã Prüfer, đến bài toán đếm cây nâng cao bằng quy hoạch động trên cây kết hợp bao hàm loại trừ.

Ở NOI Trung Quốc 2026 - Median, bài toán yêu cầu chia dãy thành \(k\) đoạn liên tiếp sao cho trung vị của các trung vị từng đoạn đạt giá trị lớn nhất. Thay vì tối ưu trực tiếp giá trị thực, hướng tiếp cận trực tiếp là chặt nhị phân đáp án \(x\), sau đó gán mỗi phần tử bằng \(+1\) nếu \(a_i \ge x\) và \(-1\) nếu ngược lại. Với \(k \le 5\), bài toán kiểm tra quy về quy hoạch động theo số đoạn đã phân chia cùng tổng giá trị dấu; khi \(k\) lớn, tính khả thi có thể xác định nhanh qua vị trí và khoảng cách giữa các phần tử nhận giá trị \(1\).

Chuyển sang NOI Trung Quốc 2026 - Kapok, mỗi đoạn con \([l, r)\) trong dãy ký ức mô tả một cây thông qua mã Prüfer, và ta cần trả lời \(m\) truy vấn kiểm tra hai đỉnh \(x, y\) có kề nhau hay không. Do mỗi truy vấn gắn với một đoạn độ dài thay đổi và phép giới hạn giá trị \(\min(a_i, k-1)\), việc xử lý độc lập từng truy vấn rất tốn kém. Cách giải quyết hiệu quả là phân nhóm truy vấn theo thuật toán Mo kết hợp mảng lưu vị trí xuất hiện gần nhất và chia khối để duy trì thông tin dựng cạnh kề của cây.

Bài toán đòi hỏi kỹ thuật đại số và tổ hợp cao nhất là NOI Trung Quốc 2026 - Rainbow Tree, yêu cầu đếm cấu hình trên cây có gốc gồm \(n \le 200\) đỉnh lấy dư theo \(998244353\). Hướng xử lý dựa trên quy hoạch động trên cây với các mảng trạng thái \(dp[x][i][j]\) theo kích thước cây con tại đỉnh \(x\). Khi gộp các cây con, ta dùng phép nhân chập kết hợp kỹ thuật bao hàm loại trừ để loại bỏ các trạng thái trùng lặp hoặc không hợp lệ.

Thứ tự tiếp cận hợp lý nhất là bắt đầu từ NOI Trung Quốc 2026 - Median để rèn luyện kỹ năng đưa bài toán tìm kiếm về bài toán kiểm tra tính khả thi, sau đó đọc NOI Trung Quốc 2026 - Kapok trước khi thử sức với bài toán đếm NOI Trung Quốc 2026 - Rainbow Tree.