NOI Trung Quốc 2026 - Ngày 1

Bạn có \(n\) đoạn thẳng nằm trong \([1,m]\). Đoạn thứ \(i\) (\(0\le i<n\)) là \([l_i,r_i]\).

Với mỗi tập chỉ số \(S\subseteq\{0,1,\ldots,n-1\}\), dựng một đồ thị có tập đỉnh là \(S\). Hai đỉnh \(u,v\) được nối bởi một cạnh khi và chỉ khi hai đoạn tương ứng giao nhau, tức tồn tại \(x\in[1,m]\) sao cho

Tập \(S\) được gọi là đẹp khi đồ thị vừa dựng chính xác là một cây.

Cho số nguyên dương \(k\le n\). Với mỗi \(s=1,2,\ldots,k\), hãy đếm số tập đẹp có đúng \(s\) phần tử. In các kết quả 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 segment.h và cài đặt đúng hai hàm sau:

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 này.
• Bộ chấm gọi hàm đúng một lần khi chương trình bắt đầu.

std::vector<int> segment(
    int n, int m, int k,
    std::vector<int> l,
    std::vector<int> r
);

• n, m, k có ý nghĩa như trong đề.
• l, r chứa hai đầu mút của \(n\) đoạn theo thứ tự.
• Hàm phải trả về một vector có đúng \(k+1\) phần tử \(a\), trong đó \(a_0=0\) và \(a_s\) là đáp án cho kích thước \(s\), lấy modulo \(998\,244\,353\).
• Bộ chấm gọi hàm đúng t lần.

Khung khai báo:

#include "segment.h"

Dữ liệu bộ chấm

Grader đọc dữ liệu theo định dạng sau:

• Dòng đầu chứa \(c,t\).
• Với mỗi trong \(t\) bộ dữ liệu:
• Dòng đầu chứa \(n,m,k\).
• \(n\) dòng tiếp theo, dòng thứ \(i\) chứa \(l_i,r_i\).

Với mỗi bộ dữ liệu, grader ghi một dòng gồm \(a_1,a_2,\ldots,a_k\).

Ràng buộc

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

• \(1\le t\le20\).
• \(1\le n\le3000\).
• \(1\le m\le10^3\).
• \(1\le k\le n\) và \(K\le200\).
• \(1\le l_i\le r_i\le m\).

Phân nhóm

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

• Tính chất A: với mọi \(i\ne j\), đoạn \(i\) không chứa đoạn \(j\), tức \(l_i>l_j\) hoặc \(r_i<r_j\).
• Tính chất B: với mọi \(0\le i<j<n\), đoạn \(i\) chứa đoạn \(j\) hoặc hai đoạn không giao nhau; tức \(l_i\le l_j\le r_j\le r_i\), hoặc \(r_i<l_j\), hoặc \(l_i>r_j\).
• Tính chất C: toàn bộ \(2n\) đầu mút \(l_0,\ldots,l_{n-1},r_0,\ldots,r_{n-1}\) đôi một khác nhau.

Ví dụ

0 3
3 3 3
1 2
2 3
1 3
4 5 4
1 2
2 3
3 4
4 5
4 2 3
1 2
1 2
1 2
1 1

3 3 0
4 3 2 1
4 6 0

Trong bộ đầu tiên, ba tập một phần tử và ba tập hai phần tử đều đẹp. Tập ba phần tử tạo thành tam giác nên không đẹp.

Trong bộ thứ hai, số tập đẹp theo kích thước lần lượt là \(4,3,2,1\).

Nguồn

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

Đất nước C có \(n\) thành phố, đánh số từ \(0\) đến \(n-1\). Có \(n-1\) con đường nối các thành phố thành một cây. Đi qua một con đường tốn \(1\) đơn vị thời gian.

Mỗi thành phố còn có một cổng dịch chuyển. Dùng cổng cũng tốn \(1\) đơn vị thời gian, sau đó người dùng được đưa tới một trong \(n\) thành phố với xác suất bằng nhau. Người dùng có thể bị đưa trở lại chính thành phố hiện tại.

Có \(m\) phép thử. Trong phép thử \(i\), người thử nghiệm cần đi từ \(x_i\) tới \(y_i\). Một chiến lược phải chọn trước một hành động cho mỗi thành phố khác đích: hoặc đi tới một đỉnh kề cố định, hoặc dùng cổng dịch chuyển. Mỗi lần tới thành phố đó, người thử nghiệm luôn thực hiện hành động đã chọn.

Nói chính xác hơn, với đích \(y_i\), chiến lược là một dãy \([a_0,\ldots,a_{n-1}]\) sao cho \(a_{y_i}=-1\); với mỗi \(j\ne y_i\), hoặc \(a_j\) là một đỉnh kề \(j\), hoặc \(a_j=n\) để biểu thị việc dùng cổng. Chiến lược hợp lệ khi kỳ vọng thời gian tới đích là hữu hạn.

Với mỗi phép thử, hãy tìm kỳ vọng thời gian nhỏ nhất trong mọi chiến lược hợp lệ.

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

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

