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

Farmer John đã lắp đặt một hệ thống mới gồm \(N-1\) đường ống để vận chuyển sữa giữa \(N\) chuồng trong trại (\(2\le N\le50\,000\)), được đánh số thuận tiện từ \(1\ldots N\). Mỗi đường ống nối một cặp chuồng, và mọi chuồng đều được nối với nhau bằng các đường đi qua những đường ống.

FJ đang bơm sữa giữa \(K\) cặp chuồng (\(1\le K\le100\,000\)). Với cặp thứ \(i\), bạn được cho hai chuồng \(s_i\) và \(t_i\), là hai đầu mút của một đường đi mà sữa được bơm dọc theo với lưu lượng một đơn vị. FJ lo rằng một số chuồng có thể bị quá tải vì toàn bộ lượng sữa được bơm qua chúng, bởi một chuồng có thể đóng vai trò là điểm trung gian trên nhiều trong số \(K\) đường đi mà sữa đang được bơm dọc theo. Hãy giúp ông xác định lượng sữa lớn nhất được bơm qua một chuồng bất kỳ. Nếu sữa được bơm dọc theo đường đi từ \(s_i\) đến \(t_i\), lượng sữa đó được tính là đi qua cả hai chuồng đầu mút \(s_i\) và \(t_i\), cũng như mọi chuồng trên đường đi giữa chúng.

Dữ liệu vào

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

\(N-1\) dòng tiếp theo, mỗi dòng chứa hai số nguyên \(x\) và \(y\) (\(x\ne y\)), mô tả một đường ống giữa chuồng \(x\) và chuồng \(y\).

\(K\) dòng tiếp theo, mỗi dòng chứa hai số nguyên \(s\) và \(t\), mô tả hai chuồng đầu mút của một đường đi mà sữa đang được bơm qua.

Dữ liệu ra

In một số nguyên biểu thị lượng sữa lớn nhất được bơm qua một chuồng bất kỳ trong trại.

Ví dụ

5 10
3 4
1 5
4 2
5 4
5 4
5 4
3 5
4 3
4 3
1 3
3 5
5 4
1 5
3 4

9

Nguồn

USACO 2015 December Contest, Platinum - Max Flow: https://usaco.org/index.php?page=viewproblem2&cpid=576

Tác giả: Brian Dean.

Cô bò Bessie là một người rất hâm mộ các trò chơi bài, điều này khá đáng ngạc nhiên vì cô không có ngón cái đối diện. Đáng tiếc là không có con bò nào khác trong đàn là đối thủ giỏi. Thực tế, chúng chơi tệ đến mức luôn chơi theo một cách hoàn toàn có thể dự đoán! Dù vậy, việc tìm ra cách chiến thắng vẫn có thể là một thử thách đối với Bessie.

Bessie và cô bạn Elsie hiện đang chơi một trò bài đơn giản. Họ lấy một bộ gồm \(2N\) lá bài, được đánh số thuận tiện từ \(1\ldots2N\), rồi chia cho Bessie \(N\) lá và Elsie \(N\) lá. Sau đó, hai cô chơi \(N\) vòng; trong mỗi vòng, Bessie và Elsie đều đánh một lá bài. Ban đầu, người đánh lá bài lớn hơn giành được một điểm. Tuy nhiên, tại một thời điểm trong trò chơi, Bessie có thể quyết định đổi luật để trong phần còn lại của trò chơi, người đánh lá bài nhỏ hơn giành được một điểm. Bessie có thể chọn không dùng quyền này và giữ cả trò chơi ở chế độ "lá bài lớn hơn thắng", hoặc cô thậm chí có thể dùng quyền này ngay từ đầu để toàn bộ trò chơi tuân theo luật "lá bài nhỏ hơn thắng".

Biết rằng Bessie có thể dự đoán thứ tự Elsie sẽ đánh các lá bài, hãy xác định số điểm tối đa Bessie có thể giành được.

Dữ liệu vào

Dòng đầu tiên chứa giá trị \(N\) (\(2\le N\le50\,000\)).

\(N\) dòng tiếp theo chứa các lá bài mà Elsie sẽ đánh trong từng vòng liên tiếp của trò chơi. Lưu ý rằng từ thông tin này có thể dễ dàng xác định các lá bài của Bessie.

Dữ liệu ra

In một dòng chứa số điểm tối đa Bessie có thể ghi được.

Ví dụ

4
1
8
4
3

3

Nguồn

USACO 2015 December Contest, Platinum - High Card Low Card (Platinum): https://usaco.org/index.php?page=viewproblem2&cpid=577

Tác giả: Austin Bannister và Brian Dean.

Farmer John đang cố thuê các nhà thầu giúp sắp xếp lại trang trại, nhưng đến nay tất cả đều bỏ việc khi nhìn thấy chuỗi chỉ dẫn phức tạp mà FJ muốn họ làm theo. Phải tự mình hoàn thành dự án, ông nhận ra rằng quả thật mình có lẽ đã khiến dự án phức tạp hơn mức cần thiết. Hãy giúp ông làm theo các chỉ dẫn để hoàn tất việc nâng cấp trang trại.

Trang trại của FJ gồm \(N\) cánh đồng nằm thành một hàng, được đánh số thuận tiện từ \(1\ldots N\). Mỗi cánh đồng có thể chứa một số lượng kiện cỏ khô bất kỳ. Các chỉ dẫn của Farmer John gồm ba loại:

1. Với một đoạn cánh đồng liên tiếp cho trước, thêm một kiện cỏ khô mới vào mỗi cánh đồng.
2. Với một đoạn cánh đồng liên tiếp cho trước, xác định số kiện cỏ khô nhỏ nhất trong một cánh đồng thuộc đoạn đó.
3. Với một đoạn cánh đồng liên tiếp cho trước, đếm tổng số kiện cỏ khô bên trong đoạn đó.

Dữ liệu vào

Dòng đầu tiên chứa hai số nguyên dương \(N\) (\(1\le N\le200\,000\)) và \(Q\) (\(1\le Q\le100\,000\)).

Dòng tiếp theo chứa \(N\) số nguyên không âm, mỗi số không vượt quá \(100\,000\), cho biết số kiện cỏ khô ban đầu trong mỗi cánh đồng.

Mỗi dòng trong \(Q\) dòng tiếp theo chứa một chữ cái in hoa M, P hoặc S, tiếp theo là hai số nguyên dương \(A\) và \(B\) (\(1\le A\le B\le N\)), hoặc ba số nguyên dương \(A\), \(B\) và \(C\) (\(1\le A\le B\le N\); \(1\le C\le100\,000\)). Có ba số nguyên khi và chỉ khi chữ cái in hoa là P.

Nếu chữ cái là M, in số kiện cỏ khô nhỏ nhất trong đoạn cánh đồng từ \(A\ldots B\).

Nếu chữ cái là P, đặt thêm \(C\) kiện cỏ khô vào mỗi cánh đồng trong đoạn từ \(A\ldots B\).

Nếu chữ cái là S, in tổng số kiện cỏ khô trong đoạn cánh đồng từ \(A\ldots B\).

Dữ liệu ra

Với mỗi chỉ dẫn M hoặc S của FJ, in một dòng kết quả tương ứng.

Ví dụ

4 5
3 1 2 4
M 3 4
S 1 3
P 2 3 1
M 3 4
S 1 3

2
6
3
8

Nguồn

USACO 2015 December Contest, Platinum - Counting Haybales: https://usaco.org/index.php?page=viewproblem2&cpid=578

Tác giả: Nick Wu.