1 条题解
-
0
【本题解由站长编写】
用最低位表示第一个输入元素,最高位表示第 n 个元素。按掩码从 1 到 2^n−1 枚举,天然满足规定的方案顺序。用 sum[mask] = sum[mask 去掉最低位] + 该位元素在 O(1) 时间计算子集和,输出时按位从低到高枚举所选数字。采用缓冲输出,避免大量解时逐个同步输出变慢。时间复杂度为 O(2^n + 输出长度),空间复杂度为 O(2^n)。
代码(C++17)
#include <bits/stdc++.h> using namespace std; struct Writer { static constexpr size_t capacity = 1 << 20; char buffer[capacity]; size_t used = 0; void flush() { fwrite(buffer, 1, used, stdout); used = 0; } void put(const string &s) { if (used + s.size() > capacity) flush(); memcpy(buffer + used, s.data(), s.size()); used += s.size(); } ~Writer() { flush(); } }; int main() { ios::sync_with_stdio(false); cin.tie(nullptr); int n; cin >> n; vector<long long> value(n); vector<string> token(n); for (int i = 0; i < n; ++i) { cin >> value[i]; token[i] = to_string(value[i]); } long long target; cin >> target; vector<long long> sum(1 << n, 0); Writer out; int count = 0; for (int mask = 1; mask < (1 << n); ++mask) { int bit = mask & -mask; sum[mask] = sum[mask ^ bit] + value[__builtin_ctz((unsigned)bit)]; if (sum[mask] != target) continue; ++count; int rest = mask; while (rest) { bit = rest & -rest; out.put(token[__builtin_ctz((unsigned)bit)]); rest ^= bit; out.put(rest ? " " : "\n"); } } out.put(to_string(count)); out.put("\n"); }
- 1
信息
- ID
- 4261
- 时间
- 1000ms
- 内存
- 256MiB
- 难度
- 5
- 标签
- 递交数
- 1
- 已通过
- 0
- 上传者