P17135 [KOI 2026 #1] 剪刀石头布

编号为 $1$ 到 $N$ 的 $N$ 个人排成一列。对于每个整数 $i$（$1 \le i \le N$），第 $i$ 个人站在从左向右数第 $i$ 个位置，并持有一张卡片 $A_i$。每张卡片均为剪刀（S）、石头（R）、布（P）中的一种。 如果两个不同的人之间没有其他人，则称这两个人相邻。你可以选择相邻的两个人，让他们进行对决。每次对决按照以下方式进行： - 如果两个人持有的卡片不同，则按照剪刀石头布的规则决定胜者。具体而言，石头（R）战胜剪刀（S），剪刀（S）战胜布（P），布（P）战胜石头（R）。 - 如果两个人持有的卡片相同，则可以由你任意指定其中一人为胜者。 败者将离场，胜者则保留自己原有的卡片，并留在原来的位置上。有人离场后，可能会有原本不相邻的两个人变得相邻，而他们之后也可以进行对决。 你需要恰好进行 $N-1$ 次对决，使得最后只剩下一名获胜者。请编写一个程序，对每个人分别判断是否存在一种安排对决的方式，使其能够成为最终获胜者。

第一行输入一个整数 $N$。 第二行输入一个长度为 $N$ 的字符串 $A$。$A$ 的第 $i$ 个字符 $A_i$ 表示第 $i$ 个人持有的卡片，为大写英文字母 S、R、P 中的一个（$1 \le i \le N$）。

第一行输出一个长度为 $N$ 的字符串。其中，第 $i$ 个字符应满足：如果第 $i$ 个人能够成为最终获胜者，则该字符为 $1$；否则，该字符为 $0$（$1 \le i \le N$）。

### 样例说明 1 如果先让第 $2$ 个人和第 $3$ 个人进行对决，由于两人持有的卡片相同，因此可以由你任意指定胜者。如果指定第 $2$ 个人获胜，那么剩下的第 $1$ 个人和第 $2$ 个人将进行对决。由于布（P）战胜石头（R），因此第 $2$ 个人可以成为最终获胜者。 也可以让第 $2$ 个人和第 $3$ 个人进行对决，并指定第 $3$ 个人获胜，之后再让第 $3$ 个人与第 $1$ 个人进行对决。这样，第 $3$ 个人可以成为最终获胜者。 由于石头（R）无法战胜布（P），因此第 $1$ 个人绝不可能成为最终获胜者。 ### 样例说明 2 如果先让第 $2$ 个人和第 $3$ 个人进行对决，由于剪刀（S）战胜布（P），因此第 $3$ 个人获胜。剩下的第 $1$ 个人和第 $3$ 个人进行对决时，由于石头（R）战胜剪刀（S），因此第 $1$ 个人可以成为最终获胜者。 如果先让第 $1$ 个人和第 $2$ 个人进行对决，由于布（P）战胜石头（R），因此第 $2$ 个人获胜。剩下的第 $2$ 个人和第 $3$ 个人进行对决时，由于剪刀（S）战胜布（P），因此第 $3$ 个人可以成为最终获胜者。 第 $2$ 个人绝不可能成为最终获胜者。 ### 限制条件 $1 \le N \le 200\,000$。 $A$ 是一个长度为 $N$ 的字符串，且仅由大写英文字母 S、R、P 组成。 ### 子任务 1. （$13$ 分）$N \le 3$。 2. （$16$ 分）字符串 $A$ 中至多包含两种不同的字符。 3. （$47$ 分）$N \le 100$。 4. （$31$ 分）$N \le 5\,000$。 5. （$43$ 分）无附加限制。 翻译由 ChatGPT-5.6 完成