Hướng dẫn giải của Cặp Palindrome
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.
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ậpTác giả: , , ,
Hiểu bài toán
Bài toán yêu cầu đếm số lượng bộ tứ chỉ số (a, b, x, y) sao cho:
- 1 <= a <= b < x <= y <= n (với n là độ dài chuỗi)
- Chuỗi con s[a..b] là một palindrome
- Chuỗi con s[x..y] là một palindrome Điều này có nghĩa là chúng ta cần tìm số cách chọn hai chuỗi con palindrome không giao nhau (disjoint), trong đó chuỗi palindrome thứ nhất nằm hoàn toàn bên trái chuỗi palindrome thứ hai. Chuỗi s có độ dài tối đa 2000 kí tự.
Các cách tiếp cận
Cách Quy hoạch động kết hợp tiền tố và hậu tố
#include <bits/stdc++.h>
using namespace std;
int main() {
ifstream fin("PALIN.INP");
ofstream fout("PALIN.OUT");
string s;
fin >> s;
int n = s.size();
// isPal[i][j] = true nếu s[i..j] là palindrome
vector<vector<bool>> isPal(n, vector<bool>(n, false));
// leftPal[i] = số lượng palindrome bắt đầu tại index i
// rightPal[i] = số lượng palindrome kết thúc tại index i
vector<long long> leftPal(n, 0);
vector<long long> rightPal(n, 0);
// Bước 1: Dùng DP để tìm tất cả palindrome
for (int len = 1; len <= n; len++) {
for (int i = 0; i + len - 1 < n; i++) {
int j = i + len - 1;
if (len == 1) isPal[i][j] = true;
else if (len == 2) isPal[i][j] = (s[i] == s[j]);
else isPal[i][j] = (s[i] == s[j] && isPal[i+1][j-1]);
if (isPal[i][j]) {
leftPal[i]++; // Có thêm 1 palindrome bắt đầu tại i
rightPal[j]++; // Có thêm 1 palindrome kết thúc tại j
}
}
}
// Bước 2: Tính tổng tiền tố (prefix sum) cho dãy leftPal
// prefixSum[i] = tổng leftPal[0] đến leftPal[i]
vector<long long> prefixSum(n, 0);
if (n > 0) prefixSum[0] = leftPal[0];
for (int i = 1; i < n; i++) {
prefixSum[i] = prefixSum[i-1] + leftPal[i];
}
// Bước 3: Tính tổng hậu tố (suffix sum) cho dãy rightPal
// suffixSum[i] = tổng rightPal[i] đến rightPal[n-1]
vector<long long> suffixSum(n+1, 0);
for (int i = n-1; i >= 0; i--) {
suffixSum[i] = suffixSum[i+1] + rightPal[i];
}
// Bước 4: Đếm các cặp palindrome không giao nhau
long long total = 0;
// Duyệt qua điểm chia tách k (palindrome bên trái kết thúc trước hoặc tại k)
// Palindrome bên trái: [i, j] với j <= k
// Palindrome bên phải: [x, y] với x > k
for (int k = 0; k < n - 1; k++) {
long long countLeft = prefixSum[k]; // Số palindrome kết thúc <= k
long long countRight = suffixSum[k+1]; // Số palindrome bắt đầu >= k+1
total += countLeft * countRight;
}
fout << total << endl;
return 0;
}
- Time Complexity: O(n^2)
- Space Complexity: O(n^2)
Cách tiếp cận này chia bài toán thành các bước rõ ràng:
- Tìm tất cả palindrome: Sử dụng quy hoạch động (DP) để kiểm tra mọi chuỗi con s[i..j] xem có phải palindrome không. Mảng
isPallưu kết quả. Thời gian O(n^2). - Đếm số lượng: Tạo hai mảng
leftPalvàrightPal.leftPal[i]: đếm số palindrome bắt đầu tại index i.rightPal[i]: đếm số palindrome kết thúc tại index i.
- Tối ưu hóa việc đếm: Thay vì lồng 4 vòng lặp để xét (a, b, x, y), ta dùng tiền tố và hậu tố.
- Tính
prefixSum[k]: tổng số palindrome kết thúc tại các vị trí từ 0 đến k (tức là nằm hoàn toàn bên trái hoặc bằng k). - Tính
suffixSum[k]: tổng số palindrome bắt đầu tại các vị trí từ k đến n-1.
- Tính
- Ghép cặp: Với mỗi điểm chia
k, số cặp hợp lệ làprefixSum[k] * suffixSum[k+1]. Tổng tất cả các điểm chia cho kết quả cuối cùng. Độ phức tạp là O(n^2) thời gian (vì DP) và O(n^2) bộ nhớ (lưu ma trận palindrome), phù hợp với n <= 2000.
Cách Bрут Phorce (Brute Force)
#include <iostream>
#include <fstream>
#include <string>
#include <vector>
using namespace std;
// Hàm kiểm tra xem một chuỗi con có phải là palindrome không
bool is_palindrome(const string& s, int l, int r) {
while (l < r) {
if (s[l] != s[r]) return false;
l++;
r--;
}
return true;
}
void solve() {
ifstream fin("PALIN.INP");
ofstream fout("PALIN.OUT");
string s;
fin >> s;
int n = s.length();
long long ans = 0;
// Duyệt tất cả bộ chỉ số (a, b, x, y)
// a, b: chỉ số của palindrome thứ nhất
// x, y: chỉ số của palindrome thứ hai
for (int a = 0; a < n; a++) {
for (int b = a; b < n; b++) {
if (is_palindrome(s, a, b)) {
for (int x = b + 1; x < n; x++) {
for (int y = x; y < n; y++) {
if (is_palindrome(s, x, y)) {
ans++;
}
}
}
}
}
}
fout << ans << endl;
}
int main() {
solve();
return 0;
}
- Time Complexity: O(n^5)
- Space Complexity: O(1)
Đây là giải pháp naïve, trực tiếp nhất.
- Lặp qua tất cả các khả năng cho cặp palindrome thứ nhất (a, b) bằng 2 vòng lặp.
- Với mỗi cặp (a, b) là palindrome, lặp qua tất cả các khả năng cho cặp palindrome thứ hai (x, y) sao cho x > b (không giao nhau) bằng 2 vòng lặp nữa.
- Kiểm tra tính palindrome cho từng cặp (a, b) và (x, y).
- Nếu cả hai đều là palindrome, tăng biến đếm. Độ phức tạp thời gian là O(n^5) vì có 4 vòng lặp lồng nhau (O(n^4)) và mỗi lần kiểm tra palindrome mất O(n). Với n=2000, cách này chắc chắn bị Time Limit Exceeded (TLE).
Phân tích độ phức tạp
| Cách tiếp cận | Time | Space | Tên |
|---|---|---|---|
| 1 | O(n^2) | O(n^2) | Quy hoạch động kết hợp tiền tố và hậu tố |
| 2 | O(n^5) | O(1) | Bрут Phorce (Brute Force) |
Bài học kinh nghiệm
- Bài toán có thể được chia thành hai bài toán con: đếm số lượng palindrome bên trái và bên trái của một điểm tách, sau đó nhân lên.
- Sử dụng quy hoạch động để kiểm tra palindrome cho tất cả các cặp (i, j) là bước chuẩn bị cần thiết cho các giải pháp hiệu quả.
- Thay vì duyệt qua từng bộ (a, b, x, y), hãy tính toán số lượng các khả năng một cách tổng quát bằng các cấu trúc dữ liệu hỗ trợ.
Lỗi thường gặp
- Sử dụng
intcho biến kết quả (res) thay vìlong longcó thể gây tràn số (overflow). - Lỗi chỉ số (index) khi chuyển đổi từ 0-based sang 1-based hoặc ngược lại, đặc biệt trong điều kiện 'không giao nhau' (b < x hoặc b+1 <= x).
Bình luận