题目大意：给出一个字符串，判断其是否是回文串，如果不是是否能经过交换字母的位置变成回文串，如果不能输出“impossible”，如果能输出该字符串的回文串，如果有多个回文串输出字典序小的串，如abcba和bacab都满足条件但是a的字典序小所以a应该在前输出abcba
思路：有一个数组储存字符串中每一个字符出现的次数，如果其中有字符出现次数为奇数但只有一个字符出现次数为奇数，或所有字符出现次数都为偶数，则可以形成回文串，否则不能形成回文串，输出时按照从前到后的顺序输出一般字符，然后再从后向前输出另一半字符，就是符合条件的字典序小的回文串
#include <iostream>
#include <string.h>using namespace std;int main()
{int t;char str[1005];int vis[29];//储存每个字符出现的次数cin >> t;while (t--){memset(vis, 0, sizeof(vis));cin >> str;for (int i = 0; str[i]; i++)//统计每个字符出现的次数{vis[str[i] - 'a']++;}int flag = -1, cnt = 0;//储存出现次数为奇数的字符是哪个，标记是否有出现次数为奇数的字符for (int i = 0; i < 26; i++)//判断出现次数为奇数的字符有多少个{if (vis[i] % 2 != 0){flag = i;cnt++;}}if (cnt > 1)//如果有多余一个的字符出现次数为奇数{cout << "impossible\n";}else{for (int i = 0; i < 26; i++)//先输出一般字符{for (int j = 0; j < vis[i] / 2; j++){printf("%c", i + 'a');}vis[i] /= 2;//没输出一个字符将其个数除以2}if (cnt == 1)//如果有出现次数为奇数的字符{printf("%c", flag + 'a');}for (int i = 25; i >= 0; i--)//逆序输出另一半字符{for (int j = 0; j < vis[i]; j++){printf("%c", i + 'a');}}printf("\n");}}
}