电子科技大学链时代工作室招新题C语言部分---题号H

1. 题目

最有操作的一道题，有利于对贪心算法有个初步了解。

这道题的开篇向我们介绍了一个叫汉明距离的概念。

汉明距离指的就是两个相同长度的字符串的不同字符的个数。

例如，abc和acd，b与c不同，c与d不同，所以这两个字符串的汉明距离就是2。

这道题就要求我们找到一个字符串，使得该字符串与已知的两个字符串的汉明距离相同，并且该字符串在字典序上要尽可能地小。（字典序上最小，就是在符合条件的字符串中，用strcmp比较出来的最小的那个）。

题目言简意赅，但却是最考验思路的一道题。

输入

第一行输入一个整数T（1 <= T <= 100），表示接下来要输入几个案例。

接下来输入T个测试案例，对每个案例，输入两行长度相同的字符串（单个字符串长度不超过 $10^{4}$ ，字符串总长度不超过 $10^{6}$ ）。

输出

输出T行，每行为其对应案例的所求字符串。

2. 第一版解法

前面说过，这道题十分考验思路，我们第一版时，我们没有找到很好的办法，解法比较暴力，思路也比较混乱。

2.1 思路

1. 我们要比较目标字符串与两个原字符串的汉明距离，那我们势必要先生成一个目标字符串，然后再根据汉明距离的差异来调整目标字符串。

2. 既然要目标字符串在字典序上最小，那我们一开始生成的目标字符串就尽可能小，并且只在必要时调整，这样才能保证得到我们想要的结果。

3. 所以，我们决定将目标字符串初始化为每个元素都是'a'，并从后往前调整（越靠前的字符权重越高，所以优先调整靠后的字符）。

4. 初始时，两个原字符串与目标字符串的汉明距离分别就是两个字符串中不等于'a'的字符的数量，然后根据不同的情况，我们对字符做不同的调整。

2.2 代码

