#P10409. [2021年联测]求和

    ID: 9527 传统题 1000ms 1024MiB 尝试: 18 已通过: 1 难度: 9 上传者: 标签>贪心数据结构CF2600线段树构造数学前缀和

[2021年联测]求和

求和

题目描述

给定长度为 nn 的整数序列 a1,…,ana_1,\ldots,a_n,构造整数序列 b1,…,bnb_1,\ldots,b_n,满足

  • 对每个 ii,有 bi≥aib_i\ge a_i;
  • 对任意不同的 i,ji,j,有 bi&bj=0b_i\mathbin{\&}b_j=0,即两个数的二进制中值为 11 的位没有交集。

求最小的 ∑i=1nbi\sum_{i=1}^n b_i。只输出这个最小和,不必输出构造方案。输入的 aia_i 及输出的和均使用二进制表示。

输入格式

第一行一个整数 nn。

接下来 nn 行,每行一个无前导零的 01 串,表示非负整数 aia_i;零表示为单字符 0。

输出格式

输出一个无前导零的 01 串,表示最小和的二进制形式。

样例 1 输入

2
10
10

样例 1 输出

110

样例 2 输入

2
10100
1001

样例 2 输出

11101

样例 3 输入

3
1
1
110

样例 3 输出

1011

样例 4 输入

2
1000100101
1110000000

样例 4 输出

11000100101

样例 5 输入

2
10100
1011000000

样例 5 输出

1011010100

数据范围

设 maxL\mathrm{maxL} 是各个 aia_i 二进制位数的最大值,∑L\sum L 是所有输入串的长度之和。全部数据满足 1≤n,maxL,∑L≤3×1051\le n,\mathrm{maxL},\sum L\le3\times10^5。

子任务 分值 附加限制
1 10 n=2n=2,maxL≤1000\mathrm{maxL}\le1000
2 n=2n=2
3 15 n,maxL≤100n,\mathrm{maxL}\le100
4 30 n,maxL≤3000n,\mathrm{maxL}\le3000
5 15 每个 aia_i 都是 22 的整次幂
6 20 无