美丽集合的最小和问题题解

题目分析

问题定义

• 「美丽的集合」：集合中所有数之和 = 所有数的 OR 和（无进位加法特性）
• 约束条件：
  1. 新数列 $b_i \geq a_i$（二进制数）
  2. 最小化 $\sum b_i$
• 输入输出：均为二进制形式

核心观察

1. 无进位加法特性：对于每个二进制位，若该位在集合中超过一个数为1，则会产生进位，破坏「美丽集合」性质
2. 关键结论：美丽集合中每个二进制位最多只能有一个数为1（否则求和时会进位，导致和大于OR和）
3. 优化目标：在满足 $b_i \geq a_i$ 的前提下，让每个二进制位尽量只被一个数占用，且总位数最少

算法设计

核心思路

1. 二进制位处理：按从高位到低位的顺序处理每个二进制位
2. 贪心选择：对于每个二进制位，优先分配给已占用较低位最少的数，确保总位数最小
3. 数据结构辅助：使用线段树维护每个数的占用状态，高效查询最优分配方案

详细步骤

1. 输入处理与预处理：

   • 将每个二进制数反转存储（便于按低位到高位处理）
   • 预处理每个数每个位置的前一个1的位置（prv数组）
   • 对每个二进制位的数进行排序，确保分配顺序最优

2. 线段树维护：

   • 线段树存储每个数的占用状态（v：当前占用位数，p：对应数的索引，c：计数）
   • 支持区间查询（找最优分配数）和单点更新（更新占用状态）

3. 递归计算结果：

   • 从最高位到最低位递归分配每个二进制位
   • 确保每个位只分配给一个数，且满足 $b_i \geq a_i$
   • 构建结果数组，最终反转得到二进制答案

算法标签

• 贪心算法
• 线段树
• 二进制处理
• 递归
• 排序

完整代码

#include <bits/stdc++.h>
using namespace std;
using pii = pair<int, int> ;

const int inf = 1e9;
const int kN = 3e5 + 5, kS = kN * 4;
int n, V;
vector<int> a[kN];
vector<int> prv[kN], rk[kN];
pii val[kN];

#define ls (o << 1)
#define rs (o << 1 | 1)

struct Info {
    int v, p, c;
    Info() {
        v = -inf, p = c = 0;
    }
    Info(int _v, int _p, int _c) {
        v = _v, p = _p, c = _c;
    }
};
Info operator + (Info x, Info y) {
    int vx = x.v + y.c, vy = y.v;
    return Info(max(vx, vy), (vy >= vx) ? y.p : x.p, x.c + y.c);
}

struct SGT {
    Info info[kS];
    void Up(int o) {
        info[o] = info[ls] + info[rs];
    }
    void Modify(int o, int l, int r, int x, Info v) {
        if (l == r)
            return void(info[o] = v);

        int mid = (l + r) >> 1;

        if (mid < x)
            Modify(rs, mid + 1, r, x, v);
        else
            Modify(ls, l, mid, x, v);

        Up(o);
    }
    Info Query(int o, int l, int r, int x, int y) {
        if ((l > y) || (r < x))
            return Info();

        if ((l >= x) && (r <= y))
            return info[o];

        int mid = (l + r) >> 1;
        return Query(ls, l, mid, x, y) + Query(rs, mid + 1, r, x, y);
    }
} sgt;

vector<int> Calc(int v, int hl) {
    Info get = sgt.Query(1, 1, V, 1, v);

    if (!get.c)
        return vector<int> {};

    int p = get.p, h = get.v, pc = h - val[p].second;

    if (h - 1 > hl)
        return vector<int> {-1};

    int seq, pos;

    tie(seq, pos) = val[p];

    int pv = prv[seq][pos], t;

    if (~pv) {
        t = rk[seq][pv];
        sgt.Modify(1, 1, V, t, Info(val[t].second + 1, t, 1));
    }

    vector<int> tmp = Calc(p - 1, h - pc - 1);

    if (tmp != vector<int> {-1}) {
        tmp.resize(h, 0);
        fill(tmp.begin() + h - pc, tmp.end(), 1);
        return tmp;
    }

    if (~pv)
        sgt.Modify(1, 1, V, t, Info());

    if (h > hl)
        return vector<int> {-1};

    tmp = Calc(p - 1, h - pc);

    assert(tmp != vector<int> {-1});
    tmp.resize(h + 1, 0);
    fill(tmp.begin() + h - pc + 1, tmp.end(), 1);
    return tmp;
}

int main() {
    ios::sync_with_stdio(0), cin.tie(0);
    cin >> n;

    for (int i = 1; i <= n; i++) {
        string s;
        cin >> s;
        int len = s.size();
        a[i].resize(len);

        for (int j = 0; j < len; j++)
            a[i][j] = s[len - j - 1] - '0';
    }

    sort(a + 1, a + n + 1,
    [&](auto & x, auto & y) {
        return x.size() > y.size();
    });

    for (int i = 1; i <= n; i++) {
        int len = a[i].size();
        prv[i] = rk[i] = vector<int> (len, 0);

        for (int j = 0, p = -1; j < len; j++) {
            prv[i][j] = p;

            if (a[i][j])
                p = j;
        }
    }

    for (int i = 0; i < a[1].size(); i++) {
        vector<int> vec;

        for (int j = 1; j <= n; j++) {
            if (a[j].size() <= i)
                break;

            if (a[j][i])
                vec.push_back(j);
        }

        sort(vec.begin(), vec.end(),
        [&](int x, int y) -> bool {
            int px = prv[x][i];
            int py = prv[y][i];

            if ((px == -1) || (py == -1)) return px < py;
            return rk[x][px] < rk[y][py];
        });

        for (int j : vec)
            val[rk[j][i] = ++V] = pii {j, i};
    }

    for (int i = 1; i <= n; i++) {
        int p = rk[i].back();
        sgt.Modify(1, 1, V, p, Info(val[p].second + 1, p, 1));
    }

    vector<int> res = Calc(V, a[1].size() + n);
    reverse(res.begin(), res.end());

    for (int i : res)
        cout << i;

    return 0;
}

代码解释

数据结构说明

1. Info结构体：存储线段树节点信息

   • v：当前占用的位数
   • p：对应的数的索引
   • c：计数（用于合并节点）

2. 线段树（SGT）：

   • Up：合并左右子节点信息
   • Modify：单点更新节点信息
   • Query：区间查询最优分配方案

3. 辅助数组：

   • prv[i][j]：第i个数第j位前一个1的位置
   • rk[i][j]：第i个数第j位的排序索引
   • val：存储排序后的位置信息

关键函数

1. Calc函数：递归计算结果

   • 查询当前最优分配的数
   • 更新线段树状态
   • 递归处理下一位，构建结果数组

2. main函数：

   • 输入处理与反转存储
   • 预处理前一个1的位置
   • 排序每个位的数
   • 初始化线段树
   • 调用Calc函数计算结果并输出

复杂度分析

• 时间复杂度：$O(L \log L)$，其中L为所有二进制数的总位数
  • 线段树操作：$O(\log V)$（V为总位数相关）
  • 递归处理：$O(V)$
• 空间复杂度：$O(kN)$，用于存储输入数据、辅助数组和线段树

该算法高效处理了大规模输入（总位数不超过$3 \times 10^5$），满足题目时间约束，是解决该问题的最优方案之一。