最大汉明距离问题详解

问题分析

我们需要在区间$[l, r]$内找到两个整数$a$和$b$（满足$l \leq a \leq b \leq r$），使得它们的十进制表示的汉明距离最大。

关键观察：

1. 当两个数字位数不同时，较短数字需要补前导零，此时汉明距离等于较长数字的位数
2. 当两个数字位数相同时，我们需要找到在相同位数情况下差异最大的两个数字

核心思路

情况1：位数不同的情况

如果$l$和$r$的位数不同，那么最大汉明距离就是$r$的位数。

证明：

• 设$l$有$n$位，$r$有$m$位，且$n < m$
• 我们可以选择$a = 10^{m-1}$（即$m$位数的最小值）和$b = r$
• 由于$a$需要补前导零，实际上比较的是$00...0a$（$m$位）和$b$
• 此时汉明距离为$m$，这是可能的最大值

情况2：位数相同的情况

当$l$和$r$位数相同时，我们需要寻找在相同前缀之后能够产生最大差异的位置。

算法策略：

1. 找到$l$和$r$从左端开始的第一个不同位置$p$
2. 最大汉明距离等于总位数减去相同前缀的长度

正确性证明：

• 在位置$p$，$l[p] < r[p]$
• 我们可以选择：
  • $a$：在位置$p$取$l[p]$，后面所有位取最小值（通常为0）
  • $b$：在位置$p$取$r[p]$，后面所有位取最大值（通常为9）
• 这样从位置$p$开始的所有位都不同，汉明距离为$n - p + 1$
• 这是可能的最大值，因为前$p-1$位必须相同（否则可能超出区间范围）

算法实现详解

输入处理

由于数字可能达到$10^{1000000}$，我们必须使用字符串处理：

scanf("%s", s + 1);  // 读取l
scanf("%s", t + 1);  // 读取r
int n = strlen(s + 1), m = strlen(t + 1);

核心逻辑

if (n != m)
    printf("%d\n", max(n, m));
else {
    int p = 0;
    while (p < n && s[p + 1] == t[p + 1])
        p++;
    printf("%d\n", n - p);
}

代码解析：

• 如果位数不同：直接输出较大位数
• 如果位数相同：
  • 找到第一个不同的位置$p$
  • 汉明距离 = 总位数$n$ - 相同前缀长度$p$

正确性验证

样例1验证

输入：

l = 11, r = 17

• 位数相同：$n = m = 2$
• 相同前缀：第一个字符'1'相同，$p = 1$
• 汉明距离：$2 - 1 = 1$
• 验证：选择$12$和$16$，二进制表示：
  • $12$ → "12"
  • $16$ → "16"
  • 只有第二位不同，距离为$1$

样例2验证

输入：

l = 1, r = 11

• 位数不同：$n = 1$, $m = 2$
• 输出：$\max(1, 2) = 2$
• 验证：选择$1$和$10$：
  • $1$ → "01"（补前导零）
  • $10$ → "10"
  • 两位都不同，距离为$2$

边界情况分析

情况1：$l = r$

• 位数相同，所有位都相同
• $p = n$，汉明距离 = $n - n = 0$
• 正确：同一个数字的汉明距离为0

情况2：$l$和$r$相差很大但位数相同

例如：$l = 1000$, $r = 9999$

• 位数相同：$n = m = 4$
• 第一个不同位置：$p = 1$（'1' vs '9'）
• 汉明距离：$4 - 1 = 3$
• 可选：$a = 1000$, $b = 9999$，距离确实为3

情况3：极端大数

• 算法使用字符串处理，支持$10^{1000000}$规模
• 时间复杂度：$O(\max(n, m))$，线性复杂度

算法复杂度分析

时间复杂度

• 字符串长度比较：$O(1)$
• 相同前缀扫描：$O(\min(n, m))$
• 总复杂度：$O(n)$，其中$n$是数字的位数

空间复杂度

• 存储两个字符串：$O(n + m)$
• 其他变量：$O(1)$
• 总空间：$O(n + m)$

数学证明

定理1：位数不同时的最优性

设$l$有$n$位，$r$有$m$位，$n < m$，则最大汉明距离为$m$。

证明：

• 任意两个$m$位数的汉明距离最多为$m$
• 选择$a = 10^{m-1}$（$m$个位：1后面$m-1$个0）和$b = r$
• 由于$a$需要补前导零，实际上比较的是$00...01$和$r$
• 如果$r \neq 10^{m-1}$，则所有位都不同，距离为$m$
• 如果$r = 10^{m-1}$，则$l = r$，但此时$n = m$，矛盾

定理2：位数相同时的最优性

设$l$和$r$都是$n$位数，第一个不同位置为$p$，则最大汉明距离为$n - p + 1$。

证明：

• 前$p-1$位必须相同，否则可能超出$[l, r]$范围
• 在位置$p$，我们可以让$a[p] = l[p]$, $b[p] = r[p]$
• 对于位置$p+1$到$n$：
  • 让$a$的这些位取最小值（通常为0）
  • 让$b$的这些位取最大值（通常为9）
• 这样确保了从位置$p$开始的所有位都不同
• 汉明距离 = $(n - p + 1)$

扩展思考

问题变种

1. 加权汉明距离：不同位可能有不同的权重
2. 多进制情况：推广到任意进制下的汉明距离
3. 多个数字：在区间内找$k$个数字，最大化两两汉明距离的最小值

算法优化

当前的$O(n)$算法已经是最优的，因为至少需要扫描输入数据。

总结

本题通过巧妙的观察和简单的字符串处理，高效地解决了大数区间内的最大汉明距离问题。核心洞察在于：

1. 位数差异直接决定最大距离：当位数不同时，答案就是较大数的位数
2. 前缀匹配确定相同部分：当位数相同时，找到第一个不同位置即可确定最大差异

算法在$O(n)$时间内解决问题，适用于极端大规模的数据输入，体现了在数论问题中字符串处理技术的重要性。