std::vector<std::pair<long long, int>> teleport(
    int c, int n, int m,
    std::vector<int> u,
    std::vector<int> v,
    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à số thành phố và số phép thử.
• Với \(0\le i<n-1\), đường thứ \(i\) nối \(u_i\) và \(v_i\).
• Với \(0\le i<m\), phép thử thứ \(i\) đi từ \(x_i\) tới \(y_i\).
• Hàm phải trả về một vector có đúng \(m\) cặp \((A_i,B_i)\). Kỳ vọng nhỏ nhất của phép thử \(i\) phải bằng phân số tối giản \(A_i/B_i\). Nếu kết quả là số nguyên dương thì phải trả về \(B_i=1\).
• Bộ chấm gọi hàm đúng một lần cho mỗi test.

Khung khai báo:

#include "teleport.h"

Dữ liệu bộ chấm

Grader đọc dữ liệu theo định dạng sau:

• Dòng đầu chứa \(c,n,m\).
• \(n-1\) dòng tiếp theo chứa các cạnh \(u_i,v_i\).
• \(m\) dòng cuối chứa các cặp \(x_i,y_i\).

Grader ghi \(m\) dòng; dòng thứ \(i\) chứa \(A_i,B_i\).

Ràng buộc

• \(2\le n\le5\cdot10^5\).
• \(1\le m\le10^6\).
• \(0\le u_i,v_i<n\) và các cạnh tạo thành một cây.
• \(0\le x_i,y_i<n\) và \(x_i\ne y_i\).

Phân nhóm

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

• Tính chất A: \(u_i=i\) và \(v_i=i+1\) với mọi \(0\le i<n-1\).
• Tính chất B: \(y_i=0\) với mọi \(0\le i<m\).

Ví dụ

0 4 4
0 1
1 2
2 3
0 3
0 1
0 2
1 2

7 3
1 1
2 1
1 1

Trong phép thử đầu tiên, đi thẳng theo đường mất \(3\) đơn vị. Nếu dùng cổng tại thành phố \(0\) cho đến khi rời được thành phố này rồi đi theo đường tới \(3\), kỳ vọng là \(7/3\). Có thể chứng minh đây là giá trị nhỏ nhất.

Một chiến lược khiến người thử nghiệm đi mãi giữa hai thành phố mà không thể tới đích không hợp lệ.

Nguồn

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

Bạn cần giải một bài tương tác được mô phỏng trong cùng tiến trình.

Độ ngon của mỗi chiếc bánh pudding là một số nguyên dương không quá \(4500\). Một chiếc bánh bí mật có độ ngon \(w\), trong đó \(1\le w\le m\).

Trong một lần hỏi, bạn chọn một dãy không rỗng \(a=[a_0,a_1,\ldots,a_{k-1}]\) gồm độ ngon của những chiếc bánh mua thêm. Thư viện chèn chiếc bánh bí mật vào dãy rồi sắp xếp thành

Giá trị trả về là

Hãy xác định chính xác \(w\), đồng thời dùng càng ít lần hỏi và càng ít bánh mua thêm càng tốt.

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

Bạn không được cài đặt hàm main, không được đọc standard input và không được ghi standard output. Submission phải include pudding.h và cài đặt:

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ố trường hợp bí mật trong test.
• Thư viện gọi hàm đúng một lần khi chương trình bắt đầu.

int find_tastiness(int c, int m);

• c là số hiệu test và m là cận trên của \(w\).
• Hàm phải trả về chính xác \(w\).
• Thư viện gọi hàm đúng t lần. Mỗi lần gọi có một giá trị \(w\) đã được cố định riêng.

Trong find_tastiness, bạn có thể gọi:

int query_tastiness(std::vector<int> a);

• a phải không rỗng; mỗi phần tử phải thuộc \([1,4500]\).
• Hàm trả về tổng gcd được định nghĩa ở trên.
• Trong mỗi lần gọi find_tastiness, bạn được gọi query_tastiness không quá \(15\) lần.
• Tổng độ dài của mọi vector a trong một lần gọi find_tastiness không quá \(3000\).

Khung khai báo:

#include "pudding.h"

Thư viện tương tác không thích nghi: giá trị \(w\) đã được xác định trước mỗi lần gọi find_tastiness và không thay đổi theo các câu hỏi. Thí sinh không được tìm cách đọc trạng thái nội bộ của grader hoặc giao tiếp trực tiếp qua standard input/output.

Trong mọi trường hợp, phần thư viện của grader dùng không quá \(1.5\) giây và \(64\ \mathrm{MiB}\); lượng tài nguyên này không tính vào giới hạn dành cho submission.

Ràng buộc

• \(1\le t\le3000\).
• \(1\le m\le3000\).
• \(1\le w\le m\).

Phân nhóm

Tính chất A: \(w\) là số nguyên tố trong mọi trường hợp.

Cách tính điểm

Nếu có một giá trị trả về sai, một câu hỏi không hợp lệ hoặc vượt giới hạn, test tương ứng nhận \(0\) điểm.

Nếu mọi giá trị đều đúng, gọi \(Q\) là số câu hỏi lớn nhất trong một lần gọi find_tastiness, \(S\) là tổng số bánh mua thêm lớn nhất trong một lần gọi, và \(P\) là số điểm của test. Điểm nhận được là

Trong đó

và

Ví dụ tương tác

Giả sử \(m=197\) và chiếc bánh bí mật có \(w=26\).

Ở câu hỏi đầu, dãy sau sắp xếp là \([7,20,26,2026]\), nên kết quả bằng

Ở câu hỏi thứ hai, dãy là \([13,26,52]\) và kết quả bằng \(13+26=39\). Lần tìm này dùng \(Q=2\) câu hỏi và \(S=3+2=5\) bánh.

Nguồn

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