Hướng dẫn giải của In xâu (string)
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.
Lời giải này đang bị ẩn cho đến khi bạn chọn mở ra.
Chúng tôi khuyên bạn nên tự thử giải bài trước. Việc mở lời giải có thể làm lộ mất ý tưởng chính trước khi bạn có cơ hội tự giải.
Bạn phải đăng nhập để mở lời giải này.
Đăng nhập
Tác giả: Hiếu Nguyễn
, , ,
Hiểu bài toán
Bài toán yêu cầu tìm số lượng ký tự tối thiểu cần in ra từ một xâu S có độ dài N sao cho mọi ký tự trong xâu ban đầu đều được 'bảo toàn' theo quy tắc: một ký tự có thể được giữ lại nếu nó không bị xóa do nằm trong một cặp 'XO' hoặc 'OX'. Cụ thể, ta có thể xóa một cặp ký tự adjacent 'X' và 'O' (dù thứ tự nào) để giảm độ dài xâu. Mục tiêu là tìm độ dài xâu cuối cùng sau khi thực hiện các phép xóa tối ưu. Nói cách khác, bài toán tìm số lượng ký tự còn lại sau khi loại bỏ tối đa các cặp 'XO' hoặc 'OX' không trùng lặp.
Các cách tiếp cận
Cách Duyệt và loại bỏ trực tiếp (Greedy)
#include <bits/stdc++.h>
using namespace std;
int main() {
ios::sync_with_stdio(0);
cin.tie(0);
// freopen("STRING.inp", "r", stdin);
// freopen("STRING.out", "w", stdout);
int n;
string s;
cin >> n >> s;
int removed = 0;
// Duyệt từ trái sang phải, nếu tìm thấy cặp XO hoặc OX thì loại bỏ chúng
// Bằng cách đánh dấu hoặc xây dựng xâu mới, ở đây ta dùng biến đếm.
for (int i = 0; i < n - 1; ) {
if ((s[i] == 'O' && s[i+1] == 'X') || (s[i] == 'X' && s[i+1] == 'O')) {
removed += 2; // Loại bỏ 2 ký tự
i += 2; // Nhảy qua 2 ký tự tiếp theo
} else {
i++;
}
}
cout << n - removed;
return 0;
}
- Time Complexity: O(n)
- Space Complexity: O(1)
Cách tiếp cận này giả định rằng ta có thể duyệt qua xâu và loại bỏ các cặp 'XO' hoặc 'OX' một cách greedily (tham lam) từ trái sang phải. Nếu ta gặp một cặp hợp lệ, ta đếm chúng là đã bị xóa và nhảy qua 2 vị trí. Số ký tự còn lại là tổng độ dài ban đầu trừ đi số ký tự đã bị xóa. Tuy nhiên, cách này có thể không tối ưu trong mọi trường hợp nếu việc loại bỏ một cặp sớm làm cản trở các cặp khác, nhưng với quy tắc đơn giản 'XO'/'OX', thường cách này hoạt động.
Cách Quy hoạch động (Dynamic Programming)
#include <bits/stdc++.h>
using namespace std;
int main() {
ios::sync_with_stdio(0);
cin.tie(0);
// freopen("STRING.inp", "r", stdin);
// freopen("STRING.out", "w", stdout);
int n;
string s;
cin >> n >> s;
// dp[i] là độ dài xâu con kết thúc tại i không chứa cặp XO/OX
// Hoặc cách khác: dp[i] là số ký tự tối đa có thể xóa từ s[0...i]
// Công thức: Nếu s[i] và s[i-1] là cặp XO/OX và chưa bị xóa trước đó:
// dp[i] = dp[i-2] + 2
// Ngược lại:
// dp[i] = dp[i-1]
int dp[100005]; // Giả sử n <= 100000
dp[0] = 0;
if (n >= 1) dp[1] = 0; // Không thể xóa 1 ký tự
for (int i = 1; i < n; i++) {
// Kiểm tra xem có thể tạo thành cặp với ký tự trước không
if ((s[i] == 'O' && s[i-1] == 'X') || (s[i] == 'X' && s[i-1] == 'O')) {
// Nếu tạo thành cặp, ta có thể xóa 2 ký tự này
// Trạng thái tốt nhất trước cặp này là tại i-2
dp[i+1] = max(dp[i], dp[i-1] + 2);
} else {
dp[i+1] = dp[i];
}
}
// Số ký tự còn lại = n - số ký tự tối đa có thể xóa
// Tuy nhiên, DP này đang tính số ký tự xóa tối đa?
// Thực tế, bài toán này yêu cầu xóa tối đa các cặp không giao nhau.
// Ta có thể dùng DP để đếm số cặp tối đa: f[i] là số cặp tối đa từ 0 đến i.
// f[i] = f[i-1]
// Nếu (s[i-1], s[i]) là cặp: f[i] = max(f[i], f[i-2] + 1)
// Kết quả: n - 2 * f[n-1]
int f[100005];
f[0] = 0;
for (int i = 1; i < n; i++) {
f[i] = f[i-1]; // Giả sử không tạo cặp tại i
if ((s[i] == 'O' && s[i-1] == 'X') || (s[i] == 'X' && s[i-1] == 'O')) {
if (i >= 2) {
f[i] = max(f[i], f[i-2] + 1);
} else {
f[i] = max(f[i], 1);
}
}
}
cout << n - 2 * f[n-1];
return 0;
}
- Time Complexity: O(n)
- Space Complexity: O(n)
Đây là cách tiếp cận chính xác và mạnh mẽ nhất. Bài toán quy về bài toán tìm số lượng cặp 'XO' hoặc 'OX' không giao nhau nhiều nhất. Định nghĩa dp[i] (hoặc f[i]) là số cặp tối đa trong xâu con kết thúc tại i.
- Nếu s[i] và s[i-1] tạo thành cặp hợp lệ, ta có thể chọn cặp này (cộng thêm 1 vào số cặp tối đa tại i-2) hoặc bỏ qua nó (giữ nguyên số cặp tại i-1).
- Ta lấy giá trị lớn hơn.
- Kết quả cuối cùng là độ dài ban đầu trừ đi 2 nhân với số cặp tối đa tìm được.
Cách Đếm số lượng ký tự
#include <bits/stdc++.h>
using namespace std;
int main() {
ios::sync_with_stdio(0);
cin.tie(0);
// freopen("STRING.inp", "r", stdin);
// freopen("STRING.out", "w", stdout);
int n;
string s;
cin >> n >> s;
int cntX = 0, cntO = 0;
for (char c : s) {
if (c == 'X') cntX++;
else cntO++;
}
// Logic: Ta có thể xóa tối đa min(cntX, cntO) cặp.
// Mỗi cặp bao gồm 1 X và 1 O.
// Nếu ta có thể ghép chúng thành các cặp XO hoặc OX.
// Vì các ký tự có thể nằm rải rác, nhưng ta luôn có thể chọn ra min(cntX, cntO) cặp.
// Ví dụ: X...X O...O. Ta có thể lấy X đầu và O cuối, hoặc X cuối O đầu.
// Miễn là số lượng đủ.
// Tuy nhiên, có một ngoại lệ: Nếu sau khi xóa hết các cặp, còn lại 1 ký tự?
// Không, bài này xóa theo cặp adjacent.
// Nhưng về mặt ngữ nghĩa, nếu ta có thể xóa bất kỳ cặp XO/OX nào (không nhất thiết adjacent)?
// Đề bài không rõ ràng lắm về việc adjacent hay không.
// Nhưng nhìn vào các solution khác, họ xử lý adjacent.
// Nếu xử lý adjacent, cách đếm số lượng này chỉ đúng khi ta có thể tái sắp xếp hoặc xử lý greedily.
// Nhưng thực tế, nếu chỉ xét adjacent, ta không thể dùng cntX, cntO trực tiếp.
// Tuy nhiên, có một cách nhìn khác:
// Nếu ta xét các ký tự còn lại sau khi xóa hết cặp XO/OX adjacent.
// Các ký tự còn lại sẽ là dãy các X hoặc O liên tiếp (ví dụ: XXX, OOO).
// Nếu ta có dãy XXX, ta không thể xóa bất kỳ ký tự nào.
// Nếu ta có XO, ta xóa được.
// Vậy kết quả là: n - 2 * min(số cặp có thể tạo).
// Số cặp có thể tạo adjacent là gì?
// Nó chính là kết quả của thuật toán贪心 hoặc DP.
// Có một cách giải khác nếu bài toán cho phép xóa bất kỳ cặp XO/OX nào trong xâu (không cần adjacent):
// Khi đó, số cặp tối đa là min(cntX, cntO).
// Kết quả là n - 2 * min(cntX, cntO).
// Dưới đây là code cho giả thuyết 'không cần adjacent' (nếu đề bài thực sự là vậy):
// nhưng các solution mẫu cho thấy họ xử lý adjacent.
cout << n - 2 * min(cntX, cntO);
return 0;
}
- Time Complexity: O(n)
- Space Complexity: O(1)
Giả sử bài toán cho phép xóa bất kỳ cặp 'X' và 'O' nào (không cần chúng ở cạnh nhau), thì số lượng cặp tối đa có thể xóa là số lượng của ký tự ít hơn giữa 'X' và 'O'. Khi đó, số ký tự còn lại là tổng số ký tự trừ đi 2 lần số cặp. Tuy nhiên, nếu bài toán yêu cầu xóa các cặp adjacent (như các solution code cho thấy), thì cách này chỉ là một ước lượng và có thể sai lệch nếu các ký tự bị cách biệt nhau. Trong hầu hết các trường hợp 'In xâu' dạng này, nếu không có ràng buộc adjacent, đây là lời giải O(1) logic (sau khi đếm).
Phân tích độ phức tạp
| Cách tiếp cận | Time | Space | Tên |
|---|---|---|---|
| 1 | O(n) | O(1) | Duyệt và loại bỏ trực tiếp (Greedy) |
| 2 | O(n) | O(n) | Quy hoạch động (Dynamic Programming) |
| 3 | O(n) | O(1) | Đếm số lượng ký tự |
Bài học kinh nghiệm
- Bài toán có thể được hiểu là tìm cách loại bỏ tối đa các cặp ký tự 'XO' hoặc 'OX' để thu được xâu ngắn nhất.
- Nếu các cặp phải là adjacent (liền kề), ta có thể dùng Quy hoạch động hoặc Tham lam để đếm số cặp tối đa.
- Nếu các cặp có thể nằm tách rời trong xâu, số cặp tối đa đơn giản là min(số lượng 'X', số lượng 'O').
Lỗi thường gặp
- Lầm tưởng rằng có thể đếm số cặp bằng cách lấy tổng số 'X' và 'O' chia 2, mà không cần quan tâm đến vị trí của chúng (chỉ đúng nếu có thể chọn bất kỳ cặp nào).
- Bỏ qua việc xử lý biên (ví dụ: xâu độ dài 0 hoặc 1).
- Lầm tưởng rằng thuật toán Tham lam duyệt từ trái sang phải luôn tìm được tối ưu (đôi khi cần duyệt lại hoặc dùng DP).
Bình luận