CF2030B.Minimise Oneness

对于任意二进制字符串 $t$，定义 $f(t)$ 为 $t$ 的仅包含 $\mathtt{0}$ 的非空子序列的数量，定义 $g(t)$ 为 $t$ 的包含至少一个 $\mathtt{1}$ 的非空子序列的数量。

注意，对于 $f(t)$ 和 $g(t)$，每个子序列出现多少次就计数多少次。例如，$f(\mathtt{000})=7$，$g(\mathtt{100})=4$。

我们定义二进制字符串 $t$ 的“oneness”为 $|f(t)-g(t)|$，其中对于任意整数 $z$，$|z|$ 表示 $z$ 的绝对值。

给定一个正整数 $n$，请你构造一个长度为 $n$ 的二进制字符串 $s$，使得其 oneness 尽可能小。如果有多种方案，可以输出任意一种。

注：
$^{\text{∗}}$ 二进制字符串是仅由字符 $\mathtt{0}$ 和 $\mathtt{1}$ 组成的字符串。
$^{\text{†}}$ 序列 $a$ 是序列 $b$ 的子序列，如果 $a$ 可以通过删除 $b$ 的若干（可能为零或全部）元素得到。例如，$\mathtt{1011101}$ 的子序列有 $\mathtt{0}$、$\mathtt{1}$、$\mathtt{11111}$、$\mathtt{0111}$，但没有 $\mathtt{000}$ 或 $\mathtt{11100}$。

第一行包含一个整数 $t$（$1 \leq t \leq 10^4$），表示测试用例的数量。

每个测试用例仅一行，包含一个整数 $n$（$1 \leq n \leq 2\cdot10^5$），表示 $s$ 的长度。

保证所有测试用例中 $n$ 的总和不超过 $2\cdot10^5$。

对于每个测试用例，输出一行长度为 $n$ 的二进制字符串 $s$。如果有多种答案，输出任意一种即可。

在第一个测试用例中，示例输出 $f(t)=1$，因为只有一个仅包含 $\mathtt{0}$ 的子序列（$\mathtt{0}$），$g(t)=0$，因为没有包含至少一个 $1$ 的子序列。oneness 为 $|1-0|=1$。输出 $\mathtt{1}$ 也是正确的，因为其 oneness 为 $|0-1|=1$。

在第二个测试用例的示例输出中，$f(t)=1$，因为只有一个仅包含 $\mathtt{0}$ 的非空子序列，$g(t)=2$，因为有两个包含至少一个 $1$ 的非空子序列（$\mathtt{01}$ 和 $\mathtt{1}$）。oneness 为 $|1-2|=1$。可以证明，对于所有长度为 $2$ 的二进制字符串，oneness 的最小值为 $1$。

由 ChatGPT 4.1 翻译