UOJ Logo Zijian Online Judge

ZOJ

#48. 求和

统计

给你一个长为 $n$ 的数列 $a_1,a_2,\dots,a_n$,请你构造一个整数序列 $b_1, b_2,\dots, b_n$,满足

  • 对于所有的 $i$,有 $b_i \ge a_i$。
  • 在二进制加法中,将 $b$ 数列求和时不发生进位。
  • 满足以上两条条件的数列中,你需要最小化 $\sum_{i=1}^n b_i$。

本题采用多组数据。

输入格式

第一行一个数 $T$,表示数据组数。

每组数据第一行一个正整数 $n$,表示数列长度。

接下来 $n$ 行,每行一个仅包含 $\texttt{01}$ 的串,表示数列中的数的二进制表示,保证以 $\texttt{1}$ 开头。

输出格式

对于每组数据,一行一个二进制数,表示 $\sum_{i=1}^n b_i$ 的二进制表示。

样例一

input

4
2
10
10
2
10100
1001
3
1
1
110
2
1101
101011

output

110
11101
1011
111011

explanation

对于第一组数据,$b=((100)_2, (10)_2)$。

对于第二组数据,$b=a$。

对于第三组数据,$b=((10)_2,(1)_2,(1000)_2)$。

对于第四组数据,$b=((10000)_2,(101011)_2)$。

样例二

见下发文件。

限制与约定

记二进制数最大串长为 $\max L$,单个测试点中单个数据总串长为 $\sum L$,所有数据总串长为 $\sum^2 L$。

对于 $100\%$ 的数据,保证 $T\le 10, 2\le n \le 10^5, 1\le \max L\le \sum L \le 10^5, 1\le \sum^2 L \le 10^6$。

测试点编号$n$$\max L$特殊限制
$1$$=2$$\le 10$
$2$$\le 20$
$3$$\le 50$
$4$$\le 300$
$5$$\le 10^3$
$6$$\le 10^5$
$7$$\le 8$$\le 8$
$8$$\le 50$
$9$$\le 100$
$10$
$11$$\le 10^3$$\sum L \le 10^3$
$12$
$13$
$14$
$15$
$16$$\le 10^5$$\sum^2 L \le 3\times 10^5$,每个二进制数都是 $2$ 的整次幂
$17$每个二进制数都是 $2$ 的整次幂
$18$
$19$$\sum^2 L \le 3\times 10^5$
$20$
$21$
$22$
$23$
$24$
$25$

时间限制:$1\texttt{s}$

空间限制:$512\texttt{MB}$

下载

样例数据下载