题解【UVA1620 懒惰的苏珊 Lazy Susan】

$\texttt{upd: }$ 改了一个错（有 -> 无）。 $\texttt{upd2: }$ 稍微修改了下描述。 - - - ## 结论： 当 $n\geq 6$ 时，若 $n$ 是奇数且输入序列的逆序对数是奇数，则无解，否则有解。 当 $n=4$ 或 $n=5$ 时，答案个数及其有限，只有这个环是 $1$ 到 $n$ 的排列（顺时针或逆时针均可，如 $2,3,4,1$、$2,1,4,3$）时有解，否则无解。但因为题目中 $n\geq 8$ 所以这种情况你无需考虑。 ## 证明： $n<6$ 的特殊情况暴搜即可证明，下面不妨假设 $n\geq 6$。 首先我们注意到，我们可以对序列 $1,2,3,4,5,6$，**不**交换序列首尾交接处的元素把 $1,2,3,4,5,6$ 变成 $6,\color{red}2,3,\color{black}5,4,1$ 或 $6,5,\color{red}3,4,\color{black}2,1$ 或 $6,3,2,\color{red}4,5,\color{black}1$（**这很重要！**）。证明不必多说，暴搜即可。 我们可以证明，当 $n$ 为奇数时，题中操作不会改变序列逆序对数的奇偶性。证明如下： > 题目中的操作等价于只对序列进行两种操作： > - 将前四个元素翻转； > - 将第一个元素移到末尾。 > > 对于第一种操作，显然前 $4$ 个元素之一与后面的元素形成的逆序对数不变，后面元素互相形成的逆序对数也不变，只需考虑前 $4$ 个元素互相形成的逆序对数。设原来此数为 $x$，则顺序对数为 $6-x$，翻转后逆序对数即为 $6-x$，逆序对数变化量为 $|x-(6-x)|=2|x-3|$ 为偶数，所以操作 $1$ 不会改变序列逆序对数的奇偶性。 > > 对于第二种操作，假设原来元素 $1$ 和其他元素形成的逆序对数为 $y$，则之后该元素和其他元素形成的逆序对数变为 $n-1-y$，而 $n$ 是奇数，所以操作 $2$ 也不会改变序列逆序对数的奇偶性。 由此可知，若 $n$ 是奇数且输入序列的逆序对数是奇数，则无解。 下面我们证明**其他情况必有解**：$\color{white}\texttt{补充楼下二位的证明}$ 若 $n\leq 7$，暴搜（~~暴搜是万能的~~）即可证明。下面不妨设 $n \geq 8$。 我们可以先把元素 $1$ 归位，只要元素 $1$ 在位置 $4$，就可以翻转过来。同理只要元素 $1$ 出现在位置 $1,4,3,5,2,6\dots$ 任何位置，都可以把元素 $1$ 归位。可以同理归位元素 $2$。然后： 若忽略元素 $1$、$2$ 后有解，则由前面的结论知不忽略是也有解，只要把**翻转序列首尾交接处的操作**换掉即可。 即把长度为 $n$ 序列的问题转化为了长度为 $n-2$ 序列的问题，又因为当 $n$ 为奇数时操作不会改变逆序对数奇偶性，可以归纳到 $n=6,7$ 时结论成立（已证）。 综上可得本题结论。 ## 代码： 当然可以用归并排序或树状数组求逆序对数，但本题数据规模小所以不需要。 ```cpp #include <bits/stdc++.h> using namespace std; int main() { int T, n, a[500]; cin >> T; while(T--) { cin >> n; for(int i = 0; i < n; ++i) cin >> a[i]; bool x = true; // 求逆序对数的奇偶性 if(n & 1) for(int i = 0; i < n; ++i) for(int j = i+1; j < n; ++j) if(a[i] > a[j]) x = !x; puts(x ? "possible" : "impossible"); } return 0; } ```