Hướng dẫn giải của Số chính phương (đề HSG 9 Phú Thọ 2022-2023)
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
Tìm số chính phương nhỏ nhất không xuất hiện trong dãy. Số chính phương tính cả 0, nên thử lần lượt 0, 1, 4, 9, ... cho đến khi gặp số không có trong dãy.
Sub 1: Vét cạn — ~O(n^2)~, dùng khi ~n \le 1000~
Với mỗi số chính phương ~k^2~ lần lượt thử, quét cả dãy xem có số đó không. Số lần thử không quá ~n+1~.
Nếu chỉ nộp sub này: đúng 42/50 test.
Sub 2: Sắp xếp và tìm nhị phân — ~O(n \log n)~
Sắp dãy một lần rồi dùng tìm nhị phân cho mỗi số chính phương. Lưu ý ~a_i~ đến ~10^{12}~ nên dùng kiểu long long cho cả ~k^2~.
Nếu chỉ nộp sub này: đúng 50/50 test.
Chương trình hoàn chỉnh
Hàm main đọc dữ liệu rồi chọn sub theo kích thước: dữ liệu nhỏ gọi sub 1 (vét cạn), dữ liệu lớn gọi sub cuối. Khi đi thi, nên nộp đầy đủ như vậy: nếu sub sau sai hoặc chưa kịp làm thì vẫn ăn điểm các sub trước.
#include <bits/stdc++.h>
using namespace std;
int n;
vector<long long> a; // dãy đề cho, 0 <= a_i <= 10^12
// Sub 1: vét cạn — thử lần lượt 0, 1, 4, 9, ...; mỗi số chính phương quét cả dãy xem có không. O(n^2)
void sub1() {
for (long long k = 0; ; k++) {
long long sq = k * k;
bool found = false;
for (int i = 0; i < n; i++)
if (a[i] == sq) { found = true; break; }
if (!found) { cout << sq << "\n"; return; }
}
}
// Sub 2: sắp xếp dãy rồi tìm nhị phân từng số chính phương. O(n log n)
void sub2() {
vector<long long> b(a);
sort(b.begin(), b.end());
for (long long k = 0; ; k++) {
long long sq = k * k;
if (!binary_search(b.begin(), b.end(), sq)) { cout << sq << "\n"; return; }
}
}
int main() {
ios::sync_with_stdio(false); cin.tie(nullptr);
cin >> n;
a.resize(n);
for (int i = 0; i < n; i++) cin >> a[i];
if (n <= 1000) sub1(); // dữ liệu nhỏ: vét cạn
else sub2();
return 0;
}
Bình luận