Hướng dẫn giải của Trùng nhau (Đề tuyển sinh 10 Chuyên Quảng Trị 2024-2025)
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
Hai album, mỗi album có các số hiệu khác nhau. Cần tìm các số hiệu có mặt ở cả hai album, in ra số lượng và danh sách theo thứ tự tăng dần (nếu không có thì in 0).
Sub 1: Vét cạn — ~O(n \cdot m)~, dùng khi ~n, m \le 7500~
Với mỗi con tem của album 1, duyệt cả album 2 để tìm số hiệu giống nhau. Nếu tìm thấy thì ghi nhận và chuyển sang con tem tiếp theo. Cuối cùng sắp xếp danh sách kết quả. Nếu chỉ nộp sub này: đúng 16/20 test (đúng hết các test trong miền, 4 test lớn bị quá giờ).
Sub 2: Sắp xếp và hai con trỏ — ~O((n + m) \log(n + m))~
Sắp xếp cả hai album. Dùng hai chỉ số ~i, j~ chạy trên hai dãy: nếu hai số bằng nhau thì ghi nhận và tăng cả hai; nếu không thì tăng chỉ số của số nhỏ hơn. Kết quả đã sắp xếp sẵn.
Bẫy cần chú ý: trường hợp không có con tem trùng nhau phải in đúng một số ~0~, không in dòng trống; số hiệu lên tới ~10^9~ nên dùng long long.
Nếu chỉ nộp sub này: đúng 20/20 test.
Chương trình hoàn chỉnh
main đọc dữ liệu. Nếu ~n, m \le 7500~ thì gọi sub1, còn lại gọi sub2. Đầu main có freopen vì máy chấm đọc/ghi file CAU3.INP, CAU3.OUT.
#include <bits/stdc++.h>
using namespace std;
int n, m;
long long a[100005]; // album 1
long long b[100005]; // album 2
vector<long long> ans; // cac con tem trung nhau (theo thu tu tang dan)
// Sub 1: vet can O(n * m) - voi moi con tem cua album 1, do tim trong album 2
void sub1() {
for (int i = 1; i <= n; i++)
for (int j = 1; j <= m; j++)
if (a[i] == b[j]) {
ans.push_back(a[i]);
break; // trong cung mot album cac con tem khac nhau nen dung ngay
}
sort(ans.begin(), ans.end());
}
// Sub 2: sap xep hai day roi dung hai con tro - O((n + m) log(n + m))
void sub2() {
vector<long long> x(a + 1, a + n + 1), y(b + 1, b + m + 1);
sort(x.begin(), x.end());
sort(y.begin(), y.end());
int i = 0, j = 0;
while (i < n && j < m) {
if (x[i] == y[j]) {
ans.push_back(x[i]);
i++; j++;
} else if (x[i] < y[j]) i++;
else j++;
}
}
int main() {
freopen("CAU3.INP", "r", stdin); // may cham doc/ghi file
freopen("CAU3.OUT", "w", stdout);
ios::sync_with_stdio(false);
cin.tie(nullptr);
cin >> n >> m;
for (int i = 1; i <= n; i++) cin >> a[i];
for (int j = 1; j <= m; j++) cin >> b[j];
// Du lieu nho (n, m <= 7500): sub1 vet can; du lieu lon: sub2 sap xep
if (n <= 7500 && m <= 7500) sub1();
else sub2();
if (ans.empty()) {
cout << 0 << "\n";
} else {
cout << ans.size() << "\n";
for (size_t k = 0; k < ans.size(); k++)
cout << ans[k] << (k + 1 < ans.size() ? " " : "\n");
}
return 0;
}
Bình luận