| # | Bài tập | Điểm | Thời gian: | Giới hạn bộ nhớ |
|---|---|---|---|---|
| 1 | USACO 2019 - Fine Dining | 100 (p) | 4.0s | 512M |
| 2 | USACO 2019 - Cowpatibility | 100 (p) | 4.0s | 512M |
| 3 | USACO 2019 - Teamwork | 100 (p) | 4.0s | 512M |
Sau một ngày dài, những cô bò đang trở về chuồng, vừa mệt vừa đói.
Trang trại gồm \(N\) đồng cỏ (\(2 \leq N \leq 50,000\)), được đánh số thuận tiện từ \(1 \dots N\). Tất cả các cô bò đều muốn đi đến chuồng ở đồng cỏ \(N\). Mỗi đồng cỏ trong số \(N-1\) đồng cỏ còn lại có một cô bò. Các cô bò có thể di chuyển giữa các đồng cỏ qua một tập hợp gồm \(M\) đường mòn hai chiều (\(1 \leq M \leq 100,000\)). Đường mòn thứ \(i\) nối hai đồng cỏ \(a_i\) và \(b_i\), đồng thời mất \(t_i\) đơn vị thời gian để đi qua. Mọi cô bò đều có thể đến chuồng qua một dãy đường mòn.
Vì đang đói, các cô bò muốn cân nhắc dừng lại ăn trên đường về. Thật tiện lợi, \(K\) đồng cỏ có những kiện cỏ khô thơm ngon (\(1 \leq K \leq N\)), trong đó kiện cỏ khô thứ \(i\) có độ ngon \(y_i\). Mỗi cô bò sẵn sàng dừng lại tại một kiện cỏ khô duy nhất trên đường đến chuồng, nhưng chỉ khi thời gian tăng thêm trên lộ trình của cô không vượt quá độ ngon của kiện cỏ khô mà cô ghé ăn. Lưu ý rằng mỗi cô bò chỉ "chính thức" ghé nhiều nhất một kiện cỏ khô để ăn, dù lộ trình của cô có thể đi qua những đồng cỏ khác cũng có kiện cỏ khô; cô chỉ đơn giản là bỏ qua chúng.
Dòng đầu tiên chứa ba số nguyên \(N\), \(M\) và \(K\) cách nhau bởi dấu cách. Mỗi dòng trong \(M\) dòng tiếp theo chứa ba số nguyên \(a_i\), \(b_i\) và \(t_i\), mô tả một đường mòn giữa hai đồng cỏ \(a_i\) và \(b_i\) cần \(t_i\) đơn vị thời gian để đi qua (\(a_i\) và \(b_i\) khác nhau, còn \(t_i\) là số nguyên dương không vượt quá \(10^4\)).
\(K\) dòng tiếp theo, mỗi dòng mô tả một kiện cỏ khô bằng hai số nguyên: chỉ số của đồng cỏ chứa nó và độ ngon của nó (một số nguyên dương không vượt quá \(10^9\)). Một đồng cỏ có thể chứa nhiều kiện cỏ khô.
Dữ liệu ra gồm \(N-1\) dòng. Dòng \(i\) chứa số nguyên duy nhất \(1\) nếu cô bò ở đồng cỏ \(i\) có thể ghé và ăn một kiện cỏ khô trên đường đến chuồng, và chứa \(0\) nếu không thể.
Ví dụ 1
4 5 1
1 4 10
2 1 20
4 2 3
2 3 5
4 3 2
2 71
1
1Trong ví dụ này, cô bò ở đồng cỏ 3 nên dừng lại ăn vì lộ trình của cô chỉ tăng thêm 6 (từ 2 lên 8), và mức tăng này không vượt quá độ ngon 7 của kiện cỏ khô. Cô bò ở đồng cỏ 2 hiển nhiên nên ăn cỏ khô tại đồng cỏ 2 vì việc này không làm thay đổi lộ trình tối ưu của cô. Trường hợp của cô bò ở đồng cỏ 1 khá thú vị, vì thoạt nhìn lộ trình tối ưu của cô (có độ dài 10) dường như sẽ tăng quá nhiều để việc dừng lại ăn cỏ là hợp lý. Tuy nhiên, cô thực sự có một lộ trình khiến việc dừng lại ăn cỏ trở nên có lợi: đi đến đồng cỏ 4, rồi đến đồng cỏ 2 (ăn cỏ khô), sau đó quay lại đồng cỏ 4.
Đề bài gốc: USACO 2018 December Contest, Gold — Fine Dining
Tác giả: Dhruv Rohatgi
Hóa ra có một yếu tố quan trọng hơn hẳn mọi yếu tố khác khi xác định liệu hai cô bò có hợp nhau để trở thành bạn bè hay không: chúng có thích những hương vị kem giống nhau không!
Mỗi cô trong số \(N\) cô bò của Nông dân John (\(2 \leq N \leq 50,000\)) đã liệt kê năm hương vị kem yêu thích của mình. Để danh sách này ngắn gọn, mỗi hương vị có thể có được biểu diễn bằng một mã số nguyên dương không vượt quá \(10^6\). Hai cô bò tương hợp nếu danh sách của chúng có ít nhất một hương vị kem chung.
Hãy xác định số cặp bò KHÔNG tương hợp.
Dòng đầu tiên chứa \(N\). Mỗi dòng trong \(N\) dòng tiếp theo chứa 5 số nguyên (đôi một khác nhau), biểu diễn các hương vị kem yêu thích của một cô bò.
In ra số cặp bò không tương hợp.
Ví dụ 1
4
1 2 3 4 5
1 2 3 10 8
10 9 8 7 6
50 60 70 80 904Ở đây, cô bò 4 không tương hợp với bất kỳ cô bò nào trong số các cô bò 1, 2 và 3; ngoài ra, cô bò 1 và cô bò 3 cũng không tương hợp.
Đề bài gốc: USACO 2018 December Contest, Gold — Cowpatibility
Tác giả: Yang Liu
Vào dịp lễ yêu thích, Nông dân John muốn gửi quà cho bạn bè. Vì không giỏi gói quà, ông muốn nhờ những cô bò của mình giúp đỡ. Như bạn có thể đoán, bản thân những cô bò cũng chẳng giỏi gói quà hơn là bao — một bài học mà Nông dân John sắp phải cay đắng nhận ra.
\(N\) cô bò của Nông dân John (\(1 \leq N \leq 10^4\)) đều đang đứng thành một hàng, được đánh số thuận tiện từ \(1 \ldots N\) theo thứ tự. Cô bò \(i\) có mức kỹ năng gói quà \(s_i\). Các mức kỹ năng này có thể chênh lệch khá nhiều, vì vậy FJ quyết định chia các cô bò thành những đội. Một đội có thể gồm bất kỳ nhóm nào chứa không quá \(K\) cô bò liên tiếp (\(1 \leq K \leq 10^3\)), và không cô bò nào được thuộc nhiều hơn một đội. Vì các cô bò học hỏi lẫn nhau, mức kỹ năng của mỗi cô bò trong một đội có thể được thay bằng mức kỹ năng của cô bò giỏi nhất trong đội đó.
Hãy giúp FJ xác định tổng mức kỹ năng lớn nhất có thể đạt được nếu ông lập đội một cách tối ưu.
Dòng đầu tiên chứa \(N\) và \(K\). \(N\) dòng tiếp theo chứa mức kỹ năng của \(N\) cô bò theo thứ tự chúng đang đứng. Mỗi mức kỹ năng là một số nguyên dương không vượt quá \(10^5\).
In ra tổng mức kỹ năng lớn nhất mà FJ có thể đạt được bằng cách chia những nhóm bò liên tiếp thích hợp thành các đội.
Ví dụ 1
7 3
1
15
7
9
2
5
1084Trong ví dụ này, phương án tối ưu là nhóm ba cô bò đầu tiên thành một đội và ba cô bò cuối cùng thành một đội, còn cô bò ở giữa ở trong một đội riêng (hãy nhớ rằng đội có ít hơn \(K\) thành viên vẫn hợp lệ). Điều này thực chất nâng mức kỹ năng của 7 cô bò thành 15, 15, 15, 9, 10, 10, 10, có tổng bằng 84.
Đề bài gốc: USACO 2018 December Contest, Gold — Teamwork
Tác giả: Brian Dean