USACO 2024 - Tháng 12 - Hạng Bạch Kim - Bộ đề bài

#	Bài tập	Điểm	Thời gian:	Giới hạn bộ nhớ
1	USACO 2025 - All Pairs Similarity	100 (p)	4.0s	512M
2	USACO 2025 - It's Mooin' Time	100 (p)	4.0s	512M
3	USACO 2025 - Maximize Minimum Difference	100 (p)	4.0s	512M

1. USACO 2025 - All Pairs Similarity

Điểm: 100 (p) Thời gian: 4.0s Bộ nhớ: 512M Input: bàn phím Output: màn hình

Lưu ý: Giới hạn bộ nhớ của bài này là 512 MB, gấp đôi mức mặc định.

Mỗi cô trong số \(N\) cô bò của Farmer John (\(1\leq N\leq 5\cdot 10^5\)) được gán một xâu bit độ dài \(K\) không chứa toàn bit \(0\) (\(1\leq K\leq 20\)). Các cô bò khác nhau có thể được gán cùng một xâu bit.

Độ tương đồng Jaccard của hai xâu bit được định nghĩa là số bit \(1\) trong phép giao theo bit của chúng chia cho số bit \(1\) trong phép hợp theo bit của chúng. Ví dụ, độ tương đồng Jaccard của hai xâu bit \(\texttt{11001}\) và \(\texttt{11010}\) là \(2/4\).

Với mỗi cô bò, hãy in tổng độ tương đồng Jaccard giữa xâu bit của cô ấy với xâu bit của từng cô trong số \(N\) cô bò, kể cả chính cô ấy, theo modulo \(10^9+7\). Cụ thể, nếu tổng bằng số hữu tỉ \(a/b\), trong đó \(a\) và \(b\) là các số nguyên không có ước chung, hãy in số nguyên duy nhất \(x\) thuộc \([0,10^9+7)\) sao cho \(bx-a\) chia hết cho \(10^9+7\).

Dữ liệu vào

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

\(N\) dòng tiếp theo, mỗi dòng chứa một số nguyên \(i\in(0,2^K)\), biểu diễn một cô bò được gắn với dạng biểu diễn nhị phân độ dài \(K\) của \(i\).

Dữ liệu ra

Với mỗi cô bò, in tổng theo modulo \(10^9+7\) trên một dòng riêng.

Phân nhóm

Các test 2–15: Có hai bộ test cho mỗi giá trị \(K\in\{10,15,16,17,18,19,20\}\).

Ví dụ

Ví dụ 1

Input

Output

Giải thích

Các cô bò được gắn với những xâu bit sau: \([\texttt{01},\texttt{01},\texttt{10},\texttt{11}]\).

Với cô bò thứ nhất, tổng là \(\text{sim}(1,1)+\text{sim}(1,1)+\text{sim}(1,2)+\text{sim}(1,3)=1+1+0+1/2\equiv 500000006\pmod{10^9+7}\).

Xâu bit của cô bò thứ hai giống cô bò thứ nhất nên tổng của cô ấy cũng giống như trên.

Với cô bò thứ ba, tổng là \(\text{sim}(2,1)+\text{sim}(2,1)+\text{sim}(2,2)+\text{sim}(2,3)=0+0+1+1/2\equiv 500000005\pmod{10^9+7}\).

Nguồn

Đề bài gốc: USACO 2024 December Contest, Platinum — All Pairs Similarity

Tác giả: Benjamin Qi.

2. USACO 2025 - It's Mooin' Time

Điểm: 100 (p) Thời gian: 4.0s Bộ nhớ: 512M Input: bàn phím Output: màn hình

Lưu ý: Giới hạn thời gian của bài này là 3 giây, gấp 1,5 lần mức mặc định.

Bessie có một xâu độ dài \(N\) (\(1\leq N\leq 3\cdot 10^5\)) chỉ gồm các ký tự M và O. Với mỗi vị trí \(i\) của xâu, chi phí để đổi ký tự tại vị trí đó thành ký tự còn lại là \(c_i\) (\(1\leq c_i\leq 10^8\)).

Bessie cho rằng xâu sẽ đẹp hơn nếu chứa nhiều tiếng moo độ dài \(L\) (\(1\leq L\leq\min(N,3)\)). Một tiếng moo độ dài \(L\) là một ký tự M theo sau bởi \(L-1\) ký tự O.

Với mỗi số nguyên dương \(k\) từ \(1\) đến \(\lfloor N/L\rfloor\), hãy tính chi phí nhỏ nhất để thay đổi xâu sao cho nó chứa ít nhất \(k\) xâu con bằng một tiếng moo độ dài \(L\).

Dữ liệu vào

Dòng đầu chứa \(L\) và \(N\).

