链接: http://codeforces.com/contest/600/problem/C 这题开始做的时候, 还是很费脑的, 首先要关注题中要求的回文问题, 不难看出是需要计算字符串中字频的奇偶, 然后可以想到, 回文只能有不能超过一种奇数的字符. 但是后边很难想的是, 如何修改才能满足 lexicographically (alphabetically) smallest palindrome(字典序下最小回文). 这时可以看到题中给出的回文都是lower case, 所以用双指针的方法, 前后两个指针扫描字频数组, 找到奇数字频的回文, 然后把字典序大的回文给字典序小的回文. 最后一个考点是重构回文, 这里需要注意的是, 我们上一步中已经通过交换的方式消灭了奇数字频的回文, 但是真的完全消灭了么? 其实不然, 回文是可以有一个奇数的字频的字符存在的, 这个字频的字符应该放在中间. 所以我们这里用odd_index, 起始值为-1(表示没有奇数字频), 如果上一步后odd_index不是-1, 这表示我们发现一个字频 这里有两个小技巧: 第一, 当重构回文的时候, 因为题中要求 If there are several ways to do that you should get the lexicographically (alphabetically) smallest palindrome. 我们需要从大的字符往小的字符扫描count数组重构回文, 因为我们想把大的字符放在中间, 把小的字符放到两边, 这种构建方法确保了构建后的回文是字典序最小的回文. […]