Hướng dẫn giải của Chọn vị kem (đề Vĩnh Phúc 2021)
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ố bộ ba đỉnh đôi một không kề nhau (tập độc lập kích thước 3) trong đồ thị ~n~ đỉnh, ~m~ cạnh. Lưu ý: một số test thật có cặp xấu bị lặp (kể cả viết ngược thứ tự) dù đề nói không trùng, nên chương trình loại cạnh lặp khi đọc.
Sub 1: Vét cạn — ~O(n^3)~, dùng khi ~n \le 400~
Duyệt mọi bộ ba ~i < j < k~ và kiểm tra cả ba cặp trong ma trận kề. Nếu chỉ nộp sub này: đúng 28/28 test (với giới hạn này chạy kịp thời gian trên máy thử), nhưng với ~n = 2000~ nói chung sẽ chậm.
Sub 2: Bù trừ và bitset — ~O(n^3 / 64)~ hoặc ~O(m \cdot n / 64)~
Số bộ ba có ít nhất một cặp xấu là ~m(n-2) - \sum \binom{d_v}{2} + T~, với ~d_v~ là bậc của đỉnh ~v~ và ~T~ là số tam giác (gọi ~t_j~ là số bộ ba có đúng ~j~ cạnh thì ~m(n-2) = t_1 + 2t_2 + 3t_3~, ~\sum \binom{d_v}{2} = t_2 + 3t_3~, ~T = t_3~). Số tam giác tính bằng bitset: với mỗi cạnh ~(u,v)~ cộng ~|N(u) \cap N(v)|~ rồi chia cho 3. Đáp án là ~\binom{n}{3}~ trừ đi số bộ ba xấu. Nếu chỉ nộp sub này: đúng 28/28 test.
Chương trình hoàn chỉnh
Hàm main đọc file cream.inp, ghi cream.out; ~n \le 400~ gọi sub1 (22 test), lớn hơn gọi sub2 (6 test). 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, m;
bitset<2005> adj[2005];
int deg[2005];
vector<pair<int, int>> edges;
long long C3(long long x) { return x * (x - 1) * (x - 2) / 6; }
// Sub 1: vét cạn mọi bộ ba — O(n^3), dùng khi n <= 400
void sub1() {
long long cnt = 0;
for (int i = 1; i <= n; i++)
for (int j = i + 1; j <= n; j++) {
if (adj[i][j]) continue;
for (int k = j + 1; k <= n; k++)
if (!adj[i][k] && !adj[j][k]) cnt++;
}
cout << cnt << "\n";
}
// Sub 2: bù trừ — tổng số bộ ba trừ đi số bộ ba có ít nhất một cặp xấu
// bad = m*(n-2) - tổng C(deg,2) + số tam giác; tam giác đếm bằng bitset: mỗi cạnh (u,v) cho |adj[u] & adj[v]|
void sub2() {
long long total = C3(n);
long long A = (long long)m * (n - 2), B = 0, tri = 0;
for (int i = 1; i <= n; i++) B += (long long)deg[i] * (deg[i] - 1) / 2;
for (auto &e : edges) tri += (adj[e.first] & adj[e.second]).count();
tri /= 3; // mỗi tam giác được đếm 3 lần (một lần cho mỗi cạnh)
cout << total - (A - B + tri) << "\n";
}
int main() {
freopen("cream.inp", "r", stdin);
freopen("cream.out", "w", stdout);
ios::sync_with_stdio(false); cin.tie(nullptr);
cin >> n >> m;
for (int i = 0; i < m; i++) {
int a, b; cin >> a >> b;
if (a == b || adj[a][b]) continue; // bỏ cặp trùng (test thật có cặp bị lặp dù đề nói không)
adj[a][b] = adj[b][a] = 1;
deg[a]++; deg[b]++;
edges.push_back({a, b});
}
m = edges.size(); // số cạnh phân biệt thực sự
if (n <= 400) sub1();
else sub2();
return 0;
}
Bình luận