Hướng dẫn giải của [200 đề thầy Đức] Bài 198: Thu gọn mảng
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ỗi thao tác xóa hai phần tử và thêm tổng của chúng, nên tổng toàn dãy không đổi và cuối cùng ta được một số nhóm, mỗi nhóm là tổng của một tập phần tử gốc (các tập rời nhau, hợp lại bằng toàn bộ dãy). Đáp số là số nhóm có tổng chia hết cho $3$. Các phần tử còn lại gom vào một nhóm không chia hết (không tính).
Đáp số tối ưu: mỗi phần tử chia hết cho $3$ là một nhóm; ghép một phần tử dư $1$ với một phần tử dư $2$; các phần tử dư giống nhau thì lấy ba cái thành một nhóm.
Sub 1: Vét cạn bằng bitmask — ~O(3^n)~, dùng khi ~n \le 8~
Với mỗi tập con $mask$, $g[mask]$ là số nhóm chia hết cho $3$ tối đa chọn được từ $mask$. Xét phần tử thấp nhất $i$ trong $mask$: hoặc bỏ $i$, hoặc chọn một tập con chứa $i$ có tổng chia hết cho $3$ rồi cộng $1$.
Nếu chỉ nộp sub này: đúng 1/21 test (test có $n \le 8$; các test lớn bị quá giờ hoặc vượt miền).
Sub 2: Đếm theo số dư — ~O(n)~
Đếm số phần tử dư $0$, $1$, $2$ là $c0$, $c1$, $c2$. Đáp số $= c0 + \min(c1, c2) + \lfloor |c1 - c2| / 3 \rfloor$.
Nếu chỉ nộp sub này: đúng 21/21 test.
Chương trình hoàn chỉnh
main đọc tất cả các truy vấn trước. Nếu mọi truy vấn có $n \le 8$ thì gọi sub 1, còn lại gọi sub 2.
#include <bits/stdc++.h>
using namespace std;
// Nhan xet: thao tac thay hai phan tu bang tong cua chung. Moi phan tu cuoi cung la tong
// cua mot nhom cac phan tu goc, nen bai toan la: chia day thanh nhieu nhom roi nhau,
// dem so nhom co tong chia het cho 3.
int q;
vector<vector<int>> tests;
// Sub 1: vet can bitmask O(3^n), dung khi moi test co n <= 8.
// g[mask] = so nhom co tong chia het 3 (roi nhau) chon duoc tu tap phan tu mask.
void sub1() {
for (const vector<int> &a : tests) {
int n = a.size();
vector<long long> sum(1 << n, 0);
for (int mask = 1; mask < (1 << n); mask++) {
int low = __builtin_ctz(mask);
sum[mask] = sum[mask ^ (1 << low)] + a[low];
}
vector<int> g(1 << n, 0);
for (int mask = 1; mask < (1 << n); mask++) {
int i = __builtin_ctz(mask);
int rest = mask ^ (1 << i);
g[mask] = g[rest]; // phan tu i khong dung
for (int t = rest;; t = (t - 1) & rest) { // nhom gom i va cac phan tu thuoc t
int sub = t | (1 << i);
if (sum[sub] % 3 == 0) g[mask] = max(g[mask], g[mask ^ sub] + 1);
if (t == 0) break;
}
}
cout << g[(1 << n) - 1] << "\n";
}
}
// Sub 2: dem so du khi chia cho 3, O(n) moi test.
// Dung: moi phan tu chia het 3 la mot nhom; cap (du 1, du 2); bo ba cung so du.
void sub2() {
for (const vector<int> &a : tests) {
long long c0 = 0, c1 = 0, c2 = 0;
for (int x : a) {
int r = x % 3;
if (r == 0) c0++;
else if (r == 1) c1++;
else c2++;
}
cout << c0 + min(c1, c2) + llabs(c1 - c2) / 3 << "\n";
}
}
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
cin >> q;
tests.resize(q);
int maxN = 0;
for (auto &a : tests) {
int n;
cin >> n;
a.resize(n);
for (auto &x : a) cin >> x;
maxN = max(maxN, n);
}
if (maxN <= 8) sub1();
else sub2();
return 0;
}
Bình luận