USACO 2025 - Tháng 1 - Hạng Bạch Kim

Bessie có một đồ thị vô hướng đơn với các đỉnh được đánh số \(1\dots N\) (\(2\le N\le 750\)). Cô sinh một thứ tự duyệt theo chiều sâu (DFS) của đồ thị bằng cách gọi hàm \(\texttt{dfs}(1)\), được định nghĩa bởi đoạn mã C++ sau. Mỗi danh sách kề (\(\texttt{adj}[i]\) với mọi \(1\le i\le N\)) có thể được hoán vị tùy ý trước khi bắt đầu duyệt theo chiều sâu, nên một đồ thị có thể có nhiều thứ tự DFS khả dĩ.

vector<bool> vis(N + 1);
vector<vector<int>> adj(N + 1);  // adjacency list
vector<int> dfs_order;

void dfs(int x) {
    if (vis[x]) return;
    vis[x] = true;
    dfs_order.push_back(x);
    for (int y : adj[x]) dfs(y);
}

Bạn được cho trạng thái ban đầu của đồ thị cũng như chi phí để thay đổi trạng thái của mỗi cạnh. Cụ thể, với mọi cặp đỉnh \((i,j)\) thỏa mãn \(1\le i<j\le N\), bạn được cho một số nguyên \(a_{i,j}\) (\(0<|a_{i,j}|\le 1000\)) sao cho:

• Nếu \(a_{i,j}>0\), cạnh \((i,j)\) hiện không có trong đồ thị và có thể được thêm vào với chi phí \(a_{i,j}\).
• Nếu \(a_{i,j}<0\), cạnh \((i,j)\) hiện có trong đồ thị và có thể được xóa với chi phí \(-a_{i,j}\).

Hãy xác định tổng chi phí nhỏ nhất để thay đổi đồ thị sao cho \([1,2\dots,N]\) là một thứ tự DFS khả dĩ.

Dữ liệu vào

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

Tiếp theo là \(N-1\) dòng. Dòng thứ \(j-1\) chứa \(a_{1,j}, a_{2,j}, \dots, a_{j-1,j}\), cách nhau bởi dấu cách.

Dữ liệu ra

Chi phí nhỏ nhất để thay đổi đồ thị sao cho \([1,2,\dots, N]\) là một thứ tự DFS khả dĩ.

Ví dụ

4
1
2 3
40 6 11

10

5
-1
10 -2
10 -7 10
-6 -4 -5 10

5

4
-1
-2 300
4 -5 6

9

Phân nhóm

• Inputs 4-9: Mọi \(a_{i,j}>0\).
• Inputs 10-16: \(N\le 50\).
• Inputs 17-23: Không có ràng buộc bổ sung.

Nguồn

USACO 2025 January Contest, Platinum — DFS Order

Đề bài: https://usaco.org/index.php?page=viewproblem2&cpid=1476

Tác giả đề: Benjamin Qi

Bessie đang thử nghiệm một thiết bị cấy ghép móng mạnh mẽ có khả năng tạo ra những sóng xung kích khổng lồ. Trước mặt cô có \(N\) (\(2 \leq N \leq 10^5\)) viên gạch xếp thành một hàng, lần lượt cần công suất ít nhất \(p_0,p_1,\dots,p_{N-1}\) để phá vỡ (\(0 \leq p_i \leq 10^{18}\)).

Bessie có thể tạo công suất bằng cách đấm vào một viên gạch cụ thể, nhưng do tính chất kỳ lạ của thiết bị cấy ghép, cú đấm sẽ không tạo ra công suất nào lên chính viên gạch cô đấm. Thay vào đó, nếu cô chọn đấm viên gạch \(x\) một lần, với \(x\) là số nguyên trong \([0,N-1]\), nó tạo ra công suất \(|i-x|\) lên viên gạch \(i\) với mọi số nguyên \(i\) trong đoạn \([0,N-1]\). Công suất này cũng được cộng dồn, nên tác dụng công suất \(2\) hai lần lên một viên gạch sẽ tạo tổng công suất \(4\) lên viên gạch đó.

Hãy xác định số cú đấm ít nhất cần thiết để phá vỡ tất cả các viên gạch.

Dữ liệu vào

Dòng đầu tiên chứa \(T\) (\(1 \leq T \leq 100\)), biểu diễn số bộ test.

Dòng \(2t\) chứa một số nguyên \(N\), là số viên gạch trong bộ test \(t\).

Dòng \(2t+1\) chứa \(N\) số \(p_0,p_1, \ldots, p_{N-1}\) cách nhau bởi dấu cách, biểu diễn viên gạch \(i\) cần công suất \(p_i\) để bị phá vỡ.

Đảm bảo tổng tất cả các giá trị \(N\) trong một input không vượt quá \(5\cdot 10^5\).

Dữ liệu ra

In \(T\) dòng, dòng thứ \(i\) là đáp án của bộ test thứ \(i\).

Ví dụ

6
5
0 2 4 5 8
5
6 5 4 5 6
5
1 1 1 1 1
5
12 10 8 6 4
7
6 1 2 3 5 8 13
2
1000000000000000000 1000000000000000000

2
3
2
4
4
2000000000000000000

Phân nhóm

• Input 2: Mọi \(p_i\) đều bằng nhau.
• Inputs 3-6: \(N\le 100\).
• Inputs 7-14: Không có ràng buộc bổ sung.

Nguồn

USACO 2025 January Contest, Platinum — Shock Wave

Đề bài: https://usaco.org/index.php?page=viewproblem2&cpid=1477

Tác giả đề: Suhas Nagar

Khu vườn của Bessie có \(N\) cây được đánh số từ \(1\) đến \(N\) (\(2\leq N\leq 5\cdot 10^5\)) theo thứ tự từ trái sang phải. Bessie biết rằng cây \(i\) cần ít nhất \(w_i\) (\(0\leq w_i \leq 10^6\)) đơn vị nước.

Bessie có một hệ thống tưới tiêu rất đặc biệt với \(N-1\) kênh dẫn nước, được đánh số từ \(1\) đến \(N-1\). Mỗi kênh \(i\) có một chi phí đơn vị tương ứng \(c_i\) (\(1\le c_i\le 10^6\)), sao cho Bessie có thể trả \(c_i k\) để cung cấp cho mỗi cây \(i\) và \(i+1\) đúng \(k\) đơn vị nước, trong đó \(k\) là một số nguyên không âm.

Bessie bận rộn và có thể không có thời gian sử dụng tất cả các kênh. Với mỗi \(2\leq i \leq N\), hãy tính chi phí nhỏ nhất cần thiết để tưới các cây từ \(1\) đến \(i\) chỉ sử dụng \(i-1\) kênh đầu tiên.

Dữ liệu vào

Dòng đầu tiên chứa một số nguyên dương \(N\).

Dòng thứ hai chứa \(N\) số nguyên cách nhau bởi dấu cách \(w_1, \ldots, w_N\).

Dòng thứ ba chứa \(N-1\) số nguyên cách nhau bởi dấu cách \(c_1, \ldots, c_{N-1}\).

Dữ liệu ra

In \(N-1\) số nguyên, mỗi số trên một dòng. Số nguyên thứ \((i-1)\) phải chứa chi phí nhỏ nhất để tưới \(i\) cây đầu tiên bằng \(i-1\) kênh đầu tiên.

Ví dụ

3
39 69 33
30 29

2070
2127

3
33 82 36
19 1

1558
676

8
35 89 44 1 35 3 62 50
7 86 94 62 63 9 49

623
4099
4114
6269
6272
6827
8827

Phân nhóm

• Input 4: \(N \leq 200\), và mọi \(w_i \leq 200\).
• Inputs 5-6: Mọi \(w_i \leq 200\).
• Inputs 7-10: \(N \leq 5000\).
• Inputs 11-14: Mọi \(w_i\) và \(c_i\) được sinh độc lập và ngẫu nhiên đều.
• Inputs 15-19: Không có ràng buộc bổ sung.

Nguồn

USACO 2025 January Contest, Platinum — Watering the Plants

Đề bài: https://usaco.org/index.php?page=viewproblem2&cpid=1478

Tác giả đề: Benjamin Qi