NOI Trung Quốc 2026 - Ngày 2

Bộ đề bài

Trở lại kỳ thi
# Bài tập Điểm Thời gian: Giới hạn bộ nhớ
1 NOI Trung Quốc 2026 - Median 100 (p) 1.0s 1G
2 NOI Trung Quốc 2026 - Kapok 100 (p) 2.0s 1G
3 NOI Trung Quốc 2026 - Rainbow Tree 100 (p) 1.0s 1G

1. NOI Trung Quốc 2026 - Median

Điểm: 100 (p) Thời gian: 1.0s Bộ nhớ: 1G Input: bàn phím Output: màn hình

Với một đa tập \(S=\{x_0,x_1,\ldots,x_{m-1}\}\), sắp xếp các phần tử theo thứ tự không tăng:

\[ y_0\ge y_1\ge\cdots\ge y_{m-1}. \]

Trong bài này, trung vị được định nghĩa là phần tử lớn thứ \(\lceil m/2\rceil\):

\[ \operatorname{Median}(S)=y_{\lceil m/2\rceil-1}. \]

Lưu ý rằng với số phần tử chẵn, định nghĩa này có thể khác định nghĩa trung vị thường gặp.

Cho dãy \([a_0,a_1,\ldots,a_{n-1}]\) và số nguyên dương \(k\le n\). Chọn

\[ 0<b_1<b_2<\cdots<b_{k-1}<n \]

để chia dãy thành đúng \(k\) đoạn không rỗng \([0,b_1),[b_1,b_2),\ldots,[b_{k-1},n)\). Đặt \(b_0=0,b_k=n\) và

\[ c_i=\operatorname{Median}(\{a_{b_i},a_{b_i+1},\ldots,a_{b_{i+1}-1}\}). \]

Độ cân bằng của phép chia là \(\operatorname{Median}(\{c_0,c_1,\ldots,c_{k-1}\})\). Hãy tìm độ cân bằng lớn nhất trong mọi cách chia.

Yêu cầu cài đặt

Bạn không được cài đặt hàm main. Submission phải include median.h và cài đặt:

C++
void init(int c, int t);
  • c là số hiệu test; c=0 biểu thị dữ liệu mẫu.
  • t là số bộ dữ liệu trong test.
  • Bộ chấm gọi hàm đúng một lần khi chương trình bắt đầu.
C++
int median(int n, int k, std::vector<int> a);
  • Các tham số lần lượt là độ dài dãy, số đoạn và dãy đã cho.
  • Hàm phải trả về độ cân bằng lớn nhất.
  • Bộ chấm gọi hàm đúng t lần.

Khung khai báo:

C++
#include "median.h"

Dữ liệu bộ chấm

  • Dòng đầu chứa \(c,t\).
  • Với mỗi trong \(t\) bộ dữ liệu:
  • Dòng đầu chứa \(n,k\).
  • Dòng tiếp theo chứa \(a_0,a_1,\ldots,a_{n-1}\).

Grader ghi một dòng đáp án cho mỗi bộ dữ liệu.

Ràng buộc

Gọi \(N\) là tổng các giá trị \(n\) trong một test.

  • \(1\le t\le20\).
  • \(5\le n\le10^6\).
  • \(2\le k\le n\).
  • \(N\le10^6\).
  • \(1\le a_i\le n\).

Phân nhóm

Mỗi test có giá trị \(5\) điểm.

Test \(N\le\) \(n\le\) Điều kiện về \(k\) Tính chất
\(1,2\) \(40\) \(20\) \(k\le n\) Không
\(3\sim5\) \(800\) \(80\) \(k\le n\) A
\(6\) \(800\) \(80\) \(k\le n\) Không
\(7,8\) \(8000\) \(800\) \(k\le n\) A
\(9\) \(8000\) \(800\) \(k\le n\) Không
\(10\) \(2\cdot10^5\) \(2\cdot10^5\) \(k=2\) Không
\(11\) \(2\cdot10^5\) \(2\cdot10^5\) \(k=3\) Không
\(12,13\) \(2\cdot10^5\) \(2\cdot10^5\) \(k=5\) Không
\(14\) \(2\cdot10^5\) \(2\cdot10^5\) \(k\le10\) Không
\(15\) \(10^6\) \(10^6\) \(k\equiv0\pmod 2\) Không
\(16,17\) \(10^6\) \(10^6\) \(k>5\) Không
\(18\sim20\) \(10^6\) \(10^6\) \(k\le n\) Không

Tính chất A: \(a_i\le2\) với mọi \(0\le i<n\).

Ví dụ

Ví dụ

Input 
0 2
10 4
6 5 1 9 2 3 10 7 4 8
10 5
5 7 3 10 8 2 9 1 6 4
Output 
9
8

Trong bộ đầu, có thể chia thành \([6,5,1]\), \([9,2]\), \([3,10]\), \([7,4,8]\). Trung vị các đoạn là \(5,9,10,7\), nên độ cân bằng là \(9\).

