UVA_10716
首先要预判一下是否可以构成回文串，剩下的工作就是看怎么移动了。
在移动的时候我们不妨先用点贪心的思想，每次应该先把两端的变成回文，如果我们先让两端变成回文之后，这样中间的字符在移动的时候就有可能少和1个移到两端的字符发生交换，因此这样的决策不会产生负面影响。
接下来就是去想我们要怎样让两端变成回文的了，其中一个猜想就是如果两端字符不同，那么就固定两端之一不动，通过移动另外一个字符使两端成为回文的，而且哪种方式交换次数少就选择哪种方式。至于为什么这么做，我暂时只是感觉可以，并没有进行严谨的证明。
#include<stdio.h>
#include<string.h>
#define MAXD 110
int h[256];
char b[MAXD];
void solve()
{
int i, j, k, n, ans, p, q;
scanf("%s", b);
memset(h, 0, sizeof(h));
for(i = 0; b[i]; i ++)
++ h[b[i]];
k = 0;
for(i = 'a'; i <= 'z'; i ++)
if(h[i] % 2)
++ k;
if(k > 1)
{
printf("Impossible\n");
return ;
}
n = strlen(b);
ans = 0;
for(i = 0; i < n / 2; i ++)
{
j = n - 1 - i;
if(b[i] != b[j])
{
for(p = j; b[p] != b[i]; p --);
for(q = i; b[q] != b[j]; q ++);
if(j - p < q - i)
{
ans += j - p;
for(k = p; k < j; k ++)
b[k] = b[k + 1];
}
else
{
ans += q - i;
for(k = q; k > i; k --)
b[k] = b[k - 1];
}
}
}
printf("%d\n", ans);
}
int main()
{
int t;
scanf("%d", &t);
while(t --)
{
solve();
}
return 0;
}