题目详解

问题重述

我们需要构造一个长度为 $n$ 的比特串（仅含 $0$ 和 $1$），要求：

1. 字符串中恰好包含 $k$ 个 $1$。
2. 字符串中作为子序列出现的 $101$ 的数量等于 $010$ 的数量。

---

关键观察

直接计算任意字符串中 $101$ 和 $010$ 子序列的数量是很困难的。
但如果我们能构造出使得这两类子序列数量都为 $0$ 的字符串，问题就变得非常简单。

---

什么时候 $101$ 和 $010$ 子序列数量都为 $0$？

一个充分条件是：字符串中所有的 $1$ 都出现在所有的 $0$ 之前。
也就是说，字符串形如：

$$\underbrace{111\ldots 1}_{k\text{个}} \underbrace{000\ldots 0}_{n-k\text{个}} $$

• 要形成 $101$ 子序列，需要 $1$ 后面出现 $0$，然后后面再出现 $1$。
  但如果所有 $1$ 都在所有 $0$ 的前面，那么一旦出现 $0$，后面就再也不会出现 $1$，因此不可能有 $101$。
• 同理，要形成 $010$ 子序列，需要 $0$ 后面出现 $1$，然后后面再出现 $0$。
  但在这种结构中，$1$ 后面不会再有 $0$，所以 $010$ 也不可能出现。

因此，这种字符串的 $101$ 和 $010$ 子序列数量均为 $0$，显然是“完美”的。

---

直接构造

按照上面的想法，我们可以直接构造：

• 输出 $k$ 个 $1$，再输出 $n-k$ 个 $0$。

但注意题目要求恰好 $k$ 个 $1$。这样构造确实满足要求。

然而，看看题目给的示例输出：

• 当 $n=4, k=2$，输出是 $1010$，而不是 $1100$。

这说明题目允许其他构造，但我们的构造 $1100$ 也是正确的。
实际上，$1100$ 中 $101$ 和 $010$ 子序列数量确实都是 $0$。
那么为什么示例没有用这种最简单的构造？可能是因为题目希望展示不同构造方式，但不代表我们的构造错误。

---

更严谨的构造（与标程一致）

标程给出了一种略微不同的构造，特别处理了 $k=0$ 和 $k=n$ 的情况，以及一般情况：

• 若 $k = 0$：全为 $0$。
• 若 $k = n$：全为 $1$。
• 否则，构造为：
  $k-1$ 个 $1$，接着 $n-k-1$ 个 $0$，最后 $1$ 个 $1$。

这种构造也能保证 $101$ 和 $010$ 子序列数量为 $0$，因为唯一的两个 $1$ 在两端，中间全是 $0$，不会出现 $1$ 在 $0$ 之后又出现 $1$ 的模式。

---

为什么示例输出不同？

题目说“如果有多个解，输出任意一个”。
示例输出 $1010$ 也是一种解，它的 $101$ 和 $010$ 子序列数量都是 $1$，不是 $0$，但依然相等。

我们的构造 $1100$ 也是正确的，而且更简单。

---

最终结论

最简单且正确的构造是：

$$\text{ans} = \underbrace{111\ldots 1}_{k\text{个}} \underbrace{000\ldots 0}_{n-k\text{个}} $$

这保证了 $101$ 和 $010$ 子序列的数量均为 $0$，因此完美满足要求。

如果 $k=0$ 或 $k=n$，这个构造自然退化到全 $0$ 或全 $1$。