给你一个 01 串构成的环 我们可以看作一个长度为 �n 的环 首尾相接 我们要通过此串构造一个数列 �a 如果01 串的第 �i 个符号位 0 则表示 ��≠��+1a i =a i+1 如果 01 串的第 �i 个符号为 1 则表示 ��=��+1a i =a i+1 如果 �=�i=n 则表示 �1��a 1 a n 之间的关系

题意理解

题目给出一个由 $0$ 和 $1$ 组成的环，长度为 $n$，要求构造一个长度为 $n$ 的数列 $a$，其中 $a_i$ 和 $a_{i+1}$ 的大小关系由环上的 $i$ 号和 $i+1$ 号位置上的数字决定，若为 $0$，则 $a_i \neq a_{i+1}$，若为 $1$，则 $a_i = a_{i+1}$，同时 $a_1$ 和 $a_n$ 的大小关系也由环上对应位置上的数字决定。现在要求你构造出满足要求的 $a$ 数列。

题目思路

我们可以从 $a_1$ 开始构造，每次根据环上的数字来决定 $a_{i+1}$ 的大小关系，直到构造出整个 $a$ 数列。但是，这个过程中会遇到一个问题，就是可能有多个数字可以作为 $a_{i+1}$ 的取值，这样就无法构造出唯一的 $a$ 数列。比如，当 $a_i < a_{i+1}$ 时，环上 $i$ 号位置上的数字为 $0$，$i+1$ 号位置上的数字为 $1$，此时 $a_{i+1}$ 可以取 $a_i$ 和 $a_i + 1$ 两个值中的任意一个，这样就无法得到唯一的 $a$ 数列。因此，我们需要对这种情况进行特判。

具体来说，我们可以从 $a_1$ 开始构造，首先将 $a_2$ 设为 $a_1$ 或 $a_1+1$，然后根据环上的数字来决定 $a_3$ 的取值，如果此时 $a_2$ 可以取多个值，则我们需要在 $a_2=a_1$ 和 $a_2=a_1+1$ 两种情况下分别进行处理，具体来说，我们分别从 $a_1$ 和 $a_1+1$ 开始构造，然后比较两个构造出来的 $a$ 数列，取其中字典序最小的一个作为最终的 $a$ 数列。

最后，我们需要检查一下构造出的 $a$ 数列是否满足条件，即 $a_n$ 和 $a_1$ 的大小关系是否与环上对应位置上的数字相同，如果不同，则说明无法构造出满足条件的 $a$ 数列。

时间复杂度

对于每个位置，我们最多需要比较两个 $a$ 数列，因此总时间复杂度为 $O(n^2)$。

参考代码

下面给出参考代码