A1455 | 构造数字
来源官方 / 2023
时间限制1s
内存限制128MB
通过 / 提交0/0
题目描述
$AC$ 狗发现了两个长度为 $n$ 的二进制整数 $a$ 和 $b$（这两个整数每一位都只能由数字 $0$ 和 $1$ 组成），它们可以有前导零。
为了不忘记这两个整数，它想用以下方式构造整数 $d$：
* 将 $a$ 和 $b$ 逐位相加，但不发生进位得到 $c$。例如：
* 将 $c$ 中连续的相等数字替换成一个数字，得到 $d$。
例如：
不幸的是，$AC$ 狗在计算出 $d$ 之间就忘记了 $a$。现在为了让 $AC$ 狗高兴起来，你需要找到一个长度为 $n$ 的二进制数 $a$，使得 $a$ 和 $b$ 构造出的 $d$ 最大。
（在比较大小时：$102>21$, $012<101$, $021=21$）
为了不忘记这两个整数，它想用以下方式构造整数 $d$：
* 将 $a$ 和 $b$ 逐位相加，但不发生进位得到 $c$。例如：
0110 加 1101 的结果为 1211；011000 加 011000 的结果为 022000。* 将 $c$ 中连续的相等数字替换成一个数字，得到 $d$。
例如：
1211 变为 121，022000 变为 020。不幸的是，$AC$ 狗在计算出 $d$ 之间就忘记了 $a$。现在为了让 $AC$ 狗高兴起来，你需要找到一个长度为 $n$ 的二进制数 $a$，使得 $a$ 和 $b$ 构造出的 $d$ 最大。
（在比较大小时：$102>21$, $012<101$, $021=21$）
输入格式
第一行包含一个整数 $T$ ($1 \le T \le 100$) — 表示测试用例的数量。
每个测试用例的第一行包含整数 $n$ ($1 \le n \le 10^5$) — 表示 $b$ 的长度。
每个测试用例的第二行包含$b$。
每个测试用例的第一行包含整数 $n$ ($1 \le n \le 10^5$) — 表示 $b$ 的长度。
每个测试用例的第二行包含$b$。
输出格式
对于每个测试用例输出 $a$，有前导 $0$ 的话也需要输出。
输入输出样例
输入 #1
5 1 0 3 011 3 110 6 111000 6 001011
输出 #1
1 110 100 101101 101110
在第一个测试用例中，$b = 0$ ，$a = 1$ 时 $d = 1$ 是最大的。
在第二个测试用例中，$b=011$：
如果 $a = 000$，则 $c = 011$ -> $d = 01$；
如果 $a = 111$，则 $c = 122$ -> $d = 12$；
如果 $a = 010$，则 $d = 021$；
如果 $a = 110$，则 $d = 121$；
可以证明 $a = 110$ 时，$d$ 是最大的。
在第三个测试用例中，$b = 110$ ，$a = 100$ 时 $d = 210$ 是最大的。
在第四个测试用例中，$b = 111000$ ，$a = 101101$ 时 $d = 212101$ 是最大的。
在第五个测试用例中，$b = 001011$ ，$a = 101110$ 时 $d = 102121$ 是最大的。
在第二个测试用例中，$b=011$：
如果 $a = 000$，则 $c = 011$ -> $d = 01$；
如果 $a = 111$，则 $c = 122$ -> $d = 12$；
如果 $a = 010$，则 $d = 021$；
如果 $a = 110$，则 $d = 121$；
可以证明 $a = 110$ 时，$d$ 是最大的。
在第三个测试用例中，$b = 110$ ，$a = 100$ 时 $d = 210$ 是最大的。
在第四个测试用例中，$b = 111000$ ，$a = 101101$ 时 $d = 212101$ 是最大的。
在第五个测试用例中，$b = 001011$ ，$a = 101110$ 时 $d = 102121$ 是最大的。
C++ 编辑器
输入
输出
可保存默认模板；新题优先使用已保存模板。
当前快捷键仅展示，暂不支持修改。
- 撤销
Ctrl / ⌘ + Z - 重做
Ctrl / ⌘ + Y - 查找
Ctrl / ⌘ + F - 全选
Ctrl / ⌘ + A - 复制
Ctrl / ⌘ + C - 剪切
Ctrl / ⌘ + X - 粘贴
Ctrl / ⌘ + V - 自动排版
工具栏排版按钮 - 草稿保存
编辑时自动保存到本机
历史
提交记录
状态说明时间源码
AI
作答助手
你好，我是作答助手。可以问思路、复杂度、样例含义或代码报错原因；不会直接给出完整 AC 代码。
确定要清空代码吗？