#include <stdio.h>
#include <string.h>int main()
{int T = 0;scanf("%d", &T);char arr1[10001] = {0};char arr2[10001] = {0};char ret[101][10001] = {0};for(int k = 0; k < T; k++){char* tmp = &ret[k][0];scanf("%s", arr1);scanf("%s", arr2);int len = strlen(arr1);int hm1 = len, hm2 = len;//记录汉明数tmp[len] = '\0';for(int i = 0; i < len; i++){tmp[i] = 'a';if(arr1[i] == 'a')hm1--;if(arr2[i] == 'a')hm2--;}int op = len - 1;while(hm1 != hm2){if(arr1[op] == arr2[op])//两个相同，改变无意义且会增大字符{op--;}else if(hm1 - hm2 >= 2&&'a' == arr2[op])//汉明数相差超过二{tmp[op] = arr1[op];hm1--;hm2++;op--;}else if(hm2 - hm1 >= 2&&'a' == arr1[op]){tmp[op] = arr2[op];hm2--;hm1++;op--;}else if(op >= 1&&hm1 - hm2 == 2&&'a' == arr2[op - 1]&&arr1[op - 1] == 'b')//下一次能改两，且刚好差两{tmp[op - 1] = arr1[op - 1];hm1--;hm2++;op--;}else if(op >= 1&&hm2 - hm1 == 2&&'a' == arr1[op - 1]&&arr2[op - 1] == 'b'){tmp[op - 1] = arr2[op - 1];hm2--;hm1++;op--;}else if(hm1 > hm2&&'a' != arr1[op]&&'a' != arr2[op]){tmp[op] = arr1[op];hm1--;op--;}else if(hm1 < hm2&&'a' != arr1[op]&&'a' != arr2[op]){tmp[op] = arr2[op];hm2--;op--;}else if(hm1 - hm2 == 1&&'a' == arr2[op]){for(char j = 'a'; j <= 'z'; j++){if(arr1[op] != j&&arr2[op] != j){tmp[op] = j;break;}}hm2++;op--;}else if(hm2 - hm1 == 1&&'a' == arr1[op]){for(char j = 'a'; j <= 'z'; j++){if(arr1[op] != j&&arr2[op] != j){tmp[op] = j;break;}}hm1++;op--;}else{op--;}}}for(int i = 0; i < T; i++){printf("Case %d: %s\n", i + 1, ret[i]);}return 0;
}

2.3 总结

这一版中，我们考虑了许多种情况，可以看到if和else语句写了一长串，以告诉程序在遇到不同情况时该怎么做。

感兴趣的小伙伴可以仔细看看第4和5个分支，这种情况是最难想到的。比如输入aab和bbc时，正确答案应该是aba，而没有这两个分支时会输出acc。

虽然这段代码看起来天衣无缝，万无一失，能讨论的情况都考虑了（我至今都想不通到底是什么测试用例会导致其失败）。但是在oj上跑时，始终会提示“wrong answer on test 2！”。

还记得我们总结的经验教训吗，当你的代码开始用if语句处理特殊输入时，就要开始考虑改改了。

用if和else语句来告诉计算机该怎么处理不同的情况，这样的算法是远比不上一个通用的算法的。

3. 最终版解法

这一版解法是我在走投无路的情况下向大佬求教，得到耐心指点之后才搞定的。

3.1 思路

这一版的思路将我们之前的做法全盘推翻了，这一次我们采用从前向后操作的顺序，并且不是调整出目标字符串，而是直接生成出目标字符串。

在写出第一版之前，我也考虑过从前往后生成目标字符串的写法。但是，这么做会有两个问题：

1. 目标字符串逐步生成，那么我在生成过程中如何知道当前位置该放什么，才能保证之后有办法使得目标字符串与两个原字符串的汉明距离相同（之后称这个目标为“汉明距离差值为0”）？

2. 如何确保我生成的字符串是字典序最小的？

为了解决这两个问题，我们需要深入地去挖掘一些隐藏的数学关系：

导致目标字符串与两个原字符串的汉明距离不同的，只能是两个原字符串字符不同的位置。也就是说，在目标字符串生成到某个位置时，它与两个原字符串的汉明距离的差值一定小于未生成部分，两个原字符串的汉明距离。我们只需要确保这一点成立，就可以将尽可能小的字符放在该位置。

好像这段话不长，但我就是看不懂？

没关系，好好理解一下，很快就会有一种恍然大悟的感觉。

那么，为什么要从前往后操作呢？因为随着我操作的进行，需要满足的条件会越来越苛刻。前面的字符更高贵，苦了后面也不能苦前面。

这个思路的妙处在于，它要求要满足的条件是一个必要条件，将条件限制到最苛刻的情况（必要条件不满足，结果一定不成立），我再考虑放置较大的字符，这样就可以确保我得到的是最小字符串。这也就是贪心算法的基本思想。

而且，随着我操作的进行，两个原字符串的汉明距离会逐渐减小，那么目标字符串与两个原字符串的汉明距离之差也会逐渐减小，直到最后归于零。

3.2 代码

#include <stdio.h>
#include <string.h>int HanMingDistance(char* str1, char* str2, int len)
{int distance = 0;for(int i = 0; i < len; i++){if(str1[i] != str2[i])distance++;}return distance;
}int main()
{int T = 0;scanf("%d", &T);char arr1[10001] = {0};char arr2[10001] = {0};char ret[101][10001] = {0};for(int k = 0; k < T; k++){char* tmp = &ret[k][0];scanf("%s", arr1);scanf("%s", arr2);int len = strlen(arr1);tmp[len] = '\0';int dice = 0;//输入的两个字符串当前位置起的汉明距离int hm1 = 0, hm2 = 0;for(int i = 0; i < len; i++){if(arr1[i] == arr2[i]){tmp[i] = 'a';continue;}dice = HanMingDistance(arr1+i, arr2+i, len-i);int tem1 = 0, tem2 = 0;for(char j = 'a'; j <= 'z'; j++){if(arr1[i] != j)tem1 = 1;elsetem1 = 0;if(arr2[i] != j)tem2 = 1;elsetem2 = 0;if(hm1 + tem1 - hm2 - tem2 < dice&&hm2 + tem2 - hm1 -tem1 < dice){hm1 = hm1 + tem1;hm2 = hm2 + tem2;tmp[i] = j;break;}}}}for(int i = 0; i < T; i++){printf("Case %d: %s\n", i + 1, ret[i]);}return 0;
}