Đoạn code cân ngoặc (Đề tự luyện HSG Tin 12 – Bài 2) – Ngăn xếp ghép ngoặc và QHĐ đếm đoạn kết thúc tại i
Đề bài
Đoạn code cân ngoặc. Cho xâu $s$ độ dài $n$ (dòng code của thầy Sơn), mỗi ký tự là một trong sáu dấu ngoặc ( ) [ ] { } hoặc một ký tự thường (chữ cái thường, chữ số, + - * / = ; ,). Đoạn $s[l..r]$ gọi là cân ngoặc nếu sau khi xoá hết ký tự thường trong đoạn, phần còn lại là một dãy ngoặc đúng (xâu rỗng cũng là dãy ngoặc đúng, nên đoạn không có dấu ngoặc nào cũng cân ngoặc). Đếm số cặp $(l, r)$ với $1 \le l \le r \le n$ mà $s[l..r]$ cân ngoặc.
Dữ liệu vào: dòng đầu là $n$ ($1 \le n \le 10^6$); dòng thứ hai là xâu $s$.
Kết quả: số đoạn cân ngoặc.
- Subtask 1 (20%): $n \le 300$.
- Subtask 2 (30%): $n \le 5000$.
- Subtask 3 (20%): $s$ chỉ gồm
(và). - Subtask 4 (30%): không có ràng buộc gì thêm.
12
f(a[i])}+{x}11Các đoạn cân ngoặc: 5 đoạn một ký tự thường f, a, i, +, x; [i], a[i], (a[i]), f(a[i]); {x}, +{x}. Tổng cộng 11 đoạn.
Bạn nào muốn thử nộp bài để hệ thống chấm xem có đúng hay không thì dùng link này nhé. Bộ test có chia subtask và có cả những test "bẫy", nên code đúng ý tưởng nhưng sai chi tiết nhỏ cũng sẽ bị trừ điểm đó.
Nộp bài Đoạn code cân ngoặcLời mở đầu
Kiểm tra một xâu có phải dãy ngoặc đúng hay không là bài "nhập môn ngăn xếp" kinh điển: đi từ trái sang phải, gặp ngoặc mở thì đẩy vào ngăn xếp, gặp ngoặc đóng thì đỉnh ngăn xếp phải là ngoặc mở cùng loại (lấy ra), cuối cùng ngăn xếp phải rỗng. Bài này khó hơn ở chỗ phải đếm trên mọi đoạn con – có tới $\frac{n(n+1)}{2} \approx 5 \cdot 10^{11}$ đoạn khi $n = 10^6$ – và trong xâu còn có ký tự thường, có cả dấu ngoặc gõ lệch.
Nhận xét quan trọng. Nếu chạy thuật toán ngăn xếp trên cả xâu, mỗi ngoặc đóng hợp lệ sẽ được ghép với đúng một ngoặc mở. Trong ví dụ, các cặp ghép là $(2, 7)$, $(4, 6)$, $(10, 12)$; dấu } ở vị trí $8$ không ghép được với ai:
Mỗi cung nối một ngoặc đóng với ngoặc mở mà ngăn xếp ghép cho nó. Dấu } ở vị trí 8 (màu đỏ) thừa: không đoạn cân ngoặc nào được chứa nó.
Ta sẽ thấy: đoạn cân ngoặc kết thúc tại một ngoặc đóng thì phải bắt đầu đúng ở ngoặc mở được ghép với nó, hoặc "nối dài" về bên trái bằng một đoạn cân ngoặc khác. Từ đó ra công thức QHĐ $O(n)$. Lộ trình:
Cách 1Thử mọi đoạn – O(n³) · 20%
Duyệt mọi cặp $(l, r)$, với mỗi đoạn chạy thuật toán ngăn xếp từ đầu: bỏ qua ký tự thường, ngoặc mở thì đẩy vào, ngoặc đóng thì đỉnh phải là ngoặc mở cùng loại (không thì đoạn hỏng ngay), hết đoạn thì ngăn xếp phải rỗng.
#include <bits/stdc++.h>
using namespace std;
// Cach 1: thu moi doan [l..r], kiem tra rieng bang ngan xep - O(n^3)
bool canNgoac(const string& s, int l, int r) {
vector<char> st;
for (int i = l; i <= r; i++) {
char c = s[i];
if (c == '(' || c == '[' || c == '{') st.push_back(c);
else if (c == ')' || c == ']' || c == '}') {
char o = (c == ')') ? '(' : (c == ']') ? '[' : '{';
if (st.empty() || st.back() != o) return false; // dong sai
st.pop_back();
}
}
return st.empty(); // khong con ngoac mo
}
int main() {
int n;
string s;
cin >> n >> s;
long long ans = 0;
for (int l = 0; l < n; l++)
for (int r = l; r < n; r++)
if (canNgoac(s, l, r)) ans++;
cout << ans << '\n';
return 0;
}import sys
MO = {')': '(', ']': '[', '}': '{'}
def can_ngoac(s, l, r):
st = []
for i in range(l, r + 1):
c = s[i]
if c == '(' or c == '[' or c == '{':
st.append(c)
elif c in MO:
if not st or st[-1] != MO[c]:
return False # dong sai
st.pop()
return not st # khong con ngoac mo
def main():
data = sys.stdin.read().split()
n = int(data[0])
s = data[1]
ans = 0
for l in range(n):
for r in range(l, n):
if can_ngoac(s, l, r):
ans += 1
print(ans)
main()Với $n = 300$ chỉ khoảng $4.5 \cdot 10^6$ phép tính, nhưng $n = 5000$ thì đã lên cỡ $2 \cdot 10^{10}$: quá chậm.
Cách 2Cố định l, kéo dài r – O(n²) · 50%
Hai đoạn $s[l..r]$ và $s[l..r+1]$ chỉ khác nhau một ký tự, nên không cần chạy lại ngăn xếp từ đầu. Cố định $l$, cho $r$ tăng dần từ $l$ và cập nhật ngăn xếp dần dần:
- sau khi xử lý ký tự $s_r$, nếu ngăn xếp rỗng thì $s[l..r]$ cân ngoặc → tăng đáp án;
- nếu $s_r$ là ngoặc đóng mà không ghép được (ngăn xếp rỗng hoặc đỉnh khác loại) thì mọi đoạn $s[l..r'], r' \ge r$ đều chứa dấu ngoặc hỏng này →
breakluôn.
#include <bits/stdc++.h>
using namespace std;
// Cach 2: co dinh l, keo dai r va cap nhat ngan xep dan - O(n^2)
int main() {
int n;
string s;
cin >> n >> s;
long long ans = 0;
vector<char> st;
for (int l = 0; l < n; l++) {
st.clear();
for (int r = l; r < n; r++) {
char c = s[r];
if (c == '(' || c == '[' || c == '{') st.push_back(c);
else if (c == ')' || c == ']' || c == '}') {
char o = (c == ')') ? '(' : (c == ']') ? '[' : '{';
if (st.empty() || st.back() != o) break; // moi doan dai hon cung hong
st.pop_back();
}
if (st.empty()) ans++; // [l..r] can ngoac
}
}
cout << ans << '\n';
return 0;
}import sys
def main():
data = sys.stdin.read().split()
n = int(data[0])
s = data[1]
mo = {')': '(', ']': '[', '}': '{'}
ans = 0
for l in range(n):
st = []
for r in range(l, n):
c = s[r]
if c == '(' or c == '[' or c == '{':
st.append(c)
elif c in mo:
if not st or st[-1] != mo[c]:
break # moi doan dai hon cung hong
st.pop()
if not st:
ans += 1 # [l..r] can ngoac
print(ans)
main()$n = 5000$ thì chỉ $1.25 \cdot 10^7$ bước, rất nhanh. Nhưng $n = 10^6$ thì $5 \cdot 10^{11}$ bước – chạy cả ngày 😅.
Cách 3Xâu chỉ có ( và ) – QHĐ trên ngăn xếp, O(n) · 70%
Đổi góc nhìn: thay vì cố định đầu đoạn, ta cố định cuối đoạn. Gọi
$$f[i] = \text{số đoạn cân ngoặc kết thúc tại vị trí } i,$$thì đáp án là $f[1] + f[2] + \cdots + f[n]$. Chạy ngăn xếp trên cả xâu (lưu vị trí các dấu ( chưa được đóng):
- $s_i$ =
(: đoạn kết thúc bằng ngoặc mở không thể cân ngoặc ⇒ $f[i] = 0$; đẩy $i$ vào ngăn xếp. - $s_i$ =
)và ngăn xếp rỗng: dấu này thừa, mọi đoạn chứa nó đều hỏng ⇒ $f[i] = 0$. - $s_i$ =
)và ngăn xếp có đỉnh là $j$: lấy $j$ ra, khi đó $$f[i] = f[j - 1] + 1.$$
Vì sao? Xét một đoạn cân ngoặc $s[l..i]$. Dấu ) cuối cùng ở vị trí $i$ phải ghép với một dấu ( nào đó ở vị trí $k \ge l$, và phần giữa $s[k+1..i-1]$ là dãy ngoặc đúng. Phần giữa đúng nghĩa là ngăn xếp đi qua nó thì "vào bao nhiêu ra bấy nhiêu", nên khi tới $i$, đỉnh ngăn xếp chính là $k$ ⇒ $k = j$. Phần còn lại $s[l..j-1]$ phải là dãy ngoặc đúng (có thể rỗng khi $l = j$). Ngược lại, ghép một đoạn cân ngoặc $s[l..j-1]$ (hoặc rỗng) với khối $s[j..i]$ (là dãy ngoặc đúng) thì được đoạn cân ngoặc. Vậy số cách chọn $l$ là: $1$ (chọn $l = j$) cộng $f[j - 1]$ (số đoạn cân ngoặc kết thúc tại $j - 1$). Quy ước $f[0] = 0$.
()(() thì đoạn () ở cuối có $f = f[3] + 1 = 1$, không cộng thêm đoạn () ở đầu.Subtask 1, 2 có thể có ký tự thường và đủ loại ngoặc, nên code Cách 3 kiểm tra: nếu xâu chỉ gồm (, ) thì dùng QHĐ, ngược lại quay về Cách 2.
#include <bits/stdc++.h>
using namespace std;
// Cach 3: xau chi gom '(' va ')' -> QHD f[i] tren ngan xep O(n); con lai dung Cach 2
int main() {
int n;
string s;
cin >> n >> s;
bool chiTron = true; // chi co '(' va ')' ?
for (char c : s)
if (c != '(' && c != ')') chiTron = false;
long long ans = 0;
if (chiTron) {
vector<int> f(n + 1, 0); // f[i] = so doan can ngoac ket thuc tai i
vector<int> st; // vi tri cac '(' chua duoc dong
for (int i = 1; i <= n; i++) {
if (s[i - 1] == '(') {
st.push_back(i);
} else if (!st.empty()) { // ')' ghep voi '(' gan nhat chua dong
int j = st.back();
st.pop_back();
f[i] = f[j - 1] + 1;
} // ')' thua: f[i] = 0
ans += f[i];
}
} else { // Cach 2: co dinh l, keo dai r
vector<char> st;
for (int l = 0; l < n; l++) {
st.clear();
for (int r = l; r < n; r++) {
char c = s[r];
if (c == '(' || c == '[' || c == '{') st.push_back(c);
else if (c == ')' || c == ']' || c == '}') {
char o = (c == ')') ? '(' : (c == ']') ? '[' : '{';
if (st.empty() || st.back() != o) break;
st.pop_back();
}
if (st.empty()) ans++;
}
}
}
cout << ans << '\n';
return 0;
}import sys
def main():
data = sys.stdin.buffer.read().split()
n = int(data[0])
s = data[1].decode()
ans = 0
if set(s) <= {'(', ')'}: # chi co '(' va ')'
f = [0] * (n + 1) # f[i] = so doan can ngoac ket thuc tai i
st = [] # vi tri cac '(' chua duoc dong
for i in range(1, n + 1):
if s[i - 1] == '(':
st.append(i)
elif st: # ')' ghep voi '(' gan nhat chua dong
j = st.pop()
f[i] = f[j - 1] + 1
# ')' thua: f[i] = 0
ans += f[i]
else: # Cach 2: co dinh l, keo dai r
mo = {')': '(', ']': '[', '}': '{'}
for l in range(n):
st = []
for r in range(l, n):
c = s[r]
if c == '(' or c == '[' or c == '{':
st.append(c)
elif c in mo:
if not st or st[-1] != mo[c]:
break
st.pop()
if not st:
ans += 1
print(ans)
main()()()()...() dài $10^6$ thì $f[2k] = k$, đáp án là $1 + 2 + \cdots + 500000 \approx 1.25 \cdot 10^{11}$: biến ans phải là long long.Cách 4Đủ ba loại ngoặc và ký tự thường – O(n) · 100%
Giữ nguyên ý tưởng $f[i]$ của Cách 3, chỉ cần xử lý thêm hai thứ:
1. Ký tự thường. Nếu $s_i$ là ký tự thường thì $s[l..i]$ cân ngoặc khi và chỉ khi $l = i$ (đoạn chỉ có mỗi ký tự đó, không có ngoặc nào) hoặc $s[l..i-1]$ cân ngoặc (thêm ký tự thường không làm thay đổi phần ngoặc). Vậy $$f[i] = f[i - 1] + 1.$$
2. Ngoặc đóng sai loại. Nếu $s_i$ là ngoặc đóng mà ngăn xếp rỗng hoặc đỉnh là ngoặc mở khác loại, thì không đoạn cân ngoặc nào chứa vị trí $i$: trong một đoạn $s[l..r]$ chứa $i$, khi chạy ngăn xếp riêng cho đoạn đó, tới $i$ thì hoặc ngăn xếp riêng rỗng (thừa ngoặc đóng), hoặc đỉnh của nó chính là đỉnh hiện tại của ngăn xếp chung (khác loại) – đằng nào cũng hỏng. Do đó $f[i] = 0$ và ta xoá sạch ngăn xếp: các ngoặc mở trước $i$ không bao giờ được phép ghép với ngoặc đóng sau $i$ nữa.
- Chỉ so ngoặc đóng với "có ngoặc mở hay không" mà quên so loại → đếm nhầm
(]là cân ngoặc. - Gặp ngoặc đóng sai thì bỏ qua nhưng không xoá ngăn xếp → ví dụ
(a]b): dấu)cuối bị ghép với(đầu và đoạn(a]b)bị đếm nhầm. - Viết $f[i] = f[i-1]$ cho ký tự thường (quên đoạn chỉ gồm chính nó).
Bảng $f$ của ví dụ f(a[i])}+{x}:
| $i$ | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 | 11 | 12 |
|---|---|---|---|---|---|---|---|---|---|---|---|---|
| $s_i$ | f | ( | a | [ | i | ] | ) | } | + | { | x | } |
| $f[i]$ | 1 | 0 | 1 | 0 | 1 | 2 | 2 | 0 | 1 | 0 | 1 | 2 |
Chẳng hạn $f[6] = f[3] + 1 = 2$ (ghép với [ ở vị trí 4: đoạn [i] và a[i]), $f[7] = f[1] + 1 = 2$ (ghép với ( ở vị trí 2: (a[i]) và f(a[i])). Tổng các $f[i]$ là $11$ ✓.
Mô phỏng: ngăn xếp và mảng f
Em nhập một xâu ngắn (tối đa 30 ký tự) rồi bấm Tiếp để xem từng bước: ngăn xếp lưu vị trí các ngoặc mở chưa đóng, ô vàng là cặp vừa ghép, ô đỏ là ngoặc đóng sai (xoá ngăn xếp).
Code hoàn chỉnh – chỉ một vòng lặp, mỗi vị trí được đẩy vào và lấy ra khỏi ngăn xếp nhiều nhất một lần:
#include <bits/stdc++.h>
using namespace std;
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
int n;
string s;
cin >> n >> s;
vector<int> f(n + 1, 0); // f[i] = so doan can ngoac ket thuc tai vi tri i
vector<int> st; // vi tri cac ngoac mo chua duoc dong
long long ans = 0;
for (int i = 1; i <= n; i++) {
char c = s[i - 1];
if (c == '(' || c == '[' || c == '{') {
st.push_back(i); // doan ket thuc o ngoac mo: f[i] = 0
} else if (c == ')' || c == ']' || c == '}') {
char o = (c == ')') ? '(' : (c == ']') ? '[' : '{';
if (!st.empty() && s[st.back() - 1] == o) {
int j = st.back();
st.pop_back();
f[i] = f[j - 1] + 1; // l = j, hoac [l..j-1] can ngoac
} else {
st.clear(); // dong sai: khong doan nao chua i
}
} else {
f[i] = f[i - 1] + 1; // ky tu thuong
}
ans += f[i];
}
cout << ans << '\n';
return 0;
}import sys
def main():
data = sys.stdin.buffer.read().split()
n = int(data[0])
s = data[1].decode()
f = [0] * (n + 1) # f[i] = so doan can ngoac ket thuc tai vi tri i
st = [] # vi tri cac ngoac mo chua duoc dong
mo = {')': '(', ']': '[', '}': '{'}
ans = 0
for i in range(1, n + 1):
c = s[i - 1]
if c == '(' or c == '[' or c == '{':
st.append(i) # doan ket thuc o ngoac mo: f[i] = 0
elif c in mo:
if st and s[st[-1] - 1] == mo[c]:
j = st.pop()
f[i] = f[j - 1] + 1 # l = j, hoac [l..j-1] can ngoac
else:
st.clear() # dong sai: khong doan nao chua i
else:
f[i] = f[i - 1] + 1 # ky tu thuong
ans += f[i]
sys.stdout.write(str(ans) + "\n")
main()clear() cộng lại không quá $n$.Bộ test chấm "bắt" những lỗi nào?
Bộ test có 38 test: 10 test subtask 1 ($n \le 300$, có $n = 1$, xâu toàn ký tự thường, xâu toàn ngoặc gõ lệch...), 9 test subtask 2 ($n = 5000$), 9 test subtask 3 (chỉ có ( ), $n = 10^6$: ()()...(), $5 \cdot 10^5$ dấu ( lồng nhau, dãy ngoặc ngẫu nhiên có ngoặc thừa...) và 10 test subtask 4 ($n = 10^6$, đủ ba loại ngoặc, có test chèn ngoặc đóng sai loại, ngoặc thừa, test toàn ký tự thường với đáp án $5 \cdot 10^{11}$). Nhiều test có đáp án vượt $2^{31}$.
| Cách làm | Sub 1 (20%) | Sub 2 (30%) | Sub 3 (20%) | Sub 4 (30%) | Điểm |
|---|---|---|---|---|---|
| Cách 1 – thử mọi đoạn $O(n^3)$ | Đúng | TLE | TLE | TLE | 20 |
| Cách 2 – cố định l, kéo dài r $O(n^2)$ | Đúng | Đúng | TLE | TLE | 50 |
| Cách 3 – QHĐ khi chỉ có ( ), còn lại Cách 2 | Đúng | Đúng | Đúng | TLE | 70 |
| Cách 4 – QHĐ đầy đủ $O(n)$ | Đúng | Đúng | Đúng | Đúng | 100 |
Sai 1 – ans kiểu int | Đúng | Đúng | 3/9 test | 7/10 test | ≈ 78 |
| Sai 2 – không kiểm tra loại ngoặc | 8/10 test | 6/9 test | Đúng | 4/10 test | 68 |
| Sai 3 – ngoặc đóng sai thì bỏ qua, không xoá ngăn xếp | 8/10 test | 7/9 test | Đúng | 5/10 test | ≈ 74 |
| Sai 4 – ký tự thường: $f[i] = f[i-1]$ | 3/10 test | 1/9 test | Đúng | 0/10 test | ≈ 29 |
Ghi chú của mình: các cách C++ ở trên đã được chấm thử với đúng bộ test của bài: Cách 1 đúng 10/10 test subtask 1 và chạy quá 3 giây ở mọi test còn lại; Cách 2 đúng hết hai subtask đầu, quá giờ ở mọi test $n = 10^6$; Cách 3 đúng 28/28 test của ba subtask đầu nhưng quá giờ ở cả 10 test subtask 4 (có ký tự thường nên phải quay về $O(n^2)$); Cách 4 đúng 38/38 test, test lâu nhất khoảng 0,02 giây. Ví dụ của đề cố ý không có ngoặc đóng sai loại khi ngăn xếp còn ngoặc mở, nên lỗi "không kiểm tra loại ngoặc" và lỗi "không xoá ngăn xếp" đều vẫn ra đúng 11 – các bạn nhớ tự thử những xâu như (a]b) trước khi nộp nhé.
Rất vui khi anh em nào đã đọc đến những dòng cuối cùng này. Anh em đọc chắc cũng mỏi mắt luôn chứ 😅 vậy anh em nghĩ người viết ra hết đống ở trên còn thế nào nữa 🤪. Vậy nên đừng tiếc gì cho mình một lời bình luận hoặc chia sẻ bài viết để động viên mình nè. Chúc anh em học tốt và gặt hái nhiều thành công 😇
- Không biết học gì trước, học gì sau, học lan man nên kiến thức bị hổng.
- Bí bài không ai gỡ, ngồi cả buổi vẫn không ra rồi bỏ cuộc.
- Code chạy được nhưng không đủ điểm, không biết sai ở đâu, chậm ở đâu.
- Không có đề thi thử và người chấm, nên không biết mình đang ở mức nào.
- Dễ nản giữa chừng khi không có ai theo sát.
- Lộ trình 111 buổi video sắp sẵn từ dòng code đầu tiên đến đề HSG thật của các tỉnh.
- Thầy trực tiếp gỡ bí, chữa bài cho từng em qua nhóm Zalo riêng.
- Hệ thống chấm bài tự động 24/7 và thi thử HSG hằng tuần để biết chính xác mình đang ở đâu.
- Đóng học phí một lần, thầy kèm lâu dài: từ thi chuyên Tin đến HSG quốc gia và cả khi lên đại học.
Nhận xét
Đăng nhận xét