Hướng dẫn giải của [2026-2027] Đề minh họa THPT Phú Thọ - Câu 4
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
Cho hai xâu ~a, b~ và xâu ~c~ có độ dài ~|a|+|b|~; cần chọn cách trộn xen kẽ ~a~ và ~b~ sao cho xâu trộn khác ~c~ ở ít vị trí nhất. Kết quả chính là số ký tự tối thiểu của ~c~ phải thay đổi.
Sub 1: Vét cạn mọi cách trộn — dùng khi ~|a|, |b| \le 10~
Quay lui: ở mỗi bước lấy ký tự đầu của ~a~ hoặc của ~b~ đặt vào vị trí tiếp theo của xâu trộn, cộng 1 vào chi phí nếu khác ký tự tương ứng của ~c~, cắt nhánh khi chi phí đã không tốt hơn đáp án tốt nhất. Có tối đa ~\binom{20}{10}~ cách trộn. Nếu chỉ nộp sub này: đúng 8/20 test.
Sub 2: Quy hoạch động — ~O(|a| \cdot |b|)~
Gọi ~dp[i][j]~ là số ký tự phải đổi ít nhất khi đã dùng ~i~ ký tự đầu của ~a~ và ~j~ ký tự đầu của ~b~ để tạo ~i+j~ ký tự đầu của ~c~. Ký tự thứ ~i+j~ của xâu trộn đến từ ~a_i~ hoặc ~b_j~, nên ~dp[i][j] = \min(dp[i-1][j] + [a_i \ne c_{i+j}],\ dp[i][j-1] + [b_j \ne c_{i+j}])~. Đáp án là ~dp[|a|][|b|]~. Nếu chỉ nộp sub này: đúng 20/20 test.
Chương trình hoàn chỉnh
Main đọc số truy vấn và ba xâu từ file CAU4.INP; xâu ngắn (~|a|, |b| \le 10~) gọi sub1, ngược lại gọi sub2. Khi đi thi nên viết như vậy: sub sau có sai hoặc chưa kịp làm thì vẫn ăn điểm sub trước.
#include <bits/stdc++.h>
using namespace std;
string a, b, c;
int best;
// Sub 1: vét cạn mọi cách trộn xen kẽ (quay lui), đếm số ký tự khác c — dùng khi |a|,|b| <= 10
void dfs(int i, int j, int cost) {
if (cost >= best) return;
if (i == (int)a.size() && j == (int)b.size()) { best = cost; return; }
int k = i + j;
if (i < (int)a.size()) dfs(i + 1, j, cost + (a[i] != c[k]));
if (j < (int)b.size()) dfs(i, j + 1, cost + (b[j] != c[k]));
}
void sub1() {
best = INT_MAX;
dfs(0, 0, 0);
printf("%d\n", best);
}
// Sub 2: quy hoạch động O(|a|*|b|). dp[i][j] = số ký tự đổi ít nhất khi đã lấy i ký tự của a
// và j ký tự của b để tạo c[0..i+j-1].
void sub2() {
int n = a.size(), m = b.size();
vector<vector<int>> dp(n + 1, vector<int>(m + 1, INT_MAX / 2));
dp[0][0] = 0;
for (int i = 0; i <= n; i++)
for (int j = 0; j <= m; j++) {
if (i > 0) dp[i][j] = min(dp[i][j], dp[i - 1][j] + (a[i - 1] != c[i + j - 1]));
if (j > 0) dp[i][j] = min(dp[i][j], dp[i][j - 1] + (b[j - 1] != c[i + j - 1]));
}
printf("%d\n", dp[n][m]);
}
int main() {
freopen("CAU4.INP", "r", stdin);
freopen("CAU4.OUT", "w", stdout);
ios::sync_with_stdio(false); cin.tie(nullptr);
int t;
cin >> t;
while (t--) {
cin >> a >> b >> c;
if (a.size() <= 10 && b.size() <= 10) sub1();
else sub2();
}
return 0;
}
Bình luận