CF1658C 题解

E1_de5truct0r · 2022-08-12 22:49:42 · 题解

思路

首先，由于 p 在这里轮换了 n 次，所以一定有且只有一次 n 开头的情况，这个时候 c_i=1。如果没有 c_i=1 或者有好几个 c_i=1，那么显然无解。

然后，我们从这个 1 的位置开始找。我们考虑怎么排除不合法的情况。

• 证明：每次移动相当于把队尾移到队头。 1. 如果队尾是最大值：则队尾是 $n$，移到队头之后 $c_i=1$，不可能会比 $c_{i-1}$ 大超过 1。 2. 如果队尾不是最大值：则去掉之后对于后面的 $c_i$ 个数没有影响，放到队头最多增加一个 $c_i$。 综上，证毕。

那么，其他的情况是否都有解呢？

答案是肯定的。因为无论如何，每次按照前面的 c 构造，要么放大的要么放小的，总之能够造出来一个解。

代码实现

我们只需要完成两个操作：

• 判断 c 数组中是否恰好只有一个 1，并记录 1 的位置。

  如果没有找到 1 或者有很多个 1，那么输出 NO。

• （假设找到了）那么从这个唯一的环上找一整圈。

  如果有，输出 NO；否则输出 YES。

实现比较简单，就不放代码了。