Skip to content

1269: OR 集合

题目

题目描述

有时候我们可以使用二进制的 OR 运算来代替加法运算。对于某个集合的整数来说,如果不存在两个整数的某个二进制位同时为 1,那么这个集合元素的加法和就等于他们二进制 OR 运算之后的值。我们把拥有这种性质的集合认为是优美的。

现在,给你 $n$ 个整数 $a_1, a_2, \dots, a_n$, 你需要找到一个集合 $b_1, b_2, \dots, b_n$,满足:

  • $b_1, b_2, \dots b_n$ 是优美的集合。
  • $\forall i \in [1, n]: b_i \geq a_i$
  • $\sum_{i=1}^n b_i$ 最小

输入格式

第一行输入一个整数 $n$,代表了集合 a 和集合 b 的大小

接下来的 $n$ 行,每行一个整数,代表了 $a_i$。这些数是由二进制形式给出的。

输出格式

以二进制的形式输出一个整数,不要有前导零。代表了最小的 $\sum_{i=1}^n b_i$。

样例输入

样例输入 1

text 2 10 10

样例输入 2

text 2 10100 1001

样例输入 3

text 3 1 1 110

样例输出

样例输出 1

text 110

样例输出 2

text 11101

样例输出 3

text 1011

数据范围

时间限制:2000 ms 空间限制:512 mb

  • 所有 $a_i$ 的位数之和不超过 $300000$

| 测试点 | 分值 | $n\leq$ | 二进制最大位数 | 额外限制 | | ------ | ---- | ------- | -------------- | ----------------- | | 1 | 4 | 2 | 10 | | | 2 | 2 | 2 | 20 | | | 3 | 2 | 2 | 100 | | | 4 | 2 | 2 | 1000 | | | 5 | 2 | 2 | 300000 | | | 6 | 4 | 100 | 100 | $a_i$​ 是 2 的次幂 | | 7 | 4 | 1000 | 1000 | $a_i$ 是 2 的次幂 | | 8 | 4 | 300000 | 300000 | $a_i$ 是 2 的次幂 | | 9 | 4 | 5 | 5 | | | 10 | 4 | 5 | 1000 | | | 11 | 4 | 1000 | 5 | | | 12 | 4 | 10 | 10 | | | 13 | 4 | 50 | 50 | | | 14 | 7 | 100 | 100 | | | 15 | 7 | 300 | 300 | | | 16 | 8 | 1000 | 1000 | | | 17 | 8 | 3000 | 3000 | | | 18 | 6 | 10000 | 10000 | | | 19 | 7 | 30000 | 30000 | | | 20 | 7 | 100000 | 100000 | | | 21 | 6 | 300000 | 300000 | |

Oops! 本题目还没有解答!

助教老师们编题的速度,已经超过了解题的速度!

OJ翻了一新,但本解答集还大多用的是2017-2019级,甚至更早的同学们贡献的答案。

如果你已经AC了,可以的话,请您参考添加页面,与大家一起分享你的题解!