Stack

5
6
3 9 4 6 7 5
1
1000000
2
2 1
10
31 41 59 26 53 58 97 93 23 84
7
3 2 1 2 3 4 5

3
0
1
8
2

Với giá [3,9,4,6,7,5], duyệt từ ngày cuối về đầu và giữ giá trị nhỏ nhất đã gặp (min hậu tố): ngày 6 (giá 5) không có ngày sau nên không xấu, min=5. Ngày 5 (giá 7) > min=5 nên xấu; ngày 4 (giá 6) > 5 nên cũng xấu. Ngày 3 (giá 4) ≤ 5 nên không xấu, min cập nhật thành 4; ngày 2 (giá 9) > 4 nên xấu; ngày 1 (giá 3) ≤ 4 nên không xấu. Tổng cộng có 3 ngày xấu (ngày 2, 4, 5), khớp đáp án 3.

3
AAA
BABA
AABBBABBBB

3
2
0

Với s="BABA", duyệt từ phải sang trái và đếm số B "tín dụng" có thể dùng để xoá một A đứng trước nó (thông qua thao tác AB hoặc dây chuyền BB): kí tự A cuối (vị trí 4) chưa có B nào bên phải nên không xoá được, phải giữ lại. Kí tự B (vị trí 3) tạo 1 tín dụng; kí tự A (vị trí 2) dùng tín dụng đó để xoá (ghép thành AB), hết tín dụng. Kí tự B (vị trí 1) tạo lại 1 tín dụng nhưng không còn A nào sau nó để ghép, nên B này cũng ở lại; số B dư (1, là số lẻ) không tự ghép được thành BB. Kết quả còn lại 1 A và 1 B, tổng độ dài 2, khớp đáp án.

4
6
_(_)_)
2
_)
8
_)_)_)_)
8
_(_)_(_)

5
1
4
8

Với s="_(_)_)" (n=6), vị trí 1 bắt buộc là '(' (dãy ngoặc đúng không thể bắt đầu bằng ')'). Đã có 2 dấu '(' cố định (vị trí 1, 2) và 2 dấu ')' cố định (vị trí 4, 6), nên trong 2 vị trí trống còn lại (3, 5) cần đúng 1 dấu '(' và 1 dấu ')' để cân bằng 3 mở - 3 đóng. Chọn vị trí 3=')', vị trí 5='(' cho dãy "(())()" với các cặp khớp (1,4) cách 3, (2,3) cách 1, (5,6) cách 1, tổng chi phí 3+1+1=5; phương án còn lại (vị trí 3='(', vị trí 5=')') cho "((()))" với chi phí 5+3+1=9, lớn hơn, nên phương án chi phí 5 là tối ưu.

2
)(

Yes

Với s=")(", lấy dấu ')' ở vị trí 1 và chuyển nó ra cuối dãy: phần còn lại là "(" rồi thêm ')' vào sau thành "()", đây là dãy ngoặc đúng và chỉ dùng đúng 1 lần di chuyển (trong giới hạn tối đa 1 lần cho phép), nên đáp án là Yes.

4
1
()
3
()(())
3
((()))
4
(())(())

1
2
3
3

1. Test 1

   Với s="()" (n=1), chỉ có cặp chỉ số (1,2) và đúng đoạn s[1..2]="()" là dãy hợp lệ duy nhất, nối 2 đỉnh thành 1 thành phần liên thông.

2. Test 2

   Với s="()(())" (độ dài 6): cặp (1,2)="()" hợp lệ nối đỉnh 1-2; trong khối sau, (4,5)="()" nối đỉnh 4-5, và (3,6)="(())" nối đỉnh 3-6. Toàn chuỗi s[1..6]="()(())" cũng là dãy hợp lệ nên (1,6) là một cạnh, gộp thành phần {1,2} với {3,6} thành nhóm {1,2,3,6}; nhóm {4,5} không có cạnh nào nối ra ngoài nên tách biệt. Kết quả có 2 thành phần liên thông, khớp đáp án.

(()))(

4

Với s="(()))(", duyệt trái sang phải bằng ngăn xếp lưu các dấu '(' chưa khớp: '(' tại vị trí 1 và 2 được đẩy vào ngăn xếp; ')' tại vị trí 3 khớp với '(' ở vị trí 2 (được 2 kí tự); ')' tại vị trí 4 khớp với '(' ở vị trí 1 (được thêm 2 kí tự); ')' tại vị trí 5 không còn gì để khớp nên bị loại; '(' tại vị trí 6 không có ')' nào theo sau để khớp nên cũng bị loại. Tổng số kí tự khớp được là 2+2=4, tương ứng dãy con "(())" lấy từ 4 vị trí đầu, khớp đáp án 4.

)((())))(()())

6 2

Với s=")((())))(()())" (14 kí tự), dùng ngăn xếp lưu chỉ số các kí tự chưa khớp: khi ')' khớp được với đỉnh ngăn xếp, độ dài đoạn hợp lệ hiện tại bằng chỉ số hiện tại trừ chỉ số còn lại ở đáy ngăn xếp. Cách quét này tìm ra 2 đoạn cùng đạt độ dài lớn nhất là 6: đoạn "((()))" (vị trí 2-7) và đoạn "(()())" (vị trí 9-14), không có đoạn nào dài hơn. Vì vậy kết quả in ra là độ dài 6 và số lượng đoạn đạt độ dài đó là 2, tức "6 2".