POJ 1854 Evil Straw Warts Live 题解《挑战程序设计竞赛》

POJ 1854 Evil Straw Warts Live 

文字游戏：求通过交换相邻字符使某字符串成为回文的最小步数。

一个回文字符串被定义为等同于自己本身的反转。 

给定一个字串，其不一定是个回文，计算最少的swap(交换次数)使这个字串成为回文。 

swap操作定义为交换两个相邻字符。 

例如字串"mamad" 可以使用三次swaps 转换成回文字串"madam"： 

1. swap "ad" 后的结果为"mamda"

2. swap "md" 后的结果为"madma"

3. swap "ma" 后的结果为"madam"

输入第一行有一个整数n表示接下来的数据组数。 

对于每组字串，长度最多为100 的小写字母够成，输出最少的交换次数， 

如果没办法转换成回文字串，则输出   "Impossible"。

4.6划分、解决、合并：分治法 

数列上的分治法 

判断是否能组成回文的方法是，若字符频次为奇数的字符多于一种，则无解，反之有解。

定义子串为母串[i:j]，i<j。初始情况子串等于母串，随算法进行不断缩短。子问题为将母串去除子串的部分变为回文。

母串去除子串后得到两个部分，分别命名为左串和右串。为了使左串最右字符和右串最左字符相等，分别比较替换左串最右字符和替换右串最左字符所需步数，取其较小者执行。比如

有两种替换方法，选择红色，得到下一个子问题：

依然选择红色，解决了整个问题。

#include <iostream>

using namespace std;
char s[8000 + 1];

int main()
{
#ifndef ONLINE_JUDGE
    freopen("in.txt", "r", stdin);
#endif
    int t;
    scanf("%d", &t);
    while (t--)
    {
        scanf("%s", s);
        int len = strlen(s);
        int count[26] = {0}, odd = 0;
        for (int i = 0; i < len; i++)
            count[s[i] - 'a']++;
        for (int i = 0; i < 26; i++)
            if (count[i] & 1)
                odd++;
        if (odd > 1)
            puts("Impossible");
        else
        {
            int step = 0;
            for (int i = 0, j = len - 1; i < j; i++, j--)
            {
                int l, r;
                for (r = j; r > i; r--)
                    if (s[i] == s[r])
                        break;
                for (l = i; l < j; l++)
                    if (s[j] == s[l])
                        break;
                if (j - r > l - i)
                {
                    step += l - i;  // 左边小
                    for (int k = l - 1; k >= i; k--)
                        swap(s[k], s[k + 1]);
                }
                else
                {
                    step += j - r;  // 右边小
                    for (int k = r + 1; k <= j; k++)
                        swap(s[k], s[k - 1]);
                }
            }
            printf("%d\n", step);
        }
    }
#ifndef ONLINE_JUDGE
    fclose(stdin);
#endif
    return 0;
}

看到这题的AC数才两百多，不知道为什么。

 知识共享署名-非商业性使用-相同方式共享：码农场 » POJ 1854 Evil Straw Warts Live 题解《挑战程序设计竞赛》