翻译
查看原帖
翻译
421781
liuzimingc楼主2021/2/26 09:37
## 题目描述
在游戏开始之前,几张牌从左到右排成一行放在一张桌子上。每张牌包含`0`或`1`。玩家轮流移动(Masha 先移动)。在每一次移动中,玩家会移除一张牌。例如,在某人移动之前,表上的卡片形成了一个序列`01010101`,那么在第 $4$ 张卡片被移动之后(卡片从 $1$ 开始编号),序列将变成`0100101`。

当只剩 $2$ 张牌时,游戏结束。这些卡上的数字决定了二进制中的数字。Masha 的目标是最小化这个数字;Petya 的目标是最大化这个数字。

现在,有些卡片上的数字变得模糊了,记作`?`。假设 Petya 和 Masha 都玩得很好,请你找出游戏结束时剩下的 $2$ 张牌所有可能的情况。
## 输入格式
只有 $1$ 行,包含一系列字符,每个字符可以是`0`,`1`或`?`。字符顺序决定了牌摆放的初始顺序。$2 \leq \texttt{字符长度} \leq 10^5$。
## 输出格式
输出所有可能的结果,每行 $1$ 个。按字典序升序排列。
## 说明/提示
样例组 #1 解释:有 $16$ 种可能的排列。如果一开始牌面为`0000`,结果是`00`;如果一开始牌面为`1111`,结果是`11`;如果一开始牌面为`0011`,结果是`01`;如果一开始牌面为`1100`,结果是`10`。总共只有 $4$ 种不同的结果。

样例组 #3 解释:只有 $2$ 种可能的数字排列:`111`和`101`。如果一开始牌面为`111`,结果是`11`;如果一开始牌面为`101`,结果是`01`。Masha 可以在第一次操作时取出最左边的牌,然后游戏结束。
2021/2/26 09:37
加载中...