Hướng dẫn giải của Xếp nhóm (Đề Long An 2021)
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
Đếm số nhóm: mỗi điểm có từ 2 đội trở lên là một nhóm, các đội có điểm riêng gộp thành một nhóm.
Sub 1: Vét cạn, ~O(N^2)~
Với mỗi đội đếm số đội cùng điểm; ghi nhận một nhóm ở lần đầu gặp điểm có từ 2 đội trở lên, và một nhóm chung cho các đội điểm riêng. Đúng 15/20 test.
Sub 2: Mảng tần suất, ~O(N + 10^6)~
Đếm tần suất từng điểm (điểm ≤ 10^6). Đúng 20/20 test.
Chương trình hoàn chỉnh
main: N ≤ 1000 gọi sub1, còn lại gọi sub2. Khi đi thi nên viết như vậy: sub sau có sai hoặc chưa kịp làm thì vẫn ăn điểm sub trước.
#include <bits/stdc++.h>
using namespace std;
int N;
vector<int> a;
// Sub 1: vet can. Voi moi doi i, dem so doi co cung diem; neu la lan dau gap diem do thi
// dem mot nhom (nhom cac doi bang diem). Doi co diem duy nhat se gop chung thanh mot nhom.
void sub1() {
int groups = 0;
bool haveUnique = false;
for (int i = 0; i < N; i++) {
int cnt = 0;
bool first = true;
for (int j = 0; j < N; j++)
if (a[j] == a[i]) {
cnt++;
if (j < i) first = false; // da xet diem nay truoc do
}
if (cnt == 1) haveUnique = true;
else if (first) groups++; // nhom cac doi co cung diem
}
if (haveUnique) groups++; // tat ca cac doi co diem rieng biet gop thanh mot nhom
cout << groups << "\n";
}
// Sub 2: dem tan suat diem (diem <= 10^6) bang mang dem.
// So nhom = so diem xuat hien >= 2 lan + 1 neu co it nhat mot diem xuat hien dung 1 lan.
void sub2() {
const int MAXV = 1000000;
vector<int> freq(MAXV + 1, 0);
for (int x : a) freq[x]++;
int groups = 0;
bool haveUnique = false;
for (int v = 0; v <= MAXV; v++) {
if (freq[v] >= 2) groups++;
else if (freq[v] == 1) haveUnique = true;
}
if (haveUnique) groups++;
cout << groups << "\n";
}
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(); // it doi: vet can O(N^2)
else sub2(); // nhieu doi: dem tan suat
return 0;
}
Bình luận