Trong bộ thứ hai, có thể chia thành \([5,7]\), \([3,10]\), \([8,2]\), \([9,1]\), \([6,4]\). Trung vị các đoạn là \(7,10,8,9,6\), nên độ cân bằng là \(8\).

Nguồn

CCF NOI 2026 - Ngày 2, bài Median. Đề và dữ liệu chính thức được phát hành theo giấy phép CC BY-NC.

2. NOI Trung Quốc 2026 - Kapok

Điểm: 100 (p) Thời gian: 2.0s Bộ nhớ: 1G Input: bàn phím Output: màn hình

Ký ức của N được biểu diễn bằng một dãy \([a_0,a_1,\ldots,a_{n-1}]\).

Mỗi cây gạo trong ký ức là một cây vô hướng có nhãn. Một đoạn nửa kín \([l,r)\) của dãy mô tả một cây như sau:

  • Cây có \(k=r-l+2\) đỉnh, đánh số từ \(0\) đến \(k-1\).
  • Dãy
\[ [\min(a_l,k-1),\min(a_{l+1},k-1),\ldots,\min(a_{r-1},k-1)] \]

là mã Prüfer của cây.

Có \(m\) truy vấn. Truy vấn thứ \(i\) hỏi: trong cây được mô tả bởi đoạn \([l_i,r_i)\), hai đỉnh \(x_i,y_i\) có kề nhau hay không?

Yêu cầu cài đặt

Bạn không được cài đặt hàm main. Submission phải include kapok.h và cài đặt:

C++
std::vector<bool> kapok(
    int c, int n, int m,
    std::vector<int> a,
    std::vector<int> l,
    std::vector<int> r,
    std::vector<int> x,
    std::vector<int> y
);
  • c là số hiệu test; c=0 biểu thị dữ liệu mẫu.
  • n, m là độ dài dãy và số truy vấn.
  • a là dãy ký ức.
  • l, r là hai đầu đoạn của từng truy vấn.
  • x, y là hai đỉnh được hỏi trong từng truy vấn.
  • Hàm phải trả về một vector có đúng \(m\) phần tử. Phần tử thứ \(i\) là true khi \(x_i,y_i\) kề nhau và false trong trường hợp còn lại.
  • Bộ chấm gọi hàm đúng một lần cho mỗi test.

Khung khai báo:

C++
#include "kapok.h"

Dữ liệu bộ chấm

  • Dòng đầu chứa \(c,n,m\).
  • Dòng thứ hai chứa \(a_0,a_1,\ldots,a_{n-1}\).
  • Mỗi trong \(m\) dòng tiếp theo chứa \(l_i,r_i,x_i,y_i\).

Grader ghi \(m\) dòng, mỗi dòng là 1 nếu câu trả lời là true, ngược lại là 0.

Ràng buộc

  • \(1\le n,m\le2\cdot10^5\).
  • \(0\le a_i<n+2\).
  • \(0\le l_i\le r_i\le n\).
  • \(0\le x_i,y_i<r_i-l_i+2\).

Phân nhóm

Mỗi test có giá trị \(4\) điểm.

Test \(n,m\le\) Tính chất
\(1,2\) \(500\) Không
\(3\sim5\) \(5000\) Không
\(6,7\) \(2\cdot10^5\) \(a_i<10\) với mọi \(i\)
\(8,9\) \(2\cdot10^5\) \(a_i<10^3\) với mọi \(i\)
\(10,11\) \(2\cdot10^5\) \(x_i,y_i<10\) với mọi truy vấn
\(12,13\) \(2\cdot10^5\) \(x_i,y_i<10^3\) với mọi truy vấn
\(14\sim16\) \(2\cdot10^5\) A
\(17\sim19\) \(2\cdot10^5\) \(r_i=n\) với mọi truy vấn
\(20\sim22\) \(10^5\) Không
\(23\sim25\) \(2\cdot10^5\) Không

Tính chất A: sau khi đã cho \(l_i,r_i\), hai giá trị \(x_i,y_i\) được sinh độc lập và đều trên toàn bộ miền giá trị hợp lệ của chúng.

Nhắc lại về mã Prüfer

Với cây vô hướng \(T\) có các đỉnh \(0,1,\ldots,c-1\), \(c\ge2\), thực hiện \(c-2\) lần:

  1. Chọn lá có nhãn nhỏ nhất \(v_i\) trong cây hiện tại.
  2. Ghi lại nhãn \(p_i\) của đỉnh kề duy nhất với \(v_i\).
  3. Xóa \(v_i\) và cạnh duy nhất nối với nó.

Dãy \([p_0,p_1,\ldots,p_{c-3}]\) thu được là mã Prüfer của \(T\).

Ví dụ

Ví dụ

