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

Bessie có một tập các đồ thị vô hướng liên thông \(G_1,G_2,\ldots,G_K\) (\(2\le K\le 5\cdot10^4\)). Với mỗi \(1\le i\le K\), đồ thị \(G_i\) có đúng \(N_i\) đỉnh (\(N_i\ge2\)), được đánh số \(1\ldots N_i\), và \(M_i\) cạnh (\(M_i\ge N_i-1\)). Mỗi \(G_i\) có thể chứa khuyên, nhưng không có nhiều cạnh nối cùng một cặp đỉnh.

Elsie tạo một đồ thị vô hướng mới \(G\) có \(N_1\cdot N_2\cdots N_K\) đỉnh. Mỗi đỉnh được gắn nhãn bởi một bộ \(K\) phần tử \((j_1,j_2,\ldots,j_K)\), trong đó \(1\le j_i\le N_i\). Trong \(G\), hai đỉnh \((j_1,j_2,\ldots,j_K)\) và \((k_1,k_2,\ldots,k_K)\) được nối bởi một cạnh khi, với mọi \(1\le i\le K\), hai đỉnh \(j_i\) và \(k_i\) được nối bởi một cạnh trong \(G_i\).

Khoảng cách giữa hai đỉnh thuộc cùng một thành phần liên thông của \(G\) là số cạnh ít nhất trên một đường đi giữa chúng. Hãy tính tổng khoảng cách từ đỉnh \((1,1,\ldots,1)\) đến mọi đỉnh nằm cùng thành phần liên thông với nó trong \(G\), lấy modulo \(10^9+7\).

Dữ liệu vào

Dòng đầu tiên chứa \(K\), số lượng đồ thị.

Mô tả mỗi đồ thị bắt đầu bằng \(N_i\) và \(M_i\) trên một dòng, tiếp theo là \(M_i\) cạnh. Các đồ thị liên tiếp được ngăn cách bằng dòng trống cho dễ đọc. Bảo đảm \(\sum N_i\le10^5\) và \(\sum M_i\le2\cdot10^5\).

Dữ liệu ra

In tổng khoảng cách từ đỉnh \((1,1,\ldots,1)\) đến mọi đỉnh có thể đi tới từ nó, lấy modulo \(10^9+7\).

Phân nhóm

• Các test 3-4 thỏa mãn \(\prod N_i\le300\).
• Các test 5-10 thỏa mãn \(\sum N_i\le300\).
• Các test 11-20 không có ràng buộc bổ sung.

Ví dụ

2

2 1
1 2

4 4
1 2
2 3
3 4
4 1

4

3

4 4
1 2
2 3
3 1
3 4

6 5
1 2
2 3
3 4
4 5
5 6

7 7
1 2
2 3
3 4
4 5
5 6
6 7
7 1

706

Nguồn

USACO 2021 January Contest, Platinum - Sum of Distances: https://usaco.org/index.php?page=viewproblem2&cpid=1092

Tác giả: Benjamin Qi.

Đồng cỏ của Farmer John được xem là một lưới ô vuông hai chiều \(N\times M\) (\(2\le N\le10^9\), \(2\le M\le2\cdot10^5\)). Ô ở hàng thứ \(x\) tính từ trên xuống và cột thứ \(y\) tính từ bên phải được ký hiệu là \((x,y)\), với \(x\in[1,N]\) và \(y\in[1,M]\). Ngoài ra, với mọi \(y\in[1,M]\), cột thứ \(y\) có chi phí \(c_y\) (\(1\le c_y\le10^9\)).

Bessie bắt đầu tại ô \((1,1)\). Nếu đang ở ô \((x,y)\), cô có thể thực hiện một trong các thao tác sau:

• Nếu \(y<M\), đi sang cột tiếp theo, tức tăng \(y\) thêm một, với chi phí \(x^2\).
• Nếu \(x<N\), đi xuống hàng tiếp theo, tức tăng \(x\) thêm một, với chi phí \(c_y\).

Cho \(Q\) truy vấn độc lập (\(1\le Q\le2\cdot10^5\)), mỗi truy vấn có dạng \((x_i,y_i)\) với \(x_i\in[1,N]\) và \(y_i\in[1,M]\). Với mỗi truy vấn, hãy tính tổng chi phí nhỏ nhất để Bessie đi từ \((1,1)\) đến \((x_i,y_i)\).

Dữ liệu vào

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

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

Dòng thứ ba chứa \(Q\).

\(Q\) dòng cuối, mỗi dòng chứa hai số nguyên \(x_i\) và \(y_i\), cách nhau bởi dấu cách.

Dữ liệu ra

In \(Q\) dòng, lần lượt chứa đáp án cho từng truy vấn. Các giá trị có thể lớn và cần kiểu số nguyên 64 bit, chẳng hạn long long trong C/C++.

Phân nhóm

• Các test 1-3 thỏa mãn \(N,M\le2000\).
• Các test 4-8 thỏa mãn \(c_2>c_3>\cdots>c_M\).
• Các test 9-15 thỏa mãn \(N\le2\cdot10^5\).
• Các test 16-20 không có ràng buộc bổ sung.

Ví dụ

5 4
1 100 100 20
20
1 1
2 1
3 1
4 1
5 1
1 2
2 2
3 2
4 2
5 2
1 3
2 3
3 3
4 3
5 3
1 4
2 4
3 4
4 4
5 4

