| # | Bài tập | Điểm | Thời gian: | Giới hạn bộ nhớ |
|---|---|---|---|---|
| 1 | USACO 2019 - Redistricting | 100 (p) | 4.0s | 512M |
| 2 | USACO 2019 - Exercise Route | 100 (p) | 4.0s | 512M |
| 3 | USACO 2019 - Train Tracking 2 | 100 (p) | 4.0s | 512M |
Siêu đô thị bò Bovinopolis đang phân chia lại các khu vực bầu cử! Đây luôn là một quá trình chính trị gây tranh cãi giữa hai giống bò lớn (Holstein và Guernsey) sinh sống tại đó, bởi cả hai giống đều muốn bảo đảm mình duy trì đủ ảnh hưởng trong chính quyền Bovinopolis.
Vùng đô thị Bovinopolis mở rộng gồm một dãy \(N\) đồng cỏ (\(1 \leq N \leq 3 \cdot 10^5\)), mỗi đồng cỏ có đúng một con bò thuộc giống Holstein hoặc Guernsey.
Chính quyền Bovinopolis muốn chia vùng đô thị mở rộng thành một số khu vực liên tiếp sao cho mỗi khu vực chứa không quá \(K\) đồng cỏ (\(1 \leq K \leq N\)), và mỗi đồng cỏ thuộc đúng một khu vực. Vì chính quyền hiện do giống Holstein kiểm soát, họ muốn tìm một cách phân chia lại sao cho số khu vực có đa số Guernsey hoặc có kết quả hòa là nhỏ nhất (một khu vực hòa nếu số bò Guernsey bằng số bò Holstein).
Một liên minh những con bò Guernsey đang lo ngại muốn tìm hiểu mức thiệt hại mà việc phân chia lại của chính quyền có thể gây ra. Hãy giúp họ xác định, trong trường hợp xấu nhất, số khu vực tối thiểu có đa số Guernsey hoặc có kết quả hòa.
Dòng đầu tiên chứa hai số nguyên \(N\) và \(K\) cách nhau bởi dấu cách. Dòng thứ hai chứa một xâu có độ dài \(N\). Mỗi ký tự là H hoặc G, tương ứng với Holstein hoặc Guernsey.
In ra số khu vực có đa số Guernsey hoặc có kết quả hòa nhỏ nhất có thể.
Ví dụ 1
7 2
HGHGGHG3Đề bài gốc: USACO 2019 January Contest, Platinum — Redistricting
Tác giả: Dhruv Rohatgi
Cô bò Bessie nhận ra rằng mình cần tập thể dục nhiều hơn để giữ vóc dáng cân đối. Cô cần bạn giúp chọn các lộ trình tiềm năng quanh trang trại cho việc chạy bộ buổi sáng.
Trang trại gồm \(N\) cánh đồng (\(1 \leq N \leq 2 \cdot 10^5\)), được đánh số thuận tiện từ \(1 \ldots N\), và được nối với nhau một cách thuận tiện bởi một tập gồm \(M\) đường mòn hai chiều (\(1 \leq M \leq 2 \cdot 10^5\)). Vì là những sinh vật có thói quen, các cô bò thường chỉ sử dụng một tập con gồm \(N-1\) đường mòn nhất định cho mọi hoạt động di chuyển hằng ngày giữa các cánh đồng — chúng gọi đây là các đường mòn "tiêu chuẩn". Chỉ sử dụng các đường mòn tiêu chuẩn, ta vẫn có thể đi từ bất kỳ cánh đồng nào đến bất kỳ cánh đồng nào khác.
Để buổi chạy bộ sáng thú vị hơn, Bessie quyết định chọn một lộ trình có sử dụng một số đường mòn không tiêu chuẩn. Tuy nhiên, cô đã quá quen với các đường mòn tiêu chuẩn nên không muốn dùng quá nhiều đường mòn không tiêu chuẩn trên lộ trình. Sau khi suy nghĩ, cô quyết định một lộ trình tốt là một chu trình đơn (quay lại điểm xuất phát và không đi qua cánh đồng nào quá một lần) chứa đúng hai đường mòn không tiêu chuẩn.
Hãy giúp Bessie đếm số lộ trình tốt mà cô có thể sử dụng. Hai lộ trình được xem là giống nhau nếu chúng gồm cùng một tập đường mòn.
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_i\) và \(b_i\), mô tả hai đầu mút của một đường mòn. \(N-1\) đường mòn đầu tiên là các đường mòn tiêu chuẩn.
In ra tổng số lộ trình mà Bessie có thể muốn sử dụng.
Ví dụ 1
5 8
1 2
1 3
1 4
1 5
2 3
3 4
4 5
5 24Đề bài gốc: USACO 2019 January Contest, Platinum — Exercise Route
Tác giả: Dhruv Rohatgi
Mỗi ngày, đoàn tàu tốc hành chạy ngang qua trang trại. Tàu có \(N\) toa (\(1 \leq N \leq 10^5\)), mỗi toa mang một nhãn là số nguyên dương từ \(1\) đến \(10^9\); các toa khác nhau có thể mang cùng một nhãn.
Thông thường, Bessie quan sát đoàn tàu chạy qua và ghi lại nhãn của các toa. Nhưng hôm nay trời quá nhiều sương mù, Bessie không thể nhìn thấy bất kỳ nhãn nào! May mắn thay, cô đã lấy được các giá trị nhỏ nhất trên cửa sổ trượt của dãy nhãn toa tàu từ một nguồn đáng tin cậy trong thành phố. Cụ thể, cô có một số nguyên dương \(K\) và \(N-K+1\) số nguyên dương \(c_1, \dots, c_{N+1-K}\), trong đó \(c_i\) là nhãn nhỏ nhất trong các toa \(i, i+1, \dots, i+K-1\).
Hãy giúp Bessie tìm số cách gán nhãn cho mỗi toa sao cho phù hợp với các giá trị nhỏ nhất trên cửa sổ trượt. Vì số này có thể rất lớn, Bessie chấp nhận phần dư của nó theo modulo \(10^9 + 7\).
Thông tin của Bessie hoàn toàn đáng tin cậy; nói cách khác, dữ liệu bảo đảm có ít nhất một cách gán nhãn phù hợp.
Dòng đầu tiên chứa hai số nguyên \(N\) và \(K\) cách nhau bởi dấu cách. Các dòng tiếp theo chứa lần lượt các giá trị nhỏ nhất trên cửa sổ trượt \(c_1, \dots, c_{N+1-K}\), mỗi dòng một giá trị.
In ra một số nguyên duy nhất: số cách gán cho mỗi toa một số nguyên dương không vượt quá \(10^9\) sao cho nhãn nhỏ nhất trong các toa \(i, i+1, \dots, i+K-1\) là \(c_i\) với mọi \(1 \leq i \leq N-K+1\), lấy theo modulo \(10^9 + 7\).
Ví dụ 1
4 2
999999998
999999999
9999999983Đề bài gốc: USACO 2019 January Contest, Platinum — Train Tracking 2
Tác giả: Dhruv Rohatgi