CEOI 2025 - Ngày 2

Đề bài

Với một mảng số nguyên \(a[0],a[1],\ldots,a[m-1]\), gọi vẻ đẹp của mảng là số lượng số nguyên dương \(k\) sao cho có thể chia mảng thành \(k\) mảng con rời nhau, mỗi mảng con là một dãy phần tử liên tiếp, mỗi phần tử của mảng ban đầu thuộc đúng một mảng con, và tất cả các mảng con đều có cùng số nguyên dương nhỏ nhất không xuất hiện.

Số nguyên dương nhỏ nhất không xuất hiện của một mảng là số nguyên nhỏ nhất lớn hơn \(0\) không xuất hiện trong mảng đó.

Cho mảng số nguyên \(v[0],v[1],\ldots,v[n-1]\) và \(q\) truy vấn \((l_i,r_i)\), trong đó \(0\le l_i\le r_i<n\). Với mỗi truy vấn, hãy tìm vẻ đẹp của mảng

Chi tiết cài đặt

Bạn cần cài đặt hàm sau:

std::vector<int> solve(
    int n,
    std::vector<int>& v,
    int q,
    std::vector<std::pair<int, int>>& queries
);

• n: kích thước của mảng số nguyên.
• v: mảng ban đầu có độ dài \(n\).
• q: số truy vấn.
• queries: mảng độ dài \(q\) mô tả các truy vấn; phần tử thứ \(i\) là cặp \((l_i,r_i)\).
• Trong giao diện của thí sinh, mọi chỉ số trong queries đều bắt đầu từ \(0\). Dữ liệu kiểm thử thô chính thức lưu hai đầu mút bắt đầu từ \(1\); trình chấm chuyển chúng về chỉ số bắt đầu từ \(0\) trước khi gọi solve.
• Hàm phải trả về một mảng gồm \(q\) số nguyên, lần lượt là đáp án của các truy vấn.
• Hàm được gọi đúng một lần cho mỗi bộ kiểm thử.

Ràng buộc

• \(1\le n\le600\,000\).
• \(1\le q\le600\,000\).
• \(1\le v[i]\le400\,000\) với mọi \(0\le i<n\).
• \(0\le l_i\le r_i<n\) với mọi \(0\le i<q\).

Phân nhóm

• Phân nhóm 1 (4 điểm): \(1\le n\le10\), \(1\le q\le100\).
• Phân nhóm 2 (6 điểm): \(1\le n,q\le100\).
• Phân nhóm 3 (17 điểm): \(1\le n,q\le1\,000\).
• Phân nhóm 4 (10 điểm): \(1\le n,q\le100\,000\) và \(1\le v[i]\le2\) với mọi \(0\le i<n\).
• Phân nhóm 5 (30 điểm): \(1\le n,q\le75\,000\).
• Phân nhóm 6 (33 điểm): Không có ràng buộc bổ sung.

Ví dụ

solve(
    10,
    {1, 1, 2, 2, 3, 3, 1, 2, 3, 4},
    2,
    {{0, 5}, {0, 8}}
)

{1, 2}

Trình chấm mẫu

Trình chấm mẫu đọc dữ liệu theo định dạng sau:

• Dòng \(1\): n q.
• Dòng \(2\): v[0] v[1] ... v[n-1].
• Dòng \(3+i\) với \(0\le i<q\): l_i r_i, sử dụng chỉ số bắt đầu từ \(0\) như giao diện solve.

Trình chấm mẫu in \(q\) dòng là các phần tử của mảng do solve trả về.

Đề bài

Cho một hoán vị

của các số \(1,2,\ldots,n\). Một phép tách của \(p\) là một hoán vị \(q\) có thể thu được bằng quy trình sau:

1. Chọn hai tập chỉ số \(A=\{i_1,i_2,\ldots,i_k\}\) và \(B=\{j_1,j_2,\ldots,j_l\}\) sao cho \(A\cap B=\varnothing\), \(A\cup B=\{0,1,\ldots,n-1\}\), \(i_1<i_2<\cdots<i_k\) và \(j_1<j_2<\cdots<j_l\).
2. Tạo hoán vị

Ký hiệu \(S(p)\) là tập hợp tất cả các phép tách của hoán vị \(p\).

Cho số nguyên \(n\) và một tập \(T\) gồm \(m\) hoán vị độ dài \(n\). Hãy đếm số hoán vị \(p\) độ dài \(n\) thỏa mãn

