Bedao OI Contest 2 - Đếm dãy ngoặc đúng

View as PDF
Submit solution
Points: 0.30 (partial)
Time limit: 1.0s
Memory limit: 256M
Input: tbrackets.inp
Output: tbrackets.out
Author:
bedao
Problem type
Allowed languages
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

Comments

Please read the guidelines before commenting.


  • -5
    trongtenlinhcbhk64  commented on Nov. 20, 2023, 2:52 a.m.

    This comment is hidden due to too much negative feedback. Show it anyway.


  • 23
    y  commented on Nov. 16, 2023, 2:20 a.m.

    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.

    • Gọi ~match_i~ là vị trí ~j<i~ lớn nhất mà ~s_j~ "match" với ~s_i~, nghĩa là ~s_j~ là dấu ngoặc mở tương ứng với dấu ngoặc đóng ~s_i~
    • Với xâu ~s[j:i]~, ta xác định được mảng ~match~ cho toàn bộ vị trí ~[j:i]~ vì xâu ~s~ là dãy ngoặc đúng
    • Vì vậy nếu xâu ~s[j':i]~ là dãy ngoặc đúng thì cũng phải xác định được mảng ~match~ cho xâu ~s[j',j-1]~

    Để 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:

    • Nếu stack rỗng, không làm gì
    • Nếu phần tử cuối của stack match được với ~i~, gán ~dp_i=dp_{top-1}+1~ và pop phần tử cuối của stack ra
    • Ngược lại, xoá sạch stack (vì nếu con ~i~ không ghép được với ~j_{max}~ thì cũng không thể ghép được với ~j~ nào khác. Nếu ghép được, thì phải tồn tại một vị trí ~i'~ trước ~i~ để ghép với vị trí ~j_{max}~ nằm đầu stack. Khi đó, vị trí ~j_{max}~ không được nằm trong stack. Lý luận tương tự cho trường hợp ~i'>i~)

    Độ phức tạp: ~O(n)~