Hướng dẫn giải của [200 đề thầy Đức] Bài 161: Cặp số có tổng bằng 0
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
Cần tìm hai chỉ số ~i < j~ sao cho ~a_i + a_j = 0~, tức ~a_j = -a_i~. Nếu không có cặp nào thì in ~-1~ ~-1~.
Sub 1: Vét cạn — ~O(N^2)~, dùng khi ~N \le 3000~
Thử mọi cặp ~i < j~ theo thứ tự ~j~ tăng dần, rồi ~i~ tăng dần, và dừng khi gặp cặp có tổng bằng ~0~.
Sub 2: Bảng băm — ~O(N \log N)~
Duyệt ~j~ từ ~1~ đến ~N~. Với mỗi ~j~, kiểm tra xem giá trị ~-a_j~ đã xuất hiện ở một vị trí ~i < j~ chưa, bằng một bảng lưu vị trí xuất hiện đầu tiên của mỗi giá trị. Nếu có thì ~(i, j)~ là cặp cần tìm; nếu không thì thêm ~a_j~ vào bảng (chỉ khi chưa có) và tiếp tục.
Bẫy cần chú ý: số ~0~ ghép với chính nó (~0 + 0 = 0~) khi có hai số ~0~ ở hai vị trí khác nhau, và phải đảm bảo ~i < j~. Giá trị ~|a_i| \le 10^9~ nên dùng long long khi tính ~-a_j~.
Chương trình hoàn chỉnh
Lưu ý: đề cho phép in cặp bất kỳ, máy chấm kiểm tra cặp in ra có thỏa ~a_i + a_j = 0~, ~i < j~ hay không. Chương trình đọc ~N~ và dãy ~a~. Nếu ~N \le 3000~ thì gọi sub1, ngược lại gọi sub2.
#include <bits/stdc++.h>
using namespace std;
int N;
vector<long long> a; // dãy a (chỉ số từ 1)
// Sub 1: vét cạn — thử mọi cặp i < j, lấy cặp đầu tiên tìm được theo thứ tự j rồi i.
// Dùng khi N <= 3000
void sub1() {
for (int j = 2; j <= N; j++)
for (int i = 1; i < j; i++)
if (a[i] + a[j] == 0) { cout << i << " " << j << "\n"; return; }
cout << -1 << " " << -1 << "\n";
}
// Sub 2: duyệt j từ 1 đến N, dùng bảng lưu vị trí đầu tiên của mỗi giá trị.
// Nếu -a[j] đã xuất hiện ở vị trí i < j thì (i, j) là cặp cần tìm. O(N log N).
void sub2() {
map<long long, int> firstPos;
for (int j = 1; j <= N; j++) {
auto it = firstPos.find(-a[j]);
if (it != firstPos.end()) { cout << it->second << " " << j << "\n"; return; }
if (!firstPos.count(a[j])) firstPos[a[j]] = j;
}
cout << -1 << " " << -1 << "\n";
}
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
cin >> N;
a.assign(N + 1, 0);
for (int i = 1; i <= N; i++) cin >> a[i];
if (N <= 3000) sub1(); // N nhỏ: vét cạn
else sub2(); // N lớn: bảng băm
return 0;
}
Bình luận