[找规律][逆序数][思维] UVa1620 Lazy Susan

自己看看了半天都找不到规律,倒是感觉和逆序数应该有关系,但是直接按照偶序列有解奇序列无解来算wa,因为按照我原来的理解是,偶序列4个反转一定还是偶序列,奇序列4个反转也一定是奇序列。搜了题解之后发现漏掉了一个条件,那就是这个是个环,所以他从任意一个地方开始都可以,这就相当于在原来的4个翻转的变换的基础上多了一种变换:把后面的一段整个的移动到前面的一段。这个操作是如果按照一次简单变换来衡量的话,相当于做了i*j次变换,其中i是分界点前一段的个数,j是后一段的。当n为偶数的时候可以找到一个分界点分为两个奇数段,则相乘之后仍然是奇数,等于说这时候是可以从奇序列变成偶序列的;而当n为奇数的时候,i和j必定一奇一偶,这时候相乘必定为偶数,无法变换序列的奇偶性。所以,只有当序列为奇序列且n为奇数的时候才无解,其他情况均有解,因为均可以变换为偶序列。

继续阅读“[找规律][逆序数][思维] UVa1620 Lazy Susan”