| # | Bài tập | Điểm | Thời gian: | Giới hạn bộ nhớ |
|---|---|---|---|---|
| 1 | USACO 2025 - Bessie's Function | 100 (p) | 4.0s | 512M |
| 2 | USACO 2025 - The Best Subsequence | 100 (p) | 4.0s | 512M |
| 3 | USACO 2025 - Friendship Editing | 100 (p) | 4.0s | 512M |
Bessie có một hàm đặc biệt \(f(x)\) nhận đầu vào là một số nguyên trong \([1,N]\) và trả về một số nguyên trong \([1,N]\) (\(1\le N\le 2\cdot 10^5\)). Hàm \(f(x)\) được định nghĩa bởi \(N\) số nguyên \(a_1\ldots a_N\), trong đó \(f(x)=a_x\) (\(1\le a_i\le N\)).
Bessie muốn hàm này có tính lũy đẳng. Nói cách khác, nó phải thỏa mãn \(f(f(x))=f(x)\) với mọi số nguyên \(x\in[1,N]\).
Với chi phí \(c_i\), Bessie có thể thay đổi giá trị của \(a_i\) thành bất kỳ số nguyên nào trong \([1,N]\) (\(1\le c_i\le 10^9\)). Hãy xác định tổng chi phí tối thiểu Bessie cần trả để làm cho \(f(x)\) có tính lũy đẳng.
Dòng đầu tiên chứa \(N\).
Dòng thứ hai chứa \(N\) số nguyên cách nhau bởi dấu cách \(a_1,a_2,\dots,a_N\).
Dòng thứ ba chứa \(N\) số nguyên cách nhau bởi dấu cách \(c_1,c_2,\dots,c_N\).
In ra tổng chi phí tối thiểu Bessie cần trả để làm cho \(f(x)\) có tính lũy đẳng.
Ví dụ 1
5
2 4 4 5 3
1 1 1 1 13Ta có thể đổi \(a_1=4\), \(a_4=4\), \(a_5=4\). Vì mọi \(c_i\) đều bằng một, tổng chi phí bằng \(3\), chính là số lần thay đổi. Có thể chứng minh không tồn tại lời giải chỉ dùng \(2\) thay đổi trở xuống.
Ví dụ 2
8
1 2 5 5 3 3 4 4
9 9 2 5 9 9 9 97Ta đổi \(a_3=3\) và \(a_4=4\). Tổng chi phí là \(2+5=7\).
Ngoài ra, trong mỗi phân nhóm trong số ba phân nhóm cuối, nửa đầu số test sẽ thỏa mãn \(c_i=1\) với mọi \(i\).
USACO 2025 February Contest, Gold — Bessie's Function. Tác giả: Avnith Vijayram.
Farmer John có một xâu nhị phân độ dài \(N\) (\(1\leq N\leq 10^9\)), ban đầu gồm toàn ký tự \(0\).
Trước tiên, ông sẽ lần lượt thực hiện \(M\) (\(1\leq M\leq 2\cdot 10^5\)) cập nhật trên xâu. Mỗi cập nhật đảo mọi ký tự từ vị trí \(l\) đến \(r\). Cụ thể, đảo một ký tự sẽ đổi nó từ \(0\) thành \(1\) hoặc ngược lại.
Sau đó, ông đưa ra \(Q\) (\(1\leq Q\leq 2\cdot 10^5\)) truy vấn. Với mỗi truy vấn, ông yêu cầu bạn in ra dãy con lớn nhất theo thứ tự từ điển có độ dài \(k\), gồm các ký tự lấy từ xâu con từ vị trí \(l\) đến \(r\). Nếu đáp án là xâu nhị phân \(s_1s_2\dots s_k\), hãy in ra \(\sum_{i=0}^{k-1}2^i\cdot s_{k-i}\) (tức giá trị của xâu khi được hiểu là một số nhị phân) modulo \(10^9+7\).
Dãy con là một xâu có thể thu được từ một xâu khác bằng cách xóa đi một số hoặc không xóa ký tự nào mà không làm thay đổi thứ tự của các ký tự còn lại.
Nhắc lại rằng xâu \(A\) lớn hơn xâu \(B\) có cùng độ dài theo thứ tự từ điển khi và chỉ khi tại vị trí đầu tiên \(i\) (nếu tồn tại) mà \(A_i\neq B_i\), ta có \(A_i>B_i\).
Dòng đầu tiên chứa \(N\), \(M\) và \(Q\).
\(M\) dòng tiếp theo chứa hai số nguyên \(l\) và \(r\) (\(1\leq l\leq r\leq N\)) — hai đầu mút của mỗi cập nhật.
\(Q\) dòng tiếp theo chứa ba số nguyên \(l\), \(r\) và \(k\) (\(1\leq l\leq r\leq N\), \(1\leq k\leq r-l+1\)) — hai đầu mút của mỗi truy vấn và độ dài dãy con.
In ra \(Q\) dòng. Dòng thứ \(i\) chứa đáp án cho truy vấn thứ \(i\).
Ví dụ 1
5 3 9
1 5
2 4
3 3
1 5 5
1 5 4
1 5 3
1 5 2
1 5 1
2 5 4
2 5 3
2 5 2
2 5 121
13
7
3
1
5
5
3
1Sau khi thực hiện \(M\) thao tác, xâu là \(10101\).
Với truy vấn đầu tiên, chỉ có một dãy con độ dài \(5\) là \(10101\), được diễn giải thành \(1\cdot 2^4+0\cdot 2^3+1\cdot 2^2+0\cdot 2^1+1\cdot 2^0=21\).
Với truy vấn thứ hai, có \(5\) dãy con phân biệt độ dài \(4\): \(0101\), \(1101\), \(1001\), \(1011\), \(1010\). Dãy con lớn nhất theo thứ tự từ điển là \(1101\), được diễn giải thành \(1\cdot 2^3+1\cdot 2^2+0\cdot 2^1+1\cdot 2^0=13\).
Với truy vấn thứ ba, dãy lớn nhất theo thứ tự từ điển là \(111\), được diễn giải thành \(7\).
Ví dụ 2
9 1 1
7 9
1 8 83Ví dụ 3
30 1 1
1 30
1 30 3073741816Hãy nhớ in đáp án modulo \(10^9+7\).
USACO 2025 February Contest, Gold — The Best Subsequence. Tác giả: Chongtian Ma.
\(N\) con bò của Farmer John được đánh số từ \(1\) đến \(N\) (\(2\le N\le 16\)). Quan hệ bạn bè giữa các con bò có thể được mô hình hóa bằng một đồ thị vô hướng có \(M\) (\(0\le M\le N(N-1)/2\)) cạnh. Hai con bò là bạn bè khi và chỉ khi có một cạnh nối chúng trong đồ thị.
Trong một thao tác, bạn có thể thêm hoặc xóa một cạnh khỏi đồ thị. Hãy tính số thao tác tối thiểu cần thiết để đảm bảo tính chất sau: nếu hai con bò \(a\) và \(b\) là bạn bè, thì với mọi con bò khác \(c\), ít nhất một trong hai con \(a\) và \(b\) là bạn bè với \(c\).
Dòng đầu tiên chứa \(N\) và \(M\).
\(M\) dòng tiếp theo, mỗi dòng chứa một cặp bạn bè \(a\) và \(b\) (\(1\le a<b\le N\)). Không có cặp bạn bè nào xuất hiện quá một lần.
In ra số cạnh cần thêm hoặc xóa.
Ví dụ 1
3 1
1 21Mạng lưới vi phạm tính chất trên. Ta có thể thêm một trong hai cạnh \((2,3)\) hoặc \((1,3)\), hoặc xóa cạnh \((1,2)\) để khắc phục.
Ví dụ 2
3 2
1 2
2 30Không cần thay đổi gì.
Ví dụ 3
4 4
1 2
1 3
1 4
2 31USACO 2025 February Contest, Gold — Friendship Editing. Tác giả: Benjamin Qi.