网站建立连接不安全怎么解决,做百度推广网站得多少钱,办公网站建设,云南 旅游 网站建设问题#xff1a; 给定一个字符串#xff0c;仅由A、B、C3个字母组成。当出现连续两个不同的字母时#xff0c;你可以用另外一个字母替换它#xff0c;如有AB或BA连续出现#xff0c;你把它们替换为字母C#xff1b;有AC或CA连续出现时#xff0c;你可以把它们替换为字母… 问题 给定一个字符串仅由A、B、C3个字母组成。当出现连续两个不同的字母时你可以用另外一个字母替换它如有AB或BA连续出现你把它们替换为字母C有AC或CA连续出现时你可以把它们替换为字母B有BC或CB连续出现时你可以把它们替换为字母A。可以不断反复按照这个规则进行替换目标是使得最终结果所得到的字符串尽可能短求最终结果的最短长度。 输入字符串。长度不超过200仅由ABC3个字母组成。 输出按照上述规则不断消除替换所得到的字符串最短的长度。 例如 输入CAB输出2。因为我们可以把它变为BB或者变为CC。 输入BCAB输出1。我们可以把它变为AAB到AC到B也可以把它变为BBB但因为前者长度更短所以输出1。 先给出几个概念 纯字符串只含有一种字母的字符串称为纯字符串例如AAA就是一个纯字符串 混字符串含有至少两种字母的字符串称为混字符串例如ABC就是一个混字符串 最优长度字符串通过消除的最终结果的最短长度称为该字符串的最优长度。上面的示例中CAB的最优长度为2BCAB的最优长度为1 最优串字符串通过消除达到最优长度时的字符串称为最优串最优串可能不止一个。如CAB的最优串为BB和CC而BCAB的最优串为B。最优串一定是纯字符串 统计向量用XYZ表示字符串的统计向量其中X、Y、Z分别表示字符串中字母A、B、C的个数。上面的示例中CAB的统计向量为111BCAB的统计向量为121 统计特征向量用XYZ表示字符串的统计特征向量其中X、Y、Z分别表示字符串中字母A、B、C的个数的奇偶性用“奇”、“偶”表示。CAB的统计特征向量为奇奇奇BCAB的统计特征向量为奇偶奇 再给出几个推论 推论1纯字符串的最优长度就是纯字符串的长度。 很明显的只有一个字母没法消除所以最优长度就是纯字符串的长度 推论2在纯字符串前或后加另一个字母得到新的混字符串则新混字符串的最优长度为1 例如BBBBBBBA。则消除的过程是BBBBBBBA BBBBBBC BBBBBA BBBBC BBBA BBC BA C 其他的类似不再赘述 推论3若纯字符串的长度为偶数则在前或后添加另一个字母得到新的混字符串则新混字符串的最优串为添加的字母若纯字符串的长度为奇数则新混字符串的最优串为剩下的一个字母 假设纯字符串为BB添加字母A则新混字符串为BBABBA BC A 假设纯字符串为BBBB添加字母A则新混字符串为BBBBABBBBA BBA A 以此类推推论3的前半部得证 假设纯字符串为B添加字母A则新混字符串为BABA C 假设纯字符串为BBB添加字母A则新混字符串为BBBABBBA BA C 以此类推推论3的后半部得证 推论4混字符串的最优长度不超过2为1或2 证明 首先混字符串通过不停的消除最终能得到一个纯字符串因为若还有不同的字母则必相邻则还能继续消除。 若该纯字符串的长度为1或2则证明了该推论不过就算纯字符串长度为2还没证明最优长度一定是2可以肯定的是最优长度不超过2即1或2都有可能 若该纯字符串的长度大于2不失一般性假设该纯字符串的长度为KK2该纯字符串都由字母B组成字母A、C是一样的该纯字符串是通过NN≥1步消除得到的 那么回退一步第N-1步消除得到的混字符串为B……BACB……B其中A前面有K1个BC后面有K2个BK1K2K-1。也有可能是B……BCAB……B和B……BACB……B是一致的不再赘述了 那么根据K1和K2的取值不同可以优化出不同的消除 K1是奇数K2是奇数。利用推论3可知B……BA CCB……B AB……BACB……B CA B最优串是B最优长度为1 K1是奇数K2是偶数。利用推论3可知B……BA CCB……B CB……BACB……B CC则最优长度不超过2因为还没法证明最优长度不会是1 K1是偶数K2是奇数。利用推论3可知B……BA ACB……B AB……BACB……B AA则最优长度不超过2因为还没法证明最优长度不会是1 K1是偶数K2是偶数。利用推论3可知B……BA ACB……B CB……BACB……B AC B最优串是B最优长度为1 综上所述混字符串的最优长度不超过2 推论5统计特征向量为奇奇奇或偶偶偶的混字符串的最优长度为2其余的混字符串的最优长度为1 证明 考察一下每次消除统计特征向量的变化过程 假设字符串的统计特征向量为奇奇奇 假设消除是AC或CA B则A和C的个数减1而B的个数增加1则统计特征向量变为偶偶偶 假设消除是AB或BA C则A和B的个数减1而C的个数增加1则统计特征向量变为偶偶偶 假设消除是BC或CB A则B和C的个数减1而A的个数增加1则统计特征向量变为偶偶偶 综上所述统计特征向量为奇奇奇的混字符串经过1次消除后统计特征向量变为偶偶偶 同理可证统计特征向量为偶偶偶的混字符串经过1次消除后统计特征向量变为奇奇奇 由此可知反复消除后统计特征向量为奇奇奇的混字符串的最优串的统计特征向量是偶偶偶。因为最优串是纯字符串只能有1种字符所以最优串不可能是奇奇奇 同理可证统计特征向量为偶偶偶的混字符串的最优串的统计特征向量也是偶偶偶。 因此统计特征向量为奇奇奇或偶偶偶的混字符串的最优串的统计特征向量为偶偶偶 假设字符串的统计特征向量为奇偶偶 假设消除是AC或CA B则A和C的个数减1而B的个数增加1则统计特征向量变为偶奇奇 假设消除是AB或BA C则A和B的个数减1而C的个数增加1则统计特征向量变为偶奇奇 假设消除是BC或CB A则B和C的个数减1而A的个数增加1则统计特征向量变为偶奇奇 综上所述统计特征向量为奇偶偶的混字符串经过1次消除后统计特征向量变为偶奇奇 同理可证统计特征向量为偶奇奇的混字符串经过1次消除后统计特征向量变为奇偶偶 由此可知反复消除后统计特征向量为奇偶偶的混字符串的最优串的统计特征向量是奇偶偶。因为最优串是纯字符串只能有1种字符所以最优串不可能是偶奇奇 同理可证统计特征向量为偶奇奇的混字符串的最优串的统计特征向量也是奇偶偶。 因此统计特征向量为奇偶偶或偶奇奇的混字符串的最优串的统计特征向量为奇偶偶 同理可证 统计特征向量为偶奇偶或奇偶奇的混字符串的最优串的统计特征向量为偶奇偶 统计特征向量为偶偶奇或奇奇偶的混字符串的最优串的统计特征向量为偶偶奇 由推论4可知混字符串的最优长度不超过2 如果混字符串的最优长度为1则最优串是A统计特征向量是奇偶偶是B统计特征向量是偶奇偶是C统计特征向量是偶偶奇 如果混字符串的最优长度为2则最优串是AA或BB或CC统计特征向量是偶偶偶 所以统计特征向量为奇奇奇或偶偶偶的混字符串的最优长度是2。 统计特征向量为奇偶偶或偶奇奇的混字符串的最优长度为1最优串是A 统计特征向量为偶奇偶或奇偶奇的混字符串的最优长度为1最优串是B 统计特征向量为偶偶奇或奇奇偶的混字符串的最优长度为1最优串是C 证明完毕 结论 1、纯字符串的最优串就是自身最优长度就是自身的长度 2、统计特征向量为奇奇奇或偶偶偶的混字符串的最优长度为2 3、其余的混字符串的最优长度是1其中统计特征向量为奇偶偶或偶奇奇的混字符串的最优串是A统计特征向量为偶奇偶或奇偶奇的混字符串的最优串是B统计特征向量为偶偶奇或奇奇偶的混字符串的最优串是C 本文转自万仓一黍博客园博客原文链接http://www.cnblogs.com/grenet/p/3300591.html如需转载请自行联系原作者
