1839C

分析 首先对于最后一个元素为1的数组，显然不存在合法构造方式。为什么？因为每个1都需要至少一个数插入在它后面对它完成翻转，如果最后一个数为1，这时没有数在它后面翻转它，所以这时无法构造。 然后我们很naive地想让每个1都只被翻转一次，那么很好想到，对于一个形如\(11\dots100\dots0\ ......

Insert Zero and Invert Prefix 题面翻译 你有一个长度为 \(n\) 的 01 序列 \(a\)，以及一个初始为空的序列 \(b\)。你接下来需要执行 \(n\) 次操作，每次操作将会使序列 \(b\) 的长度增加 \(1\)。 在第 \(i\) 次操作，你需要选择一个在 ......

首先考虑无解的情况，很明显 $a_n$ 必须为 $0$，否则没有解，因为如果最后一位为 $1$ 那么必须有 $n$ 这个数存在于 $b$ 序列中，而这种情况时不符合题意的。 然后考虑如何求解，先考虑一种比较特殊的情况，就是若干个 $1$ 后面接着一个 $0$，这里假设 $1$ 的数量有 $k$ 个， ......