Hướng dẫn giải của Tham quan du lịch (đề Phú Yên 2021)
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 danh sách điểm tham quan của hai đoàn khách, cần in các điểm xuất hiện trong cả hai danh sách, theo thứ tự tăng dần. Với N ≤ 50 có thể làm nhiều cách, miễn là đọc đúng từng dòng dữ liệu (dòng 2 và dòng 3 là hai danh sách có độ dài khác nhau, nên phải đọc bằng getline).
Sub 1: Vét cạn — ~O(N \cdot (k_1 + k_2))~
Duyệt lần lượt các điểm i = 1..N, với mỗi điểm dò tìm trong danh sách của đoàn 1 và đoàn 2 xem nó có mặt không. Nếu có mặt ở cả hai thì in ra. Cách này đúng theo đề, chỉ chậm vì phải dò tuyến tính nhiều lần.
Kết quả chấm: đạt 25/25 test.
#include <bits/stdc++.h>
using namespace std;
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
if (fopen("BAI2.INP", "r")) { freopen("BAI2.INP", "r", stdin); freopen("BAI2.OUT", "w", stdout); }
int n;
cin >> n;
string line;
getline(cin, line); // bo phan con lai cua dong 1
getline(cin, line);
stringstream s1(line);
vector<int> a;
int x;
while (s1 >> x) a.push_back(x);
getline(cin, line);
stringstream s2(line);
vector<int> b;
while (s2 >> x) b.push_back(x);
// Vet can: voi moi diem i tu 1..N, kiem tra i co trong ca hai danh sach khong
bool first = true;
for (int i = 1; i <= n; i++) {
bool inA = false, inB = false;
for (int v : a) if (v == i) inA = true;
for (int v : b) if (v == i) inB = true;
if (inA && inB) {
if (!first) cout << " ";
cout << i;
first = false;
}
}
cout << "\n";
return 0;
}
Sub 2: Dùng mảng đánh dấu — ~O(N + k_1 + k_2)~
Tạo hai mảng inA, inB kích thước N+1, đánh dấu true những điểm có trong danh sách của mỗi đoàn. Sau đó duyệt i = 1..N và in i nếu inA[i] và inB[i] đều đúng. Việc tra cứu nhờ mảng đánh dấu là O(1) nên không phải dò lại danh sách. Lưu ý kiểm tra chỉ số 1..N trước khi đánh dấu.
Kết quả chấm: đạt 25/25 test.
#include <bits/stdc++.h>
using namespace std;
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
if (fopen("BAI2.INP", "r")) { freopen("BAI2.INP", "r", stdin); freopen("BAI2.OUT", "w", stdout); }
int n;
cin >> n;
string line;
getline(cin, line); // bo phan con lai cua dong 1
// Danh dau cac diem cua doan 1 (mang chi so 1..N)
vector<bool> inA(n + 1, false), inB(n + 1, false);
getline(cin, line);
stringstream s1(line);
int x;
while (s1 >> x) if (x >= 1 && x <= n) inA[x] = true;
getline(cin, line);
stringstream s2(line);
while (s2 >> x) if (x >= 1 && x <= n) inB[x] = true;
// Diem chung: cung xuat hien trong ca hai danh sach, in theo thu tu tang dan
bool first = true;
for (int i = 1; i <= n; i++) {
if (inA[i] && inB[i]) {
if (!first) cout << " ";
cout << i;
first = false;
}
}
cout << "\n";
return 0;
}
Bình luận