AdditionalFile7001.zip

#7001. 「THUPC 2026 初赛」又一个 01 串问题

标签: 传统 | 时间限制: 1000 ms | 内存限制: 512 MiB |

题目描述

给定一个长为 $n$ 的 $01$ 串，你需要将其划分为两个子序列（可以为空），使其分别视为二进制数后的和最小。特别地，若子序列为空，则将其视为二进制数 $0$。以二进制形式输出这个最小的和。

输入格式

从标准输入读入数据。

包含多组数据。第一行一个正整数 $T$ $\left(1 \leq T \leq 10^{5}\right)$，表示数据组数。接下来 $2T$ 行，每两行表示一组数据，格式如下；

第一行一个正整数 $n$ $\left(1 \leq n \leq 5 \times 10^{5}\right)$。

第二行一个长为 $n$ 的 $01$ 串。

保证 $n$ 的总和不超过 $5 \times 10^{5}$。

输出格式

输出到标准输出。

$T$ 行，其中第 $i$ 行包含一个整数表示第 $i$ 组数据的答案。以二进制形式输出。

样例 1

输入

2
4
0101
3
000

输出

10
0

对于第一组数据，一种最优方案为，将字符串划分为第 $1,2$ 位的子序列和第 $3,4$ 位的子序列，答案为 01+01=10。

对于第二组数据，显然答案为 $0$。注意此时应该输出 $0$ 而不能输出空行。

题目使用协议

来自 THUPC2026（2026年清华大学学生程序设计竞赛暨高校邀请赛）初赛。

以下『本仓库』皆指 THUPC2026 初赛 官方仓库（https://gitlink.org.cn/thusaa/thupc2026pre）

1. 任何单位或个人都可以免费使用或转载本仓库的题目；
2. 任何单位或个人在使用本仓库题目时，应做到无偿、公开，严禁使用这些题目盈利或给这些题目添加特殊权限；
3. 如果条件允许，请在使用本仓库题目时同时提供数据、标程、题解等资源的获取方法；否则，请附上本仓库地址 或 算协公开仓库链接。