USACO 2019 - Tháng 12 - Hạng Bạch Kim

Nông dân John có \(M\) cô bò, được đánh số thuận tiện từ \(1 \ldots M\), thỉnh thoảng thích đổi khẩu vị thay vì ăn cỏ. Để chiêu đãi các cô bò, Nông dân John đã nướng \(N\) chiếc bánh (\(1 \leq N \leq 300\)), được đánh số \(1 \ldots N\). Bò \(i\) thích những chiếc bánh có số trong đoạn \([l_i,r_i]\) (từ \(l_i\) đến \(r_i\), kể cả hai đầu mút), và không có hai cô bò nào thích chính xác cùng một đoạn bánh. Bò \(i\) còn có trọng lượng \(w_i\), là một số nguyên trong phạm vi \(1 \ldots 10^6\).

Nông dân John có thể chọn một dãy các cô bò \(c_1,c_2,\ldots,c_K\), sau đó những cô bò được chọn sẽ lần lượt ăn theo thứ tự đó. Thật không may, các cô bò không biết chia sẻ! Khi đến lượt bò \(c_i\) ăn, cô sẽ ăn tất cả những chiếc bánh mà mình thích — tức là tất cả bánh còn lại trong đoạn \([l_{c_i},r_{c_i}]\). Nông dân John muốn tránh tình huống khó xử khi đến lượt một cô bò ăn nhưng tất cả bánh cô thích đều đã bị ăn hết. Vì vậy, ông muốn bạn tính tổng trọng lượng lớn nhất có thể (\(w_{c_1}+w_{c_2}+\ldots+w_{c_K}\)) của một dãy \(c_1,c_2,\ldots,c_K\) sao cho mỗi cô bò trong dãy ăn được ít nhất một chiếc bánh.

Phân nhóm

• Các test 2–5 thỏa mãn \(N \leq 50\) và \(M \leq 20\).
• Các test 6–9 thỏa mãn \(N \leq 50\).

Dữ liệu vào

Dòng đầu tiên chứa hai số nguyên \(N\) và \(M\) (\(1 \leq M \leq \frac{N(N+1)}{2}\)).

Mỗi dòng trong \(M\) dòng tiếp theo mô tả một cô bò bằng các số nguyên \(w_i\), \(l_i\) và \(r_i\).

Dữ liệu ra

In tổng trọng lượng lớn nhất có thể của một dãy hợp lệ.

Ví dụ

2 2
100 1 2
100 1 1

200

Nguồn

USACO 2019 December Contest, Platinum - Greedy Pie Eaters: https://usaco.org/index.php?page=viewproblem2&cpid=972

Tác giả: Benjamin Qi.

Tuyết đã phủ xuống trang trại, và cũng như vào đầu mỗi mùa đông, Bessie đang xây một cô bò tuyết! Phần lớn thời gian, Bessie cố gắng làm cho tác phẩm điêu khắc giống bò thật nhất có thể. Tuy nhiên, năm nay với cảm hứng nghệ thuật, cô quyết định đi theo một hướng trừu tượng hơn và xây tác phẩm điêu khắc theo hình một cái cây, gồm \(N\) quả cầu tuyết (\(1 \leq N \leq 10^5\)) được nối bằng \(N-1\) nhánh, mỗi nhánh nối một cặp quả cầu tuyết sao cho giữa mọi cặp quả cầu tuyết đều có một đường đi duy nhất.

Bessie đã gắn một chiếc mũi lên một trong các quả cầu tuyết, vì vậy nó biểu thị đầu của cô bò tuyết trừu tượng. Cô đánh số quả cầu này là 1. Để tác phẩm bắt mắt hơn, cô dự định nhuộm một số quả cầu tuyết bằng các màu khác nhau theo phong cách nghệ thuật: đổ thuốc nhuộm màu vào những thùng sữa cũ rồi hắt chúng lên tác phẩm. Các màu được nhận diện bằng những số nguyên trong phạm vi \(1 \ldots 10^5\), và Bessie có nguồn cung không giới hạn các xô thuốc nhuộm cho mọi màu có thể có.

Khi Bessie hắt một xô thuốc nhuộm lên một quả cầu tuyết, tất cả các quả cầu tuyết trong cây con của nó cũng bị hắt cùng màu thuốc nhuộm (quả cầu tuyết \(y\) nằm trong cây con của quả cầu tuyết \(x\) nếu \(x\) nằm trên đường đi từ \(y\) đến quả cầu tuyết làm đầu). Bằng cách hắt từng màu hết sức cẩn thận, Bessie đảm bảo rằng tất cả những màu từng được hắt lên một quả cầu tuyết vẫn sẽ nhìn thấy được. Ví dụ, nếu một quả cầu tuyết đã có các màu \([1,2,3]\) và Bessie hắt màu \(4\) lên nó, sau đó quả cầu tuyết sẽ có các màu \([1,2,3,4]\).

