题解

思路推导

固定某个候选冠军 $x$，把比 $x$ 小的实力视为“低”，比 $x$ 大的实力视为“高”。候选队伍沿晋级路径遇到强者胜出的轮次时，对侧子树必须产生一个低实力胜者；遇到弱者胜出的轮次时，对侧子树必须产生一个高实力胜者。

设前若干轮组成的子树要产生低实力胜者时至少需要的低实力叶子数为 $L$，产生高实力胜者时至少需要的高实力叶子数为 $H$。初始均为 $1$。强者胜出的一层会把 $L$ 翻倍而保持 $H$，弱者胜出的一层会把 $H$ 翻倍而保持 $L$。

因此，若字符串中有 $c_1$ 个 1 和 $c_0$ 个 0，候选冠军总共至少需要 $2^{c_1}-1$ 个更弱的实力和 $2^{c_0}-1$ 个更强的实力。于是所有可行的 $x$ 构成连续区间

做法

统计字符串中 0 与 1 的个数，计算区间左右端点，再从左到右输出区间内的每个整数。

正确性证明

上述子树最少叶子数递推分别给出了产生低胜者和高胜者的必要条件；每次只在需要的一个子树中放置相应类型，其余位置任意填充，又说明这些下界可以同时达到。故 $x$ 可夺冠当且仅当它拥有不少于 $2^{c_1}-1$ 个更小实力且不少于 $2^{c_0}-1$ 个更大实力，即满足给出的闭区间。算法恰好输出该区间中的全部整数，因此答案既无遗漏也无多余。

复杂度分析

除输出外的时间复杂度为 $O(n)$，额外空间复杂度为 $O(1)$；输出复杂度与答案个数成正比。