USACO 2020 - Tháng 2 - Hạng Vàng - Bộ đề bài

#	Bài tập	Điểm	Thời gian:	Giới hạn bộ nhớ
1	USACO 2020 - Timeline	100 (p)	4.0s	512M
2	USACO 2020 - Help Yourself	100 (p)	4.0s	512M
3	USACO 2020 - Delegation	100 (p)	4.0s	512M

1. USACO 2020 - Timeline

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

Trong \(M\) ngày vừa qua (\(2\le M\le 10^9\)), Bessie đã tham dự \(N\) buổi vắt sữa (\(1\le N\le 10^5\)). Tuy nhiên, cô gặp khó khăn khi nhớ lại mình đã tham dự từng buổi vào lúc nào.

Với mỗi buổi \(i=1\ldots N\), cô biết rằng buổi đó diễn ra không sớm hơn ngày \(S_i\) (\(1\le S_i\le M\)). Ngoài ra, Bessie có \(C\) ký ức (\(1\le C\le 10^5\)), mỗi ký ức được mô tả bằng một bộ ba \((a,b,x)\), trong đó cô nhớ rằng buổi \(b\) diễn ra sau buổi \(a\) ít nhất \(x\) ngày.

Hãy giúp Bessie tính ngày diễn ra sớm nhất có thể của mỗi buổi vắt sữa. Dữ liệu bảo đảm Bessie không nhớ sai; nói cách khác, tồn tại một cách gán các buổi vào những ngày trong đoạn \(1\ldots M\) sao cho mọi ràng buộc từ các ký ức của cô đều được thỏa mãn.

Phân nhóm

Các test 2-4 thỏa mãn \(N,C\le 10^3\).
Các test 5-10 không có ràng buộc bổ sung.

Dữ liệu vào

Dòng đầu tiên chứa \(N\), \(M\) và \(C\).

Dòng tiếp theo chứa \(N\) số nguyên cách nhau bởi dấu cách \(S_1,S_2,\ldots,S_N\). Mỗi số thuộc đoạn \(1\ldots M\).

Mỗi dòng trong \(C\) dòng tiếp theo chứa ba số nguyên \(a\), \(b\) và \(x\), cho biết buổi \(b\) diễn ra sau buổi \(a\) ít nhất \(x\) ngày. Trên mỗi dòng, \(a\ne b\), \(a\) và \(b\) thuộc đoạn \(1\ldots N\), còn \(x\) thuộc đoạn \(1\ldots M\).

Dữ liệu ra

In \(N\) dòng, cho biết ngày diễn ra sớm nhất có thể của mỗi buổi.

Ví dụ

Ví dụ 1

Input

Output

Giải thích

Buổi thứ hai diễn ra sau buổi thứ nhất ít nhất năm ngày, nên không thể diễn ra trước ngày \(1+5=6\). Buổi thứ tư diễn ra sau buổi thứ hai ít nhất hai ngày, nên không thể diễn ra trước ngày \(6+2=8\).

Nguồn

USACO 2020 February Contest, Gold - Timeline: https://usaco.org/index.php?page=viewproblem2&cpid=1017

Tác giả: Mark Gordon.

2. USACO 2020 - Help Yourself

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

Bessie được cho \(N\) đoạn thẳng (\(1\le N\le 10^5\)) trên một trục số một chiều. Đoạn thẳng thứ \(i\) chứa mọi số thực \(x\) thỏa mãn \(l_i\le x\le r_i\).

Định nghĩa hợp của một tập các đoạn thẳng là tập hợp mọi \(x\) nằm trong ít nhất một đoạn thẳng. Định nghĩa độ phức tạp của một tập các đoạn thẳng là số miền liên thông được biểu diễn trong hợp của chúng.

Bessie muốn tính tổng độ phức tạp trên tất cả \(2^N\) tập con của tập \(N\) đoạn thẳng đã cho, lấy phần dư theo \(10^9+7\).

Thông thường, nhiệm vụ của bạn là giúp Bessie. Nhưng lần này, bạn chính là Bessie và không có ai giúp bạn. Hãy tự giúp mình!

Phân nhóm

