Hướng dẫn giải của TKNP01: Thấy hay không thấy
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.
Hướng dẫn giải
Cho dãy ~n~ số và ~Q~ truy vấn, mỗi truy vấn hỏi giá trị ~X~ có xuất hiện trong dãy hay không (in 1 nếu có, -1 nếu không). Với ~n, Q \le 10^5~, quét cả dãy cho mỗi truy vấn là quá chậm nên cần tìm kiếm nhanh.
Sub 1: Vét cạn — ~O(n \cdot Q)~, dùng khi ~n \cdot Q \le 10^7~
Mỗi truy vấn quét toàn bộ dãy. Nếu chỉ nộp sub này: đúng 16/20 test.
Sub 2: Sắp xếp và tìm nhị phân — ~O((n + Q) \log n)~
Sắp xếp một bản sao của dãy, mỗi truy vấn dùng tìm nhị phân. Giá trị có thể âm và lên tới ~10^{18}~ 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 \cdot Q \le 10^7~ gọi sub1, ngược lại gọi sub2.
#include <bits/stdc++.h>
using namespace std;
int n, Q;
vector<long long> A;
vector<long long> qs;
// Sub 1: vet can. Moi truy van quet ca day. O(n*Q). Dung khi n*Q <= 10^7.
void sub1() {
for (long long x : qs) {
bool found = false;
for (int i = 0; i < n && !found; i++)
if (A[i] == x) found = true;
cout << (found ? 1 : -1) << "\n";
}
}
// Sub 2: sap xep day, moi truy van tim nhi phan. O((n + Q) log n).
void sub2() {
vector<long long> s = A;
sort(s.begin(), s.end());
for (long long x : qs)
cout << (binary_search(s.begin(), s.end(), x) ? 1 : -1) << "\n";
}
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
cin >> n >> Q;
A.resize(n);
for (int i = 0; i < n; i++) cin >> A[i];
qs.resize(Q);
for (int i = 0; i < Q; i++) cin >> qs[i];
if ((long long)n * Q <= 10000000) sub1();
else sub2();
return 0;
}
Bình luận