Hướng dẫn giải của [Beginner Free Contest 19] PARENTHESIS
Chỉ dùng lời giải này khi không có ý tưởng, và đừng copy-paste code từ lời giải này. Hãy tôn trọng người ra đề và người viết lời giải.
Nộp một lời giải chính thức trước khi tự giải là một hành động có thể bị ban.
Nộp một lời giải chính thức trước khi tự giải là một hành động có thể bị ban.
Hướng dẫn giải
Kiem tra co the thay dau * bang ( hoac ) de xau tro thanh day ngoac dung hay khong.
Sub 1: Quy hoach dong tap so ngoac mo, ~N \le 1000~ ~O(N^2)~
Giu tap cac so ngoac mo co the dat sau moi ky tu. Chay rieng: dung 8/10 test.
Sub 2: Tham lam khoang [lo, hi], ~N \le 10^4~ ~O(N)~
Giu khoang cac so ngoac mo co the; neu hi < 0 thi NO, cuoi cung lo = 0 thi YES. Chay rieng: dung 10/10 test.
Chương trình hoàn chỉnh
Moi test: neu N <= 1000 dung sub 1, nguoc lai dung sub 2.
#include <bits/stdc++.h>
using namespace std;
string s;
// Sub 1: quy hoach dong theo tap so ngoac mo co the co (dung khi N <= 1000)
void sub1() {
int n = s.size();
vector<char> reach(n + 2, 0), nr(n + 2, 0);
reach[0] = 1;
for (char c : s) {
fill(nr.begin(), nr.end(), 0);
for (int b = 0; b <= n; b++) {
if (!reach[b]) continue;
if (c == '(' || c == '*') nr[b + 1] = 1;
if ((c == ')' || c == '*') && b >= 1) nr[b - 1] = 1;
}
swap(reach, nr);
}
cout << (reach[0] ? "YES" : "NO") << "\n";
}
// Sub 2: tham lam O(N): giu khoang [lo, hi] cac so ngoac mo co the co
void sub2() {
long long lo = 0, hi = 0;
for (char c : s) {
if (c == '(') { lo++; hi++; }
else if (c == ')') { lo--; hi--; }
else { lo--; hi++; }
if (hi < 0) { cout << "NO\n"; return; }
lo = max(lo, 0LL);
}
cout << (lo == 0 ? "YES" : "NO") << "\n";
}
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
int T;
cin >> T;
while (T--) {
cin >> s;
if (s.size() <= 1000) sub1();
else sub2();
}
return 0;
}
Bình luận