Sau khi hắt màu lên các quả cầu tuyết một số lần, Bessie cũng có thể muốn biết một phần của cô bò tuyết có bao nhiêu màu sắc. "Độ sặc sỡ" của một quả cầu tuyết \(x\) bằng số màu phân biệt \(c\) mà quả cầu tuyết \(x\) được nhuộm màu \(c\). Nếu Bessie hỏi bạn về quả cầu tuyết \(x\), bạn phải trả lời tổng độ sặc sỡ của tất cả các quả cầu tuyết trong cây con của \(x\).

Hãy giúp Bessie tìm độ sặc sỡ của cô bò tuyết tại một số thời điểm nhất định.

Phân nhóm

\(Q\) được định nghĩa bên dưới.

• Các test 2–3 thỏa mãn \(N \leq 10^2\), \(Q \leq 2\cdot 10^2\).
• Các test 4–6 thỏa mãn \(N \leq 10^3\), \(Q \leq 2\cdot 10^3\).

Dữ liệu vào

Dòng đầu tiên chứa \(N\) và số truy vấn \(Q\) (\(1 \leq Q \leq 10^5\)).

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 nhánh nối các quả cầu tuyết \(a\) và \(b\) (\(1 \leq a,b \leq N\)).

Cuối cùng, mỗi dòng trong \(Q\) dòng cuối chứa một truy vấn. Một truy vấn có dạng

1 x c

cho biết Bessie hắt một xô nước ép màu \(c\) lên quả cầu tuyết \(x\), tô màu tất cả các quả cầu tuyết trong cây con của \(x\). Một dòng có dạng

2 x

là truy vấn tổng độ sặc sỡ của tất cả các quả cầu tuyết trong cây con của \(x\). Tất nhiên, \(1 \leq x \leq N\) và \(1 \leq c \leq 10^5\).

Dữ liệu ra

Với mỗi truy vấn loại 2, in tổng độ sặc sỡ trong cây con tương ứng.

Lưu ý rằng bạn nên sử dụng số nguyên 64 bit để tránh tràn số.

Ví dụ

5 18
1 2
1 3
3 4
3 5
1 4 1
2 1
2 2
2 3
2 4
2 5
1 5 1
2 1
2 2
2 3
2 4
2 5
1 1 1
2 1
2 2
2 3
2 4
2 5

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

Nguồn

USACO 2019 December Contest, Platinum - Bessie's Snow Cow: https://usaco.org/index.php?page=viewproblem2&cpid=973

Tác giả: Michael Cao và Benjamin Qi.

Nhân dịp năm mới, Nông dân John quyết định tặng các cô bò một cây tìm kiếm nhị phân (BST) mang không khí lễ hội!

Để sinh BST, FJ bắt đầu với một hoán vị \(a=\{a_1,a_2,\ldots,a_N\}\) của các số nguyên \(1 \ldots N\), trong đó \(N \leq 300\). Sau đó, ông chạy mã giả sau với hai tham số \(1\) và \(N\).

generate(l,r):
  nếu l > r, trả về cây con rỗng;
  x = argmin_{l <= i <= r} a_i; // chỉ số của a_i nhỏ nhất trong {a_l,...,a_r}
  trả về một BST có x là gốc,
    generate(l,x-1) là cây con trái,
    generate(x+1,r) là cây con phải;

Ví dụ, hoán vị \(\{3,2,5,1,4\}\) sinh ra BST sau:

    4
   / \
  2   5
 / \
1   3

Gọi \(d_i(a)\) là độ sâu của nút \(i\) trong cây tương ứng với \(a\), nghĩa là số nút trên đường đi từ \(a_i\) đến gốc. Trong ví dụ trên, \(d_4(a)=1\), \(d_2(a)=d_5(a)=2\) và \(d_1(a)=d_3(a)=3\).

Số nghịch thế của \(a\) bằng số cặp số nguyên \((i,j)\) sao cho \(1 \leq i<j \leq N\) và \(a_i>a_j\). Những cô bò biết rằng \(a\) mà FJ sẽ dùng để sinh BST có đúng \(K\) nghịch thế (\(0 \leq K \leq \frac{N(N-1)}{2}\)). Xét tất cả các \(a\) thỏa mãn điều kiện này, với mỗi \(1 \leq i \leq N\), hãy tính phần dư khi \(\sum_ad_i(a)\) được chia cho \(M\).

Dữ liệu vào

Dòng duy nhất của dữ liệu vào gồm ba số nguyên \(N\), \(K\) và \(M\), cách nhau bởi dấu cách, theo sau là một ký tự xuống dòng. \(M\) là một số nguyên tố trong phạm vi \([10^8,10^9+9]\).

Dữ liệu ra

In \(N\) số nguyên cách nhau bởi dấu cách, biểu thị \(\sum_ad_i(a)\pmod{M}\) với mỗi \(1 \leq i \leq N\).

Phân nhóm

• Các test 3–4 thỏa mãn \(N \leq 8\).
• Các test 5–7 thỏa mãn \(N \leq 20\).
• Các test 8–10 thỏa mãn \(N \leq 50\).

Ví dụ

3 0 192603497

1 2 3

3 1 144408983

3 4 4

Nguồn

USACO 2019 December Contest, Platinum - Tree Depth: https://usaco.org/index.php?page=viewproblem2&cpid=974

Tác giả: Yinzhan Xu.