Hướng dẫn giải của Nhóm bạn vui vẻ
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 (tập con khác rỗng) có tổng độ vui vẻ bằng K. Với ~N \le 25~ có thể dùng chia đôi để đếm nhanh.
Sub 1: Vét cạn - ~O(2^n \cdot n)~, dùng khi ~n \le 20~
Thử mọi tập con khác rỗng và đếm tập có tổng bằng K. Nếu chỉ nộp sub này: đúng 23/25 test (2 test quá giờ nằm ngoài miền của nó).
Sub 2: Chia đôi (meet in the middle) - ~O(2^{n/2} \cdot n)~
Liệt kê tổng các tập con của nửa đầu và nửa sau, sắp nửa sau. Với mỗi tổng x bên trái, đếm số lần ~K - x~ xuất hiện bên phải bằng equal_range. Vì tập rỗng được tính một lần ở mỗi nửa, nếu K = 0 thì trừ đi 1. Đúng 25/25 test.
Chương trình hoàn chỉnh
main đọc N, K và dãy. Nếu ~n \le 20~ gọi sub1, còn lại gọi sub2.
#include <bits/stdc++.h>
using namespace std;
int n;
long long K;
vector<long long> a;
// Sub 1: vet can 2^n tap con, dem tap con khac rong co tong bang K. Dung khi n <= 20.
void sub1() {
long long cnt = 0;
for (int mask = 1; mask < (1 << n); mask++) {
long long s = 0;
for (int i = 0; i < n; i++)
if ((mask >> i) & 1) s += a[i];
if (s == K) cnt++;
}
cout << cnt << "\n";
}
// Sub 2: chia doi (meet in the middle). Liet ke moi tong cua nua dau va nua sau (2^(n/2) gia tri),
// sap xep nua sau roi voi moi tong x ben trai dem so tong K - x ben phai. O(2^(n/2) * log).
// Dung cho n <= 25.
void sub2() {
int h = n / 2;
auto gen = [&](int from, int to) {
vector<long long> sums = {0}; // tong cua tap con rong
for (int i = from; i < to; i++) {
int sz = sums.size();
for (int t = 0; t < sz; t++) sums.push_back(sums[t] + a[i]);
}
return sums;
};
vector<long long> s1 = gen(0, h), s2 = gen(h, n);
sort(s2.begin(), s2.end());
long long cnt = 0;
for (long long x : s1) {
auto range = equal_range(s2.begin(), s2.end(), K - x);
cnt += range.second - range.first;
}
if (K == 0) cnt--; // bo tap con rong (duoc tinh 1 lan trong ca hai nua)
cout << cnt << "\n";
}
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
cin >> n >> K;
a.resize(n);
for (auto& x : a) cin >> x;
if (n <= 20) sub1();
else sub2();
return 0;
}
Bình luận