第七届蓝桥杯---密码脱落

X星球的考古学家发现了一批古代留下来的密码。
这些密码是由A、B、C、D、E 五种植物的种子串成的序列。
仔细分析发现,这些密码串当初应该是前后对称的(也就是我们说的镜像串)。
由于年代久远,其中许多种子脱落了,因而可能会失去镜像的特征。

你的任务是:
给定一个现在看到的密码串,计算一下从当初的状态,它要至少脱落多少个种子,才可能会变成现在的样子。

输入一行,表示现在看到的密码串(长度不大于1000)
要求输出一个正整数,表示至少脱落了多少个种子。
例如,输入:
ABCBA
则程序应该输出:
0

再例如,输入:
ABECDCBABC
则程序应该输出:
3
资源约定:
峰值内存消耗 < 256M
CPU消耗 < 3000ms

请严格按要求输出,不要画蛇添足地打印类似:“请您输入…” 的多余内容。
所有代码放在同一个源文件中,调试通过后,拷贝提交该源码。
注意: main函数需要返回0
注意: 只使用ANSI C/ANSI C++ 标准,不要调用依赖于编译环境或操作系统的特殊函数。
注意: 所有依赖的函数必须明确地在源文件中 #include , 不能通过工程设置而省略常用头文件。

提交时,注意选择所期望的编译器类型。

开始看没有什么思路,雨轩说要用贪心法,睡前稍有思路,今天验证一下吧,不过对C语言不熟悉,用C#试吧

算法一:递归遍历(感觉效率太低)

int mx;
void Do(string s,int x)
{
    if (s[0] != s[s.Length - 1])
    {
        Do(s.Substring(1),x+1);
        Do(s.Substring(0, s.Length - 1),x+1);
    }
    else
    {
        if (s.Length > 2)
            Do(s.Substring(1, s.Length - 2), x);
        else
            if (x < mx)
                mx = x;
    }
}

算法二:空间换一些效率吧,算广度不?

int Test()
{
    while(true)
    {
        if (a.Count==0)
            break;
        string s=(string)a[0];
        int c = (int)b[0];
        a.RemoveAt(0);
        b.RemoveAt(0);
        while ((s.Length > 1) && (s[0] == s[s.Length - 1]))
        {
            s = s.Substring(1, s.Length - 2);
        }
        if (s.Length<2)
            return c;
        else
        {
            a.Add(s.Substring(1));
            a.Add(s.Substring(0, s.Length - 1));
            b.Add(c + 1);
            b.Add(c + 1);
        }
    }
    return -1;
}

没想到效率差别还真大
45.png

标签: none

添加新评论