Vì kết quả có thể rất lớn, hãy trả về kết quả theo modulo \(998\,244\,353\).

Chi tiết cài đặt

Bạn cần cài đặt hàm sau:

int solve(
    int n,
    int m,
    std::vector<std::vector<int>>& splits
);

• n: độ dài của mỗi hoán vị.
• m: số phép tách được cho.
• splits: mảng gồm \(m\) hoán vị đôi một phân biệt, chính là các phần tử của tập \(T\).
• Hàm phải trả về số hoán vị \(p\) có thể có, theo modulo \(998\,244\,353\).
• Hàm được gọi đúng một lần cho mỗi bộ kiểm thử.

Ràng buộc

• \(1\le n\le300\).
• \(1\le m\le300\).

Phân nhóm

• Phân nhóm 1 (6 điểm): \(m=1\).
• Phân nhóm 2 (7 điểm): \(1\le n,m\le10\).
• Phân nhóm 3 (17 điểm): \(1\le n,m\le18\).
• Phân nhóm 4 (17 điểm): \(1\le n\le30\), \(1\le m\le15\).
• Phân nhóm 5 (16 điểm): \(1\le n,m\le90\).
• Phân nhóm 6 (16 điểm): \(1\le n\le300\), \(1\le m\le15\).
• Phân nhóm 7 (21 điểm): Không có ràng buộc bổ sung.

Ví dụ

solve(3, 2, {{1, 2, 3}, {2, 1, 3}})

4

123
132
213
231

Trình chấm mẫu

Trình chấm mẫu đọc dữ liệu theo định dạng sau:

• Dòng \(1\): n m.
• Dòng \(2+i\) với \(0\le i<m\): splits[i][0] splits[i][1] ... splits[i][n-1].

Trình chấm mẫu in kết quả của lời gọi solve với các tham số tương ứng.

Đề bài

Nếu từng bộ phận của con tàu Theseus lần lượt được thay thế theo thời gian, thì vào thời điểm nào, nếu có, nó không còn là cùng một con tàu nữa?

Khi không suy ngẫm về những vấn đề trừu tượng, Theseus dành thời gian rảnh để tiêu diệt Minotaur. Tuy nhiên, lần này anh phải đi qua một mê cung tối tăm và ngoằn ngoèo trước. Vì đây không phải việc dễ dàng, Theseus nhờ Ariadne dẫn đường.

Mê cung được biểu diễn bởi một đồ thị vô hướng liên thông gồm \(n\) đỉnh, đánh số từ \(1\) đến \(n\), và \(m\) cạnh. Có một đỉnh đặc biệt \(t\) là nơi Minotaur đang ở.

Theseus hoàn toàn không nhìn thấy đồ thị, còn Ariadne nhìn thấy toàn bộ. Họ sẽ thống nhất một chiến lược để Theseus có thể đến đỉnh chứa Minotaur một cách an toàn: Ariadne gắn nhãn \(0\) hoặc \(1\) lên mỗi cạnh. Sau đó Theseus đi vào mê cung tại một đỉnh \(s\) mà Ariadne không biết trước.

Do mê cung rất tối, tại mỗi thời điểm Theseus chỉ nhìn thấy chỉ số của đỉnh hiện tại, chỉ số của các đỉnh kề và nhãn của các cạnh kề. Hơn nữa, vì mê cung rất ngoằn ngoèo, anh không thể nhớ bất kỳ thông tin nào về những đỉnh đã đi qua trước đó.

Để đến chỗ Minotaur an toàn, Theseus phải thực hiện không quá

bước đi, trong đó \(\operatorname{dist}(s,t)\) là số cạnh ít nhất trên một đường đi từ \(s\) đến \(t\), và \(C\) là một hằng số.

Chi tiết cài đặt

Bạn cần cài đặt hai hàm sau.

std::vector<int> paint(
    int n,
    std::vector<std::pair<int, int>> edges,
    int t
);

• n: số đỉnh của đồ thị.
• edges: danh sách độ dài \(m\) mô tả các cạnh của đồ thị.
• t: đỉnh đích.
• Hàm phải trả về một danh sách độ dài \(m\). Phần tử thứ \(i\) là nhãn của cạnh thứ \(i\) trong edges và phải bằng \(0\) hoặc \(1\).
• Nếu một cạnh được gắn giá trị khác \(0\) và \(1\), hành vi của chương trình không được xác định.
• Hàm được gọi đúng một lần trong mỗi tiến trình tô màu của một bộ kiểm thử.

