跳至正文

1 条题解

  • 0
    @ 2026-10-7 20:30:08

    【本题解由站长编写】

    用最低位表示第一个输入元素,最高位表示第 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
    上传者