Hướng dẫn giải của Bộ ba (Đề HSG 9 Phú Thọ 2021-2022)
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 bộ ~(i, j, k)~ sao cho chữ số hàng đơn vị của ~a_i~ bằng chữ số đầu của ~b_j~, chữ số hàng đơn vị của ~b_j~ bằng chữ số đầu của ~c_k~, và ba giá trị đôi một khác nhau. Các bộ có giá trị trùng được loại bằng nguyên lý bù trừ.
Sub 1: Duyệt ba vòng — ~O(m \cdot n \cdot p)~, dùng khi ~m, n, p \le 500~
Thử mọi bộ ba và kiểm tra điều kiện. Nếu chỉ nộp sub này: đúng 20/40 test.
Sub 2: Đếm theo nhóm và bù trừ — ~O(m + n + p + 10^6)~
Với mỗi ~j~, số ~i~ hợp lệ là ~A_j~ và số ~k~ hợp lệ là ~C_j~, tổng là ~\sum_j A_j C_j~. Trừ các bộ có ~a = b~, ~b = c~, ~a = c~, rồi cộng hai lần số bộ có ba giá trị bằng nhau. Nếu chỉ nộp sub này: đúng 40/40 test.
Chương trình hoàn chỉnh
Nếu ~m, n, p \le 500~ 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 m, n, p;
vector<long long> a, b, c;
long long unitD(long long v) { return v % 10; } // chu so hang don vi
long long firstD(long long v) { while (v >= 10) v /= 10; return v; } // chu so dau tien ben trai
// Sub 1: duyet tat ca bo ba (i, j, k) — O(m*n*p), dung khi m, n, p <= 500
void sub1() {
long long ans = 0;
for (int i = 0; i < m; i++)
for (int j = 0; j < n; j++) {
if (unitD(a[i]) != firstD(b[j])) continue;
for (int k = 0; k < p; k++) {
if (unitD(b[j]) != firstD(c[k])) continue;
if (a[i] == b[j] || b[j] == c[k] || a[i] == c[k]) continue; // phai doi mot khac gia tri
ans++;
}
}
cout << ans << "\n";
}
// Sub 2: dem theo nhom roi tru phan bi trung gia tri bang nguyen ly bu tru.
// Tong (khong xet trung gia tri) = sum_j A_j * C_j, voi A_j = #{i: unit(a_i) = first(b_j)},
// C_j = #{k: first(c_k) = unit(b_j)}.
// Tru cac bo co a=b (E1), b=c (E2), a=c (E3), cong lai bo ba ca 3 bang nhau (T) hai lan:
// ket qua = tong - E1 - E2 - E3 + 2*T.
void sub2() {
const int V = 1000001; // gia tri <= 10^6
vector<long long> cA(V, 0), cB(V, 0), cC(V, 0);
long long AU[10] = {0}, CF[10] = {0}, B2[10][10] = {{0}};
for (long long x : a) { cA[x]++; AU[unitD(x)]++; }
for (long long x : c) { cC[x]++; CF[firstD(x)]++; }
for (long long x : b) { cB[x]++; B2[firstD(x)][unitD(x)]++; }
long long total = 0, E1 = 0, E2 = 0, E3 = 0, T = 0;
for (int j = 0; j < n; j++) {
long long bj = b[j];
long long Aj = AU[firstD(bj)];
long long Cj = CF[unitD(bj)];
total += Aj * Cj;
if (unitD(bj) == firstD(bj)) {
E1 += cA[bj] * Cj; // a_i = b_j
E2 += Aj * cC[bj]; // b_j = c_k
}
}
for (int v = 0; v < V; v++) {
if (cA[v] > 0 && cC[v] > 0)
E3 += cA[v] * cC[v] * B2[unitD(v)][firstD(v)]; // a_i = c_k = v
if (cA[v] > 0 && cB[v] > 0 && cC[v] > 0 && unitD(v) == firstD(v))
T += cA[v] * cB[v] * cC[v]; // ca ba bang nhau
}
cout << total - E1 - E2 - E3 + 2 * T << "\n";
}
int main() {
ios::sync_with_stdio(false); cin.tie(nullptr);
cin >> m >> n >> p;
a.assign(m, 0); b.assign(n, 0); c.assign(p, 0);
for (auto &x : a) cin >> x;
for (auto &x : b) cin >> x;
for (auto &x : c) cin >> x;
if (m <= 500 && n <= 500 && p <= 500) sub1();
else sub2();
return 0;
}
Bình luận