- 构造类题目.
仔细看样例解释能发现点东西?
- 结论:答案只可能是 \(Impossible,1,2\) .
- \(Impossible:\) 有 \(n\) 个或 \(n-1\) 个相同的字母,显然无法拼出另一个回文串.
(样例3)
- \(1:\) \(Cut\) \(1\) 次,相当于是做了原串的一个循环排列. \(O(n^2)\) 对所有循环排列验证是否符合要求即可.
(样例4)
- \(2:\) 在原串中找出一段 \(len<n/2\) 的前缀以及与它等长的后缀,将它们 \(Cut\) 出后交换.若所有的前缀与对应交换后都不符合要求,则一定是 \(Impossible\) 对应的两种局面,否则至少有一个前缀 \(pre\) 满足 \(pre!=inverse(pre)\),即它对应的 \(suf\) ,交换两者即得一个合法的解.
(样例1)
- 只需判断是否为前 \(2\) 种情况,时间复杂度为 \(O(n^2)\) .
代码:咕了
CF1109B Sasha and One More Name
原文：https://www.cnblogs.com/jklover/p/10390273.html
