Hướng dẫn giải của Đếm số (Đề chọn ĐTQG Phú Thọ 2014-2015)
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 n số nguyên dương (n <= 10^6, a_i < 10^6), đếm số lượng giá trị chỉ xuất hiện đúng một lần. Đề dùng file CAU2.INP và CAU2.OUT.
Sub 1: Đếm từng số bằng vòng lặp — ~O(n^2)~, dùng khi ~n \le 5000~
Với mỗi ai, đếm số lần ai xuất hiện trong cả dãy. Nếu đúng 1 lần thì tăng bộ đếm.
Nếu chỉ nộp sub này: đúng 19/28 test (các test n lớn bị quá giờ).
Sub 2: Mảng đếm tần suất — ~O(n + 10^6)~
Vì a_i < 10^6 nên dùng mảng freq[v] đếm số lần xuất hiện của v, rồi đếm các v có freq[v] = 1. Bẫy: mảng phải có kích thước 10^6+1.
Nếu chỉ nộp sub này: đúng 28/28 test.
Chương trình hoàn chỉnh
Main đọc n, dãy a từ CAU2.INP. Nếu n <= 5000 gọi sub1, ngược lại gọi sub2.
#include <bits/stdc++.h>
using namespace std;
int n;
vector<int> a;
// Sub 1: voi moi so, dem so lan xuat hien bang vong lap — O(n^2), dung khi n <= 5000
void sub1() {
int cnt = 0;
for (int i = 0; i < n; i++) {
int c = 0;
for (int j = 0; j < n; j++)
if (a[j] == a[i]) c++;
if (c == 1) cnt++;
}
cout << cnt << "\n";
}
// Sub 2: dem tan suat bang mang dem (a_i < 10^6) — O(n + 10^6)
void sub2() {
vector<int> freq(1000001, 0);
for (int i = 0; i < n; i++) freq[a[i]]++;
int cnt = 0;
for (int v = 1; v <= 1000000; v++)
if (freq[v] == 1) cnt++;
cout << cnt << "\n";
}
int main() {
freopen("CAU2.INP", "r", stdin);
freopen("CAU2.OUT", "w", stdout);
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 <= 5000) sub1();
else sub2();
return 0;
}
Bình luận