USACO 2020 - US Open - Hạng Vàng

Mệt mỏi vì xoáy tóc cứng đầu của mình, Nông dân John quyết định đi cắt tóc. Ông có \(N\) (\(1 \leq N \leq 10^5\)) sợi tóc xếp thành một hàng, và ban đầu sợi tóc \(i\) dài \(A_i\) micromét (\(0 \leq A_i \leq N\)). Lý tưởng nhất, ông muốn độ dài tóc không giảm từ trái sang phải, vì vậy ông định nghĩa "độ xấu" của mái tóc là số nghịch thế: số cặp \((i,j)\) sao cho \(i < j\) và \(A_i > A_j\).

Với mỗi \(j=0,1,\ldots,N-1\), FJ muốn biết độ xấu của mái tóc nếu tất cả các sợi dài hơn \(j\) đều bị cắt ngắn xuống đúng độ dài \(j\).

(Một sự thật thú vị: trung bình một người thực sự có khoảng \(10^5\) sợi tóc trên đầu!)

Dữ liệu vào

Tệp haircut.in:

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

Dòng thứ hai chứa \(A_1,A_2,\ldots,A_N\).

Dữ liệu ra

Tệp haircut.out:

Với mỗi \(j=0,1,\ldots,N-1\), in độ xấu của mái tóc FJ trên một dòng mới.

Lưu ý rằng các số nguyên lớn xuất hiện trong bài này có thể đòi hỏi sử dụng kiểu dữ liệu số nguyên 64 bit (chẳng hạn long long trong C/C++).

Phân nhóm

• Test 2 thỏa mãn \(N \leq 100\).
• Các test 3–5 thỏa mãn \(N \leq 5000\).
• Các test 6–13 không có ràng buộc bổ sung.

Ví dụ

5
5 2 3 3 0

0
4
4
5
7

Nguồn

USACO 2020 US Open Contest, Gold — Haircut

Tác giả bài: Dhruv Rohatgi.

Mỗi con trong số \(N\) con bò của Nông dân John (\(1 \leq N \leq 2\cdot 10^5\)) có một màu yêu thích. Những con bò được đánh số thuận tiện từ \(1 \ldots N\) (như mọi khi), và mỗi màu có thể được biểu diễn bằng một số nguyên trong phạm vi \(1 \ldots N\).

Tồn tại \(M\) cặp bò \((a,b)\) sao cho bò \(b\) ngưỡng mộ bò \(a\) (\(1 \leq M \leq 2\cdot 10^5\)). Có thể xảy ra \(a=b\), trong trường hợp đó một con bò ngưỡng mộ chính nó. Với bất kỳ màu \(c\) nào, nếu mỗi con trong hai con bò \(x\) và \(y\) đều ngưỡng mộ một con bò có màu yêu thích là \(c\), thì \(x\) và \(y\) có cùng màu yêu thích.

Dựa trên thông tin này, hãy xác định một cách gán màu yêu thích cho những con bò sao cho số màu yêu thích phân biệt trong toàn bộ đàn bò là lớn nhất. Vì có nhiều cách gán thỏa mãn tính chất này, hãy in ra cách có thứ tự từ điển nhỏ nhất (nghĩa là chọn cách gán lần lượt tối thiểu hóa màu được gán cho các con bò \(1 \ldots N\) theo thứ tự đó).

Dữ liệu vào

Tệp fcolor.in:

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

Mỗi dòng trong \(M\) dòng tiếp theo chứa hai số nguyên \(a\) và \(b\) cách nhau bởi dấu cách (\(1 \leq a,b \leq N\)), biểu thị rằng bò \(b\) ngưỡng mộ bò \(a\). Cùng một cặp có thể xuất hiện nhiều lần trong dữ liệu vào.

Dữ liệu ra

Tệp fcolor.out:

Với mỗi \(i\) từ \(1 \ldots N\), in màu của bò \(i\) trong cách gán cần tìm trên một dòng mới.

Phân nhóm

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

Ví dụ

9 12
1 2
4 2
5 8
4 6
6 9
2 9
8 7
8 3
7 1
9 4
3 5
3 4

1
2
3
1
1
2
3
2
3

Nguồn

USACO 2020 US Open Contest, Gold — Favorite Colors

Tác giả bài: William Lin và Benjamin Qi.

Nông dân John lại nghĩ ra một bài tập thể dục buổi sáng mới cho những con bò!

Như trước đây, \(N\) con bò của Nông dân John (\(1 \leq N \leq 10^4\)) đang đứng thành một hàng. Con bò thứ \(i\) từ bên trái mang nhãn \(i\) với mỗi \(1 \leq i \leq N\). Ông yêu cầu chúng lặp lại bước sau cho đến khi những con bò trở về đúng thứ tự ban đầu:

• Cho một hoán vị \(A\) độ dài \(N\), những con bò thay đổi thứ tự sao cho con bò đứng thứ \(i\) từ bên trái trước khi thay đổi sẽ đứng thứ \(A_i\) từ bên trái sau khi thay đổi.

Ví dụ, nếu \(A=(1,2,3,4,5)\) thì những con bò thực hiện một bước. Nếu \(A=(2,3,1,5,4)\) thì những con bò thực hiện sáu bước. Thứ tự của những con bò từ trái sang phải sau mỗi bước như sau:

• 0 bước: \((1,2,3,4,5)\)
• 1 bước: \((3,1,2,5,4)\)
• 2 bước: \((2,3,1,4,5)\)
• 3 bước: \((1,2,3,5,4)\)
• 4 bước: \((3,1,2,4,5)\)
• 5 bước: \((2,3,1,5,4)\)
• 6 bước: \((1,2,3,4,5)\)

Tìm tổng của tất cả các số nguyên dương \(K\) sao cho tồn tại một hoán vị độ dài \(N\) khiến những con bò phải thực hiện đúng \(K\) bước.

Vì số này có thể rất lớn, hãy in đáp án theo modulo \(M\) (\(10^8 \leq M \leq 10^9+7\), \(M\) là số nguyên tố).

Dữ liệu vào

Tệp exercise.in:

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

Dữ liệu ra

Tệp exercise.out:

In một số nguyên duy nhất.

Phân nhóm

• Các test 2–5 thỏa mãn \(N \leq 10^2\).
• Các test 6–10 không có ràng buộc bổ sung.

Ví dụ

5 1000000007

21

Nguồn

USACO 2020 US Open Contest, Gold — Exercise

Tác giả bài: Benjamin Qi.