Hướng dẫn giải của Độ giống nhau (Đề tuyển sinh 10 Chuyên Quảng Trị 2024-2025)
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
Độ giống nhau của hai số là số hàng (tính từ hàng đơn vị) mà cả hai số đều có và chữ số ở hàng đó bằng nhau. Cần tổng độ giống nhau của mọi cặp ~(i, j)~ với ~i \ne j~.
Sub 1: Xét từng cặp — ~O(n^2 \log A)~, dùng khi ~n \le 1000~
Với mỗi cặp, so sánh chữ số từ phải sang trái cho đến khi một trong hai số hết chữ số. Nếu chỉ nộp sub này: đúng 4/20 test.
Sub 2: Đếm theo hàng và chữ số — ~O(n \log A)~
Với mỗi hàng ~p~ và chữ số ~d~, nếu có ~cnt~ số có chữ số ~d~ ở hàng ~p~ thì có ~\binom{cnt}{2}~ cặp giống nhau ở hàng đó; cộng lại tất cả. Nếu chỉ nộp sub này: đúng 20/20 test.
Chương trình hoàn chỉnh
Nếu ~n \le 1000~ dùng sub 1, còn lại dùng sub 2. 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<long long> a;
// Sub 1: xet tung cap (i, j), so sanh tung chu so tu phai sang trai — dung khi n <= 1000
void sub1() {
long long ans = 0;
for (int i = 0; i < n; i++)
for (int j = i + 1; j < n; j++) {
long long x = a[i], y = a[j];
while (x > 0 && y > 0) { // het chu so cua mot so thi dung (khong tinh vi tri thieu)
if (x % 10 == y % 10) ans++;
x /= 10; y /= 10;
}
}
cout << ans << "\n";
}
// Sub 2: dem theo tung vi tri (don vi, chuc, tram, ...) va tung chu so d:
// co cnt so cung co chu so d o vi tri do, moi cap trong nhom duoc tinh dung 1 lan -> C(cnt, 2)
void sub2() {
static long long cnt[12][10];
memset(cnt, 0, sizeof cnt);
for (int i = 0; i < n; i++) {
long long x = a[i];
int p = 0;
while (x > 0) { cnt[p][x % 10]++; x /= 10; p++; }
}
long long ans = 0;
for (int p = 0; p < 12; p++)
for (int d = 0; d < 10; d++) ans += cnt[p][d] * (cnt[p][d] - 1) / 2;
cout << ans << "\n";
}
int main() {
freopen("CAU4.INP", "r", stdin);
freopen("CAU4.OUT", "w", stdout);
ios::sync_with_stdio(false); cin.tie(nullptr);
cin >> n;
a.assign(n, 0);
for (auto &x : a) cin >> x;
if (n <= 1000) sub1();
else sub2();
return 0;
}
Bình luận