Các test 2-3 thỏa mãn \(N\le 16\).
Các test 4-7 thỏa mãn \(N\le 1000\).
Các test 8-12 không có ràng buộc bổ sung.

Dữ liệu vào

Dòng đầu tiên chứa \(N\).

Mỗi dòng trong \(N\) dòng tiếp theo chứa hai số nguyên \(l_i\) và \(r_i\). Dữ liệu bảo đảm \(l_i<r_i\) và tất cả các giá trị \(l_i,r_i\) là những số nguyên đôi một phân biệt thuộc đoạn \(1\ldots 2N\).

Dữ liệu ra

In đáp án lấy phần dư theo \(10^9+7\).

Ví dụ

Ví dụ 1

Input

Output

Giải thích

Độ phức tạp của mỗi tập con khác rỗng được viết dưới đây.

\[ \{[1,6]\}\implies 1, \{[2,3]\}\implies 1, \{[4,5]\}\implies 1 \]

\[ \{[1,6],[2,3]\}\implies 1, \{[1,6],[4,5]\}\implies 1, \{[2,3],[4,5]\}\implies 2 \]

\[ \{[1,6],[2,3],[4,5]\}\implies 1 \]

Đáp án là \(1+1+1+1+1+2+1=8\).

Nguồn

USACO 2020 February Contest, Gold - Help Yourself: https://usaco.org/index.php?page=viewproblem2&cpid=1018

Tác giả: Benjamin Qi.

3. USACO 2020 - Delegation

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

Trang trại của Farmer John gồm \(N\) đồng cỏ (\(2\leq N\leq 10^5\)) được nối bởi \(N-1\) con đường sao cho có thể đi từ bất kỳ đồng cỏ nào đến bất kỳ đồng cỏ nào khác. Nói cách khác, trang trại là một cây. Nhưng sau 28 năm xử lý những bài toán thuật toán hóc búa chắc chắn nảy sinh từ cây, FJ đã quyết định rằng một trang trại có dạng cây đơn giản là quá phức tạp. Ông tin rằng các bài toán thuật toán sẽ đơn giản hơn trên các đường đi.

Vì vậy, kế hoạch của ông là phân hoạch tập hợp các con đường thành nhiều đường đi và giao trách nhiệm về mỗi đường đi cho một người làm công xứng đáng. Để tránh tranh chấp, ông muốn mọi đường đi có cùng độ dài. Ông tự hỏi với những độ dài nào thì tồn tại một cách phân hoạch như vậy.

Chính xác hơn, với mỗi \(1\leq K\leq N-1\), hãy giúp Farmer John xác định liệu có thể phân hoạch các con đường thành những đường đi có độ dài đúng bằng \(K\) hay không.

Phân nhóm

Trong các test 2-4, cây có dạng hình sao; nhiều nhất một đỉnh có bậc lớn hơn hai.
Các test 5-8 thỏa mãn \(N\le 10^3\).
Các test 9-15 không có ràng buộc bổ sung.

Dữ liệu vào

Dòng đầu tiên chứa một số nguyên \(N\).

Mỗi dòng trong \(N-1\) dòng tiếp theo chứa hai số nguyên \(a\) và \(b\) cách nhau bởi dấu cách, mô tả một cạnh nối đỉnh \(a\) với đỉnh \(b\). Cả \(a\) và \(b\) đều thuộc đoạn \(1\ldots N\).

Dữ liệu ra

In một xâu bit có độ dài \(N-1\). Với mỗi \(1\le K\le N-1\), bit thứ \(K\) tính từ bên trái của xâu bằng 1 nếu có thể phân hoạch các cạnh của cây thành những đường đi có độ dài đúng bằng \(K\), và bằng \(0\) nếu không thể.

Ví dụ

Ví dụ 1

Input

Output

111000000000

Giải thích

Có thể phân hoạch cây này thành các đường đi có độ dài \(K\) với \(K=1,2,3\). Khi \(K=3\), một tập các đường đi khả dĩ là:

\[ 13-12-11-8, 10-9-8-6, 7-6-2-3, 5-4-2-1 \]

Nguồn

USACO 2020 February Contest, Gold - Delegation: https://usaco.org/index.php?page=viewproblem2&cpid=1019

Tác giả: Mark Gordon và Dhruv Rohatgi.