int travel(
    int n,
    int u,
    std::vector<std::pair<int, int>> neighbours
);

• n: số đỉnh của đồ thị.
• u: đỉnh hiện tại.
• neighbours: danh sách các cặp \((v,e)\), cho biết có một cạnh nối \(u\) với \(v\) và cạnh ấy mang nhãn \(e\).
• Hàm phải trả về một đỉnh kề để Theseus di chuyển tới. Nếu đỉnh trả về là \(t\), chương trình tự động kết thúc.
• Trong mọi lời gọi hàm này, đảm bảo \(u\ne t\).
• Mỗi lời gọi hàm biểu diễn một bước đi trong mê cung. Trong mỗi bộ kiểm thử, hàm có thể được gọi số lần cần thiết cho đến khi Theseus đến đỉnh đích.

Chú ý: Các lời gọi paint và travel được thực hiện trong các tiến trình độc lập. Chương trình không được dùng biến toàn cục hoặc biến static để truyền thông tin giữa các thực thể khác nhau của paint hoặc travel. Mọi hành vi cố lách yêu cầu này đều dẫn đến hành vi không được xác định.

Ràng buộc

• \(1\le n\le10\,000\).
• \(1\le m\le50\,000\).
• \(C=14\).
• Đỉnh xuất phát \(s\) của mỗi bộ kiểm thử được cố định trước khi gọi hàm label.

Phân nhóm

• Phân nhóm 1 (4 điểm): Đồ thị là một clique, tức là có cạnh giữa mọi cặp đỉnh \(1\le u<v\le n\).
• Phân nhóm 2 (10 điểm): Khoảng cách từ đỉnh đích đến mọi đỉnh trong đồ thị không vượt quá \(2\) cạnh.
• Phân nhóm 3 (11 điểm): Đồ thị là một cây.
• Phân nhóm 4 (13 điểm): Đồ thị là đồ thị hai phía, tức là có thể chia các đỉnh thành hai tập sao cho không có cạnh nối hai đỉnh thuộc cùng một tập.
• Phân nhóm 5 (12 điểm): Đồ thị là một đồ thị bậc thang như định nghĩa dưới đây.
• Phân nhóm 6 (50 điểm): Không có ràng buộc bổ sung.

Đồ thị bậc thang gồm hai đường đi song song có cùng độ dài; mỗi cặp đỉnh tương ứng trên hai đường đi được nối bằng một cạnh để tạo thành các bậc thang. Ở một đầu của bậc thang có đỉnh đặc biệt \(t\), là đỉnh đích, được nối với cả hai đầu mút ở phía đó và đóng vai trò như một đỉnh cha chung. Với mọi đồ thị như vậy, \(n\) luôn là số lẻ.

![Minh họa đồ thị bậc thanghttps://cdn.lqdoj.edu.vn/media/pagedown-uploads/pd_7_963affdb.png

Ví dụ

Xét đồ thị có \(7\) đỉnh và \(7\) cạnh dưới đây. Đỉnh xuất phát là \(3\), được tô màu xanh lá; đỉnh đích là \(7\), được tô màu đỏ.

![Đồ thị trong ví dụ Theseushttps://cdn.lqdoj.edu.vn/media/pagedown-uploads/pd_7_388d02c1.png

Đầu tiên, trình chấm gọi paint. Giả sử hàm trả về dãy nhãn sau:

Khi ấy, một chuỗi lời gọi travel hợp lệ đưa Theseus đến đích là:

Khi giá trị trả về là \(7\), tức đỉnh đích, chương trình dừng lại.

Trình chấm mẫu

Trình chấm mẫu đọc dữ liệu theo định dạng sau:

• Dòng \(1\): n m.
• Dòng \(2\): s t.
• Dòng \(3+i\) với \(0\le i<m\): a b, biểu diễn một cạnh nối hai đỉnh \(a\) và \(b\).

Đầu tiên, trình chấm gọi paint với các tham số tương ứng và gắn nhãn cho các cạnh theo danh sách trả về. Sau đó, trình chấm gọi travel với các tham số \(n\), \(s\) và danh sách các đỉnh kề của \(s\). Sau lời gọi đầu tiên, trình chấm tiếp tục gọi travel, lấy đỉnh hiện tại là đỉnh do lời gọi trước trả về, cho đến khi đạt đỉnh đích \(t\).

Với mỗi bước, trình chấm mẫu in đỉnh hiện tại và đỉnh do travel trả về. Cuối cùng, trình chấm in tổng số bước đi.