Bedao OI Contest 2 - Đếm dãy ngoặc đúng
Xem dạng PDF
Gửi bài giải
Điểm:
0,30 (OI)
Giới hạn thời gian:
1.0s
Giới hạn bộ nhớ:
256M
Input:
tbrackets.inp
Output:
tbrackets.out
Tác giả:
Dạng bài
Ngôn ngữ cho phép
C, C++, Go, Java, Kotlin, Pascal, PyPy, Python, Rust, Scratch
Các dấu ngoặc xuất hiện rất nhiều trong các biểu thức toán học để thể hiện thứ tự tính toán. Giờ đây ta bỏ hết các hạng tử toán tử đi, chỉ giữ lại các dấu ngoặc, biểu thức mà ta thu được gọi là một dãy ngoặc đúng. Cụ thể hơn:
Xâu rỗng là biểu thức ngoặc đúng
Nếu ~A~ là biểu thức ngoặc đúng thì (~A~), [~A~], {~A~}, <~A~> cũng là dãy ngoặc đúng
Nếu ~A~ và ~B~ là biểu các thức ngoặc đúng thì ~AB~ cũng là biểu thức ngoặc đúng
Cho một xâu ~S~ là một biểu thức ngoặc (có thể không đúng).
Yêu cầu: Hãy đếm số xâu con liên tiếp của ~S~ là dãy ngoặc đúng.
Input
Vào từ file văn bản tbrackets.inp:
- Một xâu ~S~ (~|S| \le 10^5~)
Output
Đưa ra file văn bản tbrackets.out:
- Một số nguyên duy nhất là kết quả bài toán.
Scoring
| Subtask | Điểm | Giới hạn |
|---|---|---|
| 1 | ~30\%~ | ~n \le 100~ |
| 2 | ~30\%~ | ~S~ chỉ gồm các kí tự ( và ) |
| 3 | ~40\%~ | Không có ràng buộc gì thêm |
Sample Input 1
()()()
Sample Output 1
6
Sample Input 2
[]{()}
Sample Output 2
4
Bình luận
Bình luận này đã bị ẩn vì có quá nhiều phản ứng tiêu cực. Nhấn để xem.
Mình xin đóng góp lời giải cho bài toán này như sau:
Gọi ~dp_i~ là số dãy ngoặc đúng kết thúc tại ~i~. Ta có công thức ~dp_i = dp_{j-1}+1~ với ~j~ là vị trí lớn nhất ~<i~ và ~s[j...i]~ tạo thành một dãy ngoặc đúng. Nghĩa là ta sẽ ghép xâu ~s[j:i]~ với các xâu ngoặc đúng nằm tại ~j~.
Vậy tại sao ta không thêm với toàn bộ ~j~ mà chỉ xét vị trí ~j~ lớn nhất?
Giả sử ta có một vị trí ~j'<j~ và ~s[j':i],s[j:i]~ đồng thời là dãy ngoặc đúng. Khi đó ta có thể cắt xâu ~s[j',i']~ thành ~s[j',j-1]~ và ~s[j,i]~; và hai xâu này là hai dãy ngoặc đúng.
Để tìm vị trí ~j_{max}<i~ mà ~s[j:i]~ là dãy ngoặc đúng, ta sử dụng stack. Cụ thể, nếu gặp kí tự mở, ta push vị trí ~i~ vào stack. Ngược lại, nếu gặp kí tự đóng:
Độ phức tạp: ~O(n)~
Mình cũng đang có ý tưởng giống bạn nè :))
:)