Dòng tiếp theo chứa xâu độ dài \(N\) của Bessie, chỉ gồm các ký tự M và O.

Dòng tiếp theo chứa các số nguyên cách nhau bởi dấu cách \(c_1\dots c_N\).

Dữ liệu ra

In \(\lfloor N/L\rfloor\) dòng, lần lượt là đáp án cho từng \(k\) theo thứ tự tăng dần.

Phân nhóm

Test 5: \(L=3\), \(N\leq 5000\).
Test 6: \(L=1\).
Các test 7–10: \(L=2\).
Các test 11–18: \(L=3\).

Ví dụ

Ví dụ 1

Input

1 4
MOOO
10 20 30 40

Output

Ví dụ 2

Input

3 4
OOOO
50 40 30 20

Output

Ví dụ 3

Input

2 20
OOOMOMOOOMOOOMMMOMOO
44743602 39649528 94028117 50811780 97338107 30426846 94909807 22669835 78498782 18004278 16633124 24711234 90542888 88490759 12851185 74589289 54413775 21184626 97688928 10497142

Output

Ví dụ 4

Input

3 20
OOOMOMOOOMOOOMMMOMOO
44743602 39649528 94028117 50811780 97338107 30426846 94909807 22669835 78498782 18004278 16633124 24711234 90542888 88490759 12851185 74589289 54413775 21184626 97688928 10497142

Output

Nguồn

Đề bài gốc: USACO 2024 December Contest, Platinum — It's Mooin' Time

Tác giả: Benjamin Qi.

3. USACO 2025 - Maximize Minimum Difference

Điểm: 100 (p) Thời gian: 4.0s Bộ nhớ: 512M Input: bàn phím Output: màn hình

Lưu ý: Giới hạn thời gian của bài này là 4 giây, gấp đôi mức mặc định.

Moo! Bạn được cho một số nguyên \(N\) (\(2\leq N\leq 2000\)). Xét tất cả các hoán vị \(p=[p_0,p_1,\dots,p_{N-1}]\) của \([0,1,2,\dots,N-1]\). Gọi \(f(p)=\min_{i=0}^{N-2}|p_i-p_{i+1}|\) là hiệu tuyệt đối nhỏ nhất giữa hai phần tử liên tiếp bất kỳ của \(p\), và gọi \(S\) là tập hợp tất cả các hoán vị \(p\) đạt giá trị \(f(p)\) lớn nhất có thể.

Bạn còn được cho \(K\) (\(0\leq K\leq N\)) ràng buộc có dạng \(p_i=j\) (\(0\leq i,j<N\)). Hãy đếm số hoán vị thuộc \(S\) thỏa mãn tất cả các ràng buộc, theo modulo \(10^9+7\).

Dữ liệu vào

Dòng đầu chứa \(T\) và \(N\) (\(1\leq TN\leq 2\cdot 10^4\)), nghĩa là bạn cần giải \(T\) bộ test độc lập, mỗi bộ được xác định bởi một tập ràng buộc khác nhau.

Mỗi bộ test bắt đầu bằng \(K\), tiếp theo là \(K\) dòng, mỗi dòng chứa \(i\) và \(j\). Đảm bảo rằng:

Cùng một giá trị \(i\) không xuất hiện quá một lần trong cùng một bộ test.
Cùng một giá trị \(j\) không xuất hiện quá một lần trong cùng một bộ test.

Dữ liệu ra

Với mỗi bộ test, in đáp án theo modulo \(10^9+7\) trên một dòng riêng.

Phân nhóm

Test 5: \(N=15\).
Test 6: \(N=2000\).
Các test 7–9: Trong mọi bộ test đều có ràng buộc \(p_0=\lfloor N/2\rfloor\).
Các test 10–13: Trong mọi bộ test, tồn tại một ràng buộc \(p_i=j\) với \(j=\lfloor N/2\rfloor\).
Các test 14–20: Không có ràng buộc bổ sung.

Ví dụ

Ví dụ 1

Input

Output

2
0
1

Giải thích

Giá trị lớn nhất có thể của \(f(p)\) là \(2\), và \(S=\{[2,0,3,1],[1,3,0,2]\}\).

Ví dụ 2

Input

Output

Giải thích

Hoán vị \(p=[5,0,6,1,7,2,9,4,10,3,8]\) phải được tính trong tất cả các bộ test.

Ví dụ 3

Input

Output

Giải thích

Hoán vị \(p=[4,9,3,8,2,7,0,5,10,1,6]\) phải được tính trong tất cả các bộ test.

Ví dụ 4

Input

Output

Giải thích

Hãy nhớ in đáp án theo modulo \(10^9+7\).

Nguồn

Đề bài gốc: USACO 2024 December Contest, Platinum — Maximize Minimum Difference

Tác giả: Benjamin Qi.