Input 
0 8 3
2 0 2 6 0 7 2 2
0 3 0 2
3 5 1 2
0 0 0 1
Output 
1
0
1
  • Đoạn \([0,3)\) cho mã Prüfer \([2,0,2]\) của cây có các cạnh \((1,2),(0,3),(0,2),(2,4)\), nên \(0,2\) kề nhau.
  • Đoạn \([3,5)\) cho mã \([3,0]\) của cây có các cạnh \((1,3),(0,2),(0,3)\), nên \(1,2\) không kề nhau.
  • Đoạn \([0,0)\) cho cây hai đỉnh với cạnh duy nhất \((0,1)\).

Nguồn

CCF NOI 2026 - Ngày 2, bài Kapok. Đề và dữ liệu chính thức được phát hành theo giấy phép CC BY-NC.

3. NOI Trung Quốc 2026 - Rainbow Tree

Điểm: 100 (p) Thời gian: 1.0s Bộ nhớ: 1G Input: bàn phím Output: màn hình

Có một cây có gốc gồm \(n\) đỉnh, đánh số từ \(0\) đến \(n-1\). Đỉnh \(0\) là gốc; với \(1\le i<n\), cha của đỉnh \(i\) là \(f_i\).

Mỗi đỉnh có thể mang một trong vô hạn màu. Với mỗi đỉnh \(i\), gọi \(c_i\) là số màu khác nhau xuất hiện trong cây con gốc \(i\). Độ rực rỡ của cây là dãy

\[ [c_0,c_1,\ldots,c_{n-1}]. \]

Độ rực rỡ chỉ phụ thuộc vào số màu phân biệt trong các cây con, không phụ thuộc vào tên cụ thể của các màu.

Hình 1: Một cách tô màu có độ rực rỡ \([3,2,1,2,1,1]\); các đỉnh \(0,1,5\) cùng màu, các đỉnh \(2,4\) cùng màu và đỉnh \(3\) mang màu còn lại.

Một quy luật được mô tả bằng tập \(S\subseteq\{1,2,\ldots,n-1\}\). Một cách tô màu thỏa quy luật \(S\) khi với mọi \(u\in S\), tồn tại một tổ tiên thực sự \(p\) của \(u\) có cùng màu với \(u\).

Gọi \(w_S\) là số dãy độ rực rỡ khác nhau có thể thu được từ những cách tô màu thỏa quy luật \(S\). Hai độ rực rỡ khác nhau khi ít nhất một vị trí trong hai dãy khác nhau.

Hãy tính

\[ \sum_{S\subseteq\{1,2,\ldots,n-1\}} w_S \]

theo modulo \(998\,244\,353\).

Yêu cầu cài đặt

Bạn không được cài đặt hàm main. Submission phải include rainbow.h và cài đặt:

C++
int rainbow(int c, int n, std::vector<int> f);
  • c là số hiệu test; c=0 biểu thị dữ liệu mẫu.
  • n là số đỉnh.
  • f có độ dài \(n\), với \(f_0=0\) và \(f_i\) là cha của \(i\) khi \(1\le i<n\).
  • Hàm phải trả về tổng cần tìm theo modulo \(998\,244\,353\).
  • Bộ chấm gọi hàm đúng một lần cho mỗi test.

Khung khai báo:

C++
#include "rainbow.h"

Dữ liệu bộ chấm

  • Dòng đầu chứa \(c,n\).
  • Dòng thứ hai chứa \(f_1,f_2,\ldots,f_{n-1}\).

Grader ghi một số nguyên là giá trị trả về của rainbow.

Ràng buộc

  • \(1\le n\le200\).
  • \(0\le f_i<i\) với mọi \(1\le i<n\).

Phân nhóm

Mỗi test có giá trị \(4\) điểm.

Test \(n\le\) Tính chất
\(1\) \(4\) Không
\(2\) \(8\) Không
\(3,4\) \(16\) Không
\(5\sim7\) \(50\) Không
\(8,9\) \(10^2\) B
\(10\sim12\) \(10^2\) Không
\(13\sim15\) \(150\) Không
\(16\) \(200\) A
\(17\sim19\) \(200\) B
\(20\sim25\) \(200\) Không
  • Tính chất A: \(f_i=i-1\) với mọi \(1\le i<n\); cây là một đường đi.
  • Tính chất B: với mọi đỉnh \(i\), có không quá hai đỉnh \(j\) thỏa \(f_j=i\).

Ví dụ

Ví dụ 1

Input 
0 3
0 0
Output 
8
Note
  • Với \(S=\varnothing\), có ba độ rực rỡ: \([1,1,1]\), \([2,1,1]\), \([3,1,1]\).
  • Với \(S=\{1\}\), có hai độ rực rỡ: \([1,1,1]\), \([2,1,1]\).
  • Với \(S=\{2\}\), cũng có hai độ rực rỡ trên.
  • Với \(S=\{1,2\}\), chỉ có \([1,1,1]\).

Do đó đáp án là \(3+2+2+1=8\).

Ví dụ 2

Input 
0 6
0 1 0 3 1
Output 
279

Nguồn

CCF NOI 2026 - Ngày 2, bài Rainbow Tree. Đề và dữ liệu chính thức được phát hành theo giấy phép CC BY-NC.