USACO 2021 - Tháng 1 - Hạng Bạc

Những chú bò của Farmer John đang biểu diễn các bước nhảy mới!

Ban đầu, cả \(N\) con bò (\(2\le N\le 10^5\)) đứng thành một hàng, với bò \(i\) ở vị trí thứ \(i\). Chuỗi động tác gồm \(K\) cặp vị trí (\(1\le K\le 2\cdot10^5\)): \((a_1,b_1),(a_2,b_2),\ldots,(a_K,b_K)\). Ở phút thứ \(i=1\ldots K\), hai con bò đang đứng tại vị trí \(a_i\) và \(b_i\) đổi chỗ.

Cùng \(K\) lần đổi chỗ này lại diễn ra trong các phút \(K+1\ldots2K\), rồi \(2K+1\ldots3K\), và tiếp tục lặp theo chu kỳ mãi mãi. Nói cách khác:

• Phút \(1\): bò tại \(a_1\) và \(b_1\) đổi chỗ.
• Phút \(2\): bò tại \(a_2\) và \(b_2\) đổi chỗ.
• \(\ldots\)
• Phút \(K\): bò tại \(a_K\) và \(b_K\) đổi chỗ.
• Phút \(K+1\): bò tại \(a_1\) và \(b_1\) đổi chỗ.
• Phút \(K+2\): bò tại \(a_2\) và \(b_2\) đổi chỗ.
• Và cứ tiếp tục như vậy.

Với mỗi con bò, hãy xác định số vị trí phân biệt trong hàng mà nó từng đứng.

Dữ liệu vào

Dòng đầu tiên chứa \(N\) và \(K\). Mỗi dòng thứ \(i\) trong \(K\) dòng tiếp theo chứa \(a_i\) và \(b_i\) (\(1\le a_i<b_i\le N\)).

Dữ liệu ra

In \(N\) dòng, dòng thứ \(i\) chứa số vị trí phân biệt mà bò \(i\) từng đến.

Phân nhóm

• Các test 1-5 thỏa mãn \(N\le 100\), \(K\le 200\).
• Các test 6-10 thỏa mãn \(N\le 2000\), \(K\le 4000\).
• Các test 11-20 không có ràng buộc bổ sung.

Ví dụ

5 4
1 3
1 2
2 3
2 4

4
4
3
4
1

Nguồn

USACO 2021 January Contest, Silver - Dance Mooves: https://usaco.org/index.php?page=viewproblem2&cpid=1086

Tác giả: Chris Zhang.

Gần đây Bessie được tặng một bộ dụng cụ vẽ và muốn sơn hàng rào dài ở một đầu đồng cỏ. Hàng rào gồm \(N\) đoạn liên tiếp, mỗi đoạn dài 1 mét (\(1\le N\le 10^5\)). Bessie có 26 màu khác nhau, được ký hiệu bằng các chữ cái từ A đến Z theo độ đậm tăng dần: A rất nhạt, còn Z rất đậm. Vì vậy, màu mong muốn của từng đoạn hàng rào được mô tả bằng một xâu độ dài \(N\).

Ban đầu, mọi đoạn hàng rào đều chưa được sơn. Trong một nét cọ, Bessie có thể tô một đoạn liên tiếp bất kỳ bằng một màu duy nhất, miễn là cô không bao giờ sơn màu nhạt hơn lên trên màu đậm hơn; cô chỉ có thể phủ màu đậm lên màu nhạt.

Ví dụ, một đoạn chưa tô có độ dài bốn có thể được sơn như sau:

.... -> BBB. -> BBLL -> BQQL

Vì sắp hết thời gian, Bessie có thể phải để nguyên một đoạn liên tiếp không sơn. Cô đang xét \(Q\) đoạn ứng viên (\(1\le Q\le 10^5\)), mỗi đoạn được mô tả bởi hai số nguyên \((a,b)\) với \(1\le a\le b\le N\), là hai đầu mút của đoạn \(a\ldots b\) cần để trống.

Với mỗi đoạn ứng viên, hãy tính số nét cọ ít nhất để sơn mọi đoạn hàng rào nằm ngoài đoạn đó đúng màu mong muốn, đồng thời giữ mọi đoạn bên trong chưa sơn. Bessie không thực sự sơn trong quá trình này, nên đáp án của các ứng viên độc lập với nhau.

Dữ liệu vào

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

Dòng tiếp theo chứa một xâu độ dài \(N\), biểu diễn màu mong muốn của từng đoạn hàng rào.

\(Q\) dòng tiếp theo, mỗi dòng chứa hai số nguyên \(a\) và \(b\), cách nhau bởi dấu cách, mô tả một đoạn ứng viên cần để trống.

Dữ liệu ra

Với mỗi ứng viên trong \(Q\) ứng viên, in đáp án trên một dòng mới.

Phân nhóm

• Các test 1-4 thỏa mãn \(N,Q\le 100\).
• Các test 5-7 thỏa mãn \(N,Q\le 5000\).
• Các test 8-13 không có ràng buộc bổ sung.

Ví dụ

8 2
ABBAABCB
3 6
1 4

4
3

.... -> AA.. -> ABBB -> ABCB

Nguồn

USACO 2021 January Contest, Silver - No Time to Paint: https://usaco.org/index.php?page=viewproblem2&cpid=1087

Tác giả: Andi Qu và Brian Dean.

Farmer John muốn chụp một bức ảnh đàn bò đang gặm cỏ để treo lên tường. Đồng cỏ được biểu diễn bằng một lưới \(N\) hàng và \(N\) cột gồm các ô vuông, giống một bàn cờ \(N\times N\), với \(2\le N\le 1000\). Trong bức ảnh trước, đàn bò tụ lại quá đông ở một vùng. Lần này, ông muốn chúng được phân bố đều trên đồng cỏ và đặt ra các quy tắc sau:

• Không có hai con bò nào ở cùng một ô.
• Mọi lưới con \(2\times2\), có tổng cộng \((N-1)\times(N-1)\) lưới như vậy, phải chứa đúng 2 con bò.

Ví dụ, cách đặt sau hợp lệ:

CCC
...
CCC

Cách đặt sau không hợp lệ vì vùng \(2\times2\) chứa ô góc dưới bên phải chỉ có 1 con bò:

C.C
.C.
C..

Không có ràng buộc nào khác. Có thể giả sử Farmer John có vô hạn bò.

Farmer John muốn một số ô có bò hơn các ô khác. Cụ thể, khi đặt một con bò vào ô \((i,j)\), vẻ đẹp của bức ảnh tăng thêm \(a_{ij}\) đơn vị (\(0\le a_{ij}\le 1000\)). Hãy xác định tổng vẻ đẹp lớn nhất của một cách đặt bò hợp lệ.

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 \(N\) số nguyên. Số thứ \(j\) trên dòng thứ \(i\), tính từ trên xuống, là \(a_{ij}\).

Dữ liệu ra

In một số nguyên là vẻ đẹp lớn nhất có thể của bức ảnh.

Phân nhóm

• Các test 2-4 thỏa mãn \(N\le 4\).
• Các test 5-10 thỏa mãn \(N\le 10\).
• Các test 11-20 thỏa mãn \(N\le 1000\).

Ví dụ

4
3 3 1 1
1 1 3 1
3 3 1 1
1 1 3 3

22

CC..
..CC
CC..
..CC

Nguồn

USACO 2021 January Contest, Silver - Spaced Out: https://usaco.org/index.php?page=viewproblem2&cpid=1088

Tác giả: Hankai Zhang và Danny Mittal.