0
1
2
3
4
1
5
11
19
29
2
9
20
35
54
3
13
29
49
69

    1  2  3  4
  *--*--*--*--*
1 | 0| 1| 2| 3|
  *--*--*--*--*
2 | 1| 5| 9|13|
  *--*--*--*--*
3 | 2|11|20|29|
  *--*--*--*--*
4 | 3|19|35|49|
  *--*--*--*--*
5 | 4|29|54|69|
  *--*--*--*--*

Nguồn

USACO 2021 January Contest, Platinum - Minimum Cost Paths: https://usaco.org/index.php?page=viewproblem2&cpid=1093

Tác giả: Benjamin Qi.

Bessie vừa được tặng một bộ dụng cụ vẽ. Tấm vải được biểu diễn bằng một hình chữ nhật \(N\times M\) ô, với các hàng đánh số \(1\ldots N\) từ trên xuống và các cột đánh số \(1\ldots M\) từ trái sang phải (\(1\le N,M\le1000\)). Sau khi tô, màu của mỗi ô được biểu diễn bằng một chữ cái in hoa từ A đến Z. Ban đầu mọi ô đều chưa có màu và mỗi ô không được tô quá một lần.

Bessie đã chỉ định màu mong muốn cho từng ô. Trong một nét cọ, cô có thể tô một tập ô bằng cùng một màu nếu tập đó tạo thành một thành phần liên thông, tức từ một ô bất kỳ trong tập có thể đi tới mọi ô khác qua một dãy ô kề. Hai ô được coi là kề nhau nếu có chung một cạnh.

Ví dụ, tấm vải \(3\times3\) sau:

AAB
BBA
BBB

có thể được tô bằng bốn nét như sau, và không thể dùng ít hơn:

...    ..B    AAB    AAB    AAB
... -> ... -> ... -> BB. -> BBA
...    ...    ...    BBB    BBB

Là một nghệ sĩ tiên phong, Bessie sẽ chỉ tô một hình chữ nhật con của tấm vải. Cô đang xét \(Q\) ứng viên (\(1\le Q\le1000\)), mỗi ứng viên được mô tả bởi bốn số nguyên \(x_1,y_1,x_2,y_2\). Hình chữ nhật con gồm mọi ô có hàng từ \(x_1\) đến \(x_2\) và cột từ \(y_1\) đến \(y_2\), kể cả hai đầu.

Với mỗi hình chữ nhật con ứng viên, hãy tính số nét cọ ít nhất để tô mỗi ô bên trong đúng màu mong muốn, đồng thời giữ mọi ô bên ngoài chưa tô. Bessie không thực sự tô trong quá trình này, nên đáp án của các ứng viên độc lập với nhau.

Lưu ý: Giới hạn thời gian của bài cao hơn mức mặc định 50%, và giới hạn bộ nhớ là 512 MB, gấp đôi mức mặc định.

Dữ liệu vào

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

\(N\) dòng tiếp theo, mỗi dòng chứa một xâu gồm \(M\) chữ cái in hoa, biểu diễn màu mong muốn của một hàng trên tấm vải.

\(Q\) dòng tiếp theo, mỗi dòng chứa bốn số nguyên \(x_1,y_1,x_2,y_2\), cách nhau bởi dấu cách, mô tả một hình chữ nhật con ứng viên (\(1\le x_1\le x_2\le N\), \(1\le y_1\le y_2\le M\)).

Dữ liệu ra

Với mỗi ứng viên trong \(Q\) ứng viên, in đáp án trên một dòng mới.

Phân nhóm

• Các test 1-2 thỏa mãn \(N,M\le50\).
• Trong các test 3-5, tấm vải không chứa chu trình đơn sắc. Cụ thể, không tồn tại một dãy ô phân biệt \(c_1,c_2,c_3,\ldots,c_k\) thỏa mãn đồng thời:
• \(k>2\);
• mọi ô \(c_1,\ldots,c_k\) có cùng màu mong muốn;
• \(c_i\) kề \(c_{i+1}\) với mọi \(1\le i<k\);
• \(c_k\) kề \(c_1\).
• Trong các test 6-8, mỗi thành phần liên thông gồm các ô có cùng màu mong muốn có thể nằm trọn trong một hình vuông \(2\times2\) có cạnh song song với các trục tọa độ.
• Trong các test 9-11, mỗi thành phần liên thông như vậy có thể nằm trọn trong một hình vuông \(3\times3\) có cạnh song song với các trục tọa độ.
• Các test 12-20 không có ràng buộc bổ sung.

Tấm vải \(3\times3\) ở trên có một chu trình đơn sắc là bốn ô B ở góc dưới bên trái. Nó không thỏa mãn điều kiện của các test 6-8 vì thành phần gồm năm ô B không nằm trọn trong hình vuông \(2\times2\). Tấm vải \(3\times3\) này thỏa mãn điều kiện của các test 9-11.

Ví dụ

4 8 9
ABBAAAAA
ABAAAABA
CAADABBA
AAAAAAAA
1 1 4 8
3 5 3 8
1 3 2 4
1 4 2 5
1 1 3 3
4 4 4 4
2 6 4 8
3 5 4 6
1 6 3 8

6
3
2
1
4
1
3
2
2

Nguồn

USACO 2021 January Contest, Platinum - Paint by Letters: https://usaco.org/index.php?page=viewproblem2&cpid=1094

Tác giả: Andi Qu.