放牧代码和思想
专注自然语言处理、机器学习算法
    愛しさ 優しさ すべて投げ出してもいい

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

目录

s2.png挑战程序设计竞赛第二版.jpg

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。初始情况子串等于母串,随算法进行不断缩短。子问题为将母串去除子串的部分变为回文。

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

s1.png

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

s2.png

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

#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;
}

16524469 hankcs 1854 Accepted 148K 204MS C++ 1400B 2017-01-27 11:59:10

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

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

评论 欢迎留言

  • 昵称 (必填)
  • 邮箱 (必填)
  • 网址

我的作品

HanLP自然语言处理包《自然语言处理入门》