Editorial for Bedao Mini Contest 09 - BRACKET
Remember to use this editorial only when stuck, and not to copy-paste code from it. Please be respectful to the problem author and editorialist.
Submitting an official solution before solving the problem yourself is a bannable offence.
Submitting an official solution before solving the problem yourself is a bannable offence.
Author:
Xét dãy ngoặc ~T~ có độ dài ~m~, gọi ~f_i~ là số dấu ngoặc mở "dư" của dãy tạo bởi ~i~ phần tử đầu tiên của ~T~. Cụ thể:
- ~f_0 = 0~.
- Nếu ~T_i = '('~ thì ~f_i = f_{i-1} + 1~, ngược lại ~f_i = f_{i-1} - 1~ với mọi ~1 \leq i \leq m~.
~T~ là dãy ngoặc đúng khi thỏa mãn cả hai điều kiện:
- ~min(f_0, f_1, f_2, ..., f_m) = 0~: số lượng dấu ngoặc mở "dư" không được âm tại bất kì tiền tố nào của ~T~.
- ~f_m = 0~: cả dãy ngoặc không dư dấu ngoặc mở nào.
Nhận xét: nếu thêm một dấu ngoặc mở vào đầu dãy (giả sử dấu ngoặc này có chỉ số là ~-1~ và không ảnh hưởng gì đến các chỉ số của các dấu ngoặc khác) thì tất cả phần tử của mảng ~f~ sẽ tăng lên ~1~.
Một cách chèn các dấu ngoặc để ~T~ trở thành dãy ngoặc đúng như sau:
Đặt ~x = -min(f_0, f_1, f_2, ..., f_m)~ (~x \geq 0~).
Thêm ~x~ dấu ngoặc mở vào đầu dãy, lúc này ~f_m = f_m + x~.
Thêm ~f_m~ dấu ngoặc đóng
Comments