Bùa Yêu

Điểm: 0,10 (OI)

Giới hạn thời gian: 3.0s

Giới hạn bộ nhớ: 512M

Input: stdin

Output: stdout

Tác giả:

vnoicup

Dạng bài

Ngôn ngữ cho phép

C, C++, Go, Java, Kotlin, Pascal, PyPy, Python, Rust, Scratch

Đã sống gần hai mươi năm trên đời mà vẫn chưa có người yêu, Trung quyết định lên chùa cầu duyên. Sau khi thực hiện đủ các nghi lễ, Trung được nhận một tấm bùa. Trên tấm bùa ghi một xâu độ dài ~n~ chỉ gồm hai chữ cái ~\texttt{O}~ hoặc ~\texttt{K}~. Với hiểu biết uyên thâm về bủa ngải của mình, Trung biết rằng độ hiệu nghiệm của tấm bùa phụ thuộc vào các cặp chữ cái liên tiếp nhau. Cụ thể:

Cặp chữ ~\texttt{OK}~ có tác dụng, do đó, nếu tấm bùa có ~a~ cặp chữ ~\texttt{OK}~ thì độ hiệu nghiệm của tấm bùa sẽ tăng lên ~a^2~.
Cặp chữ ~\texttt{KO}~ phản tác dụng, do đó, nếu tấm bùa có ~b~ cặp chữ ~\texttt{KO}~ thì độ hiệu nghiệm của tấm bùa sẽ giảm đi ~b^2~.

Nói cách khác, nếu tấm bùa có ~a~ cặp chữ ~\texttt{OK}~ và ~b~ cặp chữ ~\texttt{KO}~ thì độ hiệu nghiệm của tấm bùa sẽ là ~a^2 - b^2~. Ví dụ, nếu tấm bùa ghi xâu ~\texttt{OOOKOO}~ thì ~a = 1~, ~b = 1~, do vậy độ hiệu nghiệm của tấm bùa sẽ là ~1^2 - 1^2 = 0~.

Trung chưa hài lòng lắm về tấm bùa của mình, nên đã xin nhà chùa phát cho một tấm bùa khác. Tuy nhiên, nhà chùa chỉ cho phép Trung thay đổi tấm bùa hiện tại tối đa ~k~ lần, mỗi lần Trung có thể chọn hai chữ cái bất kì trên tấm bùa và đổi chỗ chúng cho nhau. Hãy giúp Trung có được tấm bùa yêu với độ hiệu nghiệm lớn nhất có thể nhé!

Input

Mỗi test gồm nhiều test case. Dòng đầu tiên chứa số lượng test case ~t~ (~1 \leq t \leq 10\,000~). Mô tả của mỗi test case như sau.

Dòng đầu tiên gồm hai số nguyên dương ~n~ và ~k~ (~2 \leq n \leq 10^5~, ~1 \leq k \leq 10~) — độ dài của xâu được ghi trên tấm bùa và số lần biến đổi tối đa.

Dòng thứ hai gồm một xâu ~s~ gồm ~n~ kí tự ~\texttt{O}~ hoặc ~\texttt{K}~, mô tả xâu được ghi trên tấm bùa.

Đảm bảo rằng tổng ~n~ của tất cả các test case không vượt quá ~10^5~.

Output

Với mỗi test case, in ra một số nguyên là độ hiệu nghiệm tối đa tấm bùa có thể đạt được.

Scoring

Subtask	Điểm	Ràng buộc
1	~250~	Tổng của ~n~ không vượt quá ~100~, ~k = 1~
2	~750~	~k = 1~
3	~1250~	Không có ràng buộc gì thêm
Tổng	~2250~

Sample Input 1

5
2 1
KO
2 1
OK
7 1
OOOKKKK
7 1
KKOOKKK
10 2
KOOKOKKKOO

Sample Output 1

Notes

Ở test case thứ nhất, cách biến đổi tối ưu là ~\mathtt{KO}~ ~\to \mathtt{OK}~. Xâu thu được cuối cùng có độ hiệu nghiệm là ~1~.

Ở test case thứ hai, cách biến đổi tối ưu là giữ nguyên xâu ~\mathtt{OK}~, với độ hiệu nghiệm là ~1~.

Ở test case thứ năm, một cách biến đổi tối ưu là ~\mathtt{KO}~~\mathtt{OKOKKKOO} \to \mathtt{OKOKOK}~~\texttt{K}~~\texttt{KO}~~\texttt{O}~ ~\to \mathtt{OKOKOKOKOK}~, thu được xâu cuối cùng có độ hiệu nghiệm là ~9~.

Bình luận

Hãy đọc nội quy trước khi bình luận.

17
y đã bình luận lúc 13, Tháng 8, 2024, 9:47 ← chỉnh sửa →
Mình xin đóng góp lời giải cho bài này như sau:

Subtask 1:

Duyệt trâu ~n^2~ cách hoán đổi, với mỗi cách hoán đổi tính chi phí trong ~O(n)~

Subtask 2:

Cho xâu ~s~ độ dài ~n~ được đánh số từ ~1~. Nếu biết số vị trí ~i > 1~ có ~s_i \neq s_{i-1}~ là ~x~ thì ta có thể tính chi phí trong ~O(1)~ như sau:

Nếu ~s_1 = \text{O}~ thì chi phí là ~{\left\lfloor \frac{x}{2} \right\rfloor}^2 - {\left\lfloor \frac{x-1}{2} \right\rfloor}^2~

Nếu ~s_1 = \text{K}~ thì chi phí là ~{\left\lfloor \frac{x-1}{2} \right\rfloor}^2 - {\left\lfloor \frac{x}{2} \right\rfloor}^2~

Một thao tác swap ta có thể đưa về việc: thay đổi kí tự ~s_i~ và ~s_j~ thành đối của nó ~(i<j)~, hay nghĩa là ghép cặp một kí tự ~\text{O}~ với một kí tự ~\text{K}~ sau đó hoặc ngược lại.

Ta sẽ sử dụng quy hoạch động. Gọi ~\text{dp}(i, \text{numOper}, \text{numO}, \text{numK}, \text{last})~ là số vị trí ~j \leq i~ có ~s_j \neq s_{j-1}~ lớn nhất với điều kiện:

Đã sử dụng ~\text{numOper}~ thao tác;

Đã thực hiện ~\text{numO}~ lần đổi từ ~\text{O} \rightarrow \text{K}~, nhưng những vị trí này chưa được ghép cặp với các kí tự ~\text{K}~ nào đằng sau nó;

Đã thực hiện ~\text{numK}~ lần đổi từ ~\text{K} \rightarrow \text{O}~, nhưng những vị trí này chưa được ghép cặp với các kí tự ~\text{O}~ nào đằng sau nó.

Kí tự ~s_{i}~ là ~\text{last}~

Tại vị trí ~i~, giả sử đã tính được ~\text{dp}(i, \text{numOper}, \text{numO}, \text{numK}, \text{last})~ và muốn chuyển sang trạng thái thứ ~i+1~:

Nếu ta giữ nguyên ~s_{i+1}~:

Chuyển sang trạng thái ~(i+1, \text{numOper}, \text{numO}, \text{numK}, s_{i+1})~

Nếu ta chọn thay đổi ~s_{i+1}~:

Nếu ta cho vị trí ~i+1~ trả "nợ" cho các vị trí trước:

Nếu ~s_{i+1}= \text{O}~: chuyển sang trạng thái ~(i+1, \text{numOper} + 1, \text{numO}, \text{numK} - 1, \text{K})~

Nếu ~s_{i+1}= \text{K}~: chuyển sang trạng thái ~(i+1, \text{numOper} + 1, \text{numO} - 1, \text{numK}, \text{O})~

Nếu ta muốn tiếp tục cho vị trí ~i+1~ vào danh sách "nợ":

Nếu ~s_{i+1}= \text{O}~: chuyển sang trạng thái ~(i+1, \text{numOper} + 1, \text{numO} + 1, \text{numK}, \text{K})~

Nếu ~s_{i+1}= \text{K}~: chuyển sang trạng thái ~(i+1, \text{numOper} + 1, \text{numO}, \text{numK} + 1, \text{O})~

Lưu ý xử lí các trạng thái không hợp lệ một cách thích hợp.

Vì ~k \geq 1~, nên ta luôn chọn thay đổi kí tự đầu tiên thành ~\text{O}~ để đáp án là dương. Từ đó dễ dàng suy ra base case cho bài toán.

Để lấy đáp án, ta duyệt toàn bộ trạng thái ~(i, j, 0, 0, x)~ với ~0 \leq j \leq k~, ~x \in \{0,1\}~ và đoạn ~[i+1,n]~ chứa toàn kí tự ~x~ để lấy kết quả. Nếu trạng thái hợp lệ, cực đại hoá kết quả với ~{\left\lfloor \frac{\text{dp}(i,j,0,0,x)}{2} \right\rfloor}^2 - {\left\lfloor \frac{\text{dp}(i,j,0,0,x)-1}{2} \right\rfloor}^2~

Độ phức tạp: ~O(nk^3)~

Ngoài ra mình đọc submission còn thấy một số thuật toán tham lam cho subtask này, nhưng mình chưa nghĩ kĩ nên trình bày luôn thuật toán này để phục vụ cho subtask cuối ;)

Subtask 3:

Bằng thuật toán của subtask 2 ta có thể qua luôn được subtask 3 như sau:

Nhận thấy ta chỉ duyệt các bộ ~(\text{numOper}, \text{numO}, \text{numK})~ có ~\text{numO} \leq \text{numOper}~ và ~\text{numO} + \text{numK} \leq \text{numOper}~. Nên ta có thể nén các bộ trạng thái này lại. Thực tế chưa có đến ~300~ trạng thái với ~k \leq 10~. Vậy độ phức tạp tối đa là ~n \times 300 \times 2~ ~= 6 \times 10^7~

Tuy nhiên ta cũng có thể làm tốt hơn:

Nhận thấy việc lưu ~\text{numOper}~ là không cần thiết.

Ta thay đổi ý nghĩa của biến ~\text{numO}~ và ~\text{numK}~ thành số lần đổi ~\text{O} \rightarrow \text{K}~ và số lần đổi ~\text{K} \rightarrow \text{O}~ (bỏ qua khái niệm "nợ" ở subtask 2).

Như vậy ta chỉ cần đảm bảo ~\text{numO}~ và ~\text{numK}~ luôn dương và ~\leq k~ trong mọi vị trí ~i~, và đến thời điểm cuối cùng ~\text{numO}=\text{numK}~ là đủ, do các thao tác có thể đổi chỗ cho nhau.

Công thức chuyển từ đây cũng đơn giản hơn, các bạn có thể tự suy ra từ subtask 2.

Từ đó độ phức tạp giảm xuống ~O(nk^2)~.

Triển khai mẫu các bạn có thể xem ở phần Editorial.