Codeforces gym 102823H. Hamming Distance 题解
题目大意
定义汉明距离为两个等长字符串间不同字符的个数和，给定两个字符串，求字典序最小的到这两个字符串汉明距离相同的字符串。
题解
我们设给定两个字符串为 \(a\) 和 \(b\) ，构造的字符串为 \(c\)，若在第 \(i\) 位 \(a,b\) 的字符相等，则 \(c\) 放字符 \('a'\) 一定是最优解（考虑从前往后依次放字符）。若不相等，则当我们选的字符和 \(a\) 的相等时，\(c\) 到 \(b\) 的距离会比 \(a\) 加 \(1\)。假设当前是第 \(i\) 位，字符从小到大枚举到了 \(x\) ，设 \(sd = H(c,a)-H(c,b)\) 并且 \(sd\) 只考虑前 \(i-1\) 位已经填好的，\(cd\) 为仅考虑当前位的 \(H(c,a)-h(c,b)\)，假设从 \(i+1\) 位往后，\(a,b\) 后缀的不相同的字符数为 \(d[i+1]\)，假设选定 \(x\) ，则之后可能的 \(\beta=H(c,a)-H(c,b)\) 的 \(\beta\) 的取值范围为 \[
\beta\in[-d[i+1]+sd+cd,d[i+1]+sd+cd]
\] 记为 \(\beta\in[L,R]\)，这个区间记为 \(I\)，由于最终要求 \(H(c,a)=H(c,b)\)，即 \(H(c,a)-H(c,b)=0\)，所以要求必须有 \(0\in I\)。
在下面的代码中，我在 i==n 时加入了一个断言 assert(L == 0 && R == 0)，因为 \(d[n+1]=-d[n+1]=0\)，可以得到 \(L=R=sd+cd\)，即最终这个区间收敛到了一点，且该点为\(y=sd+cd\)（前提是答案始终存在），此时只有 \(L=R=0\) 才能满足上文中的条件，故最终循环结束后，可以得到 \[
H(c,a)=H(c,b)
\]
代码
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
|
#include <cstdio>
#include <cctype>
#include <algorithm>
#include <cstring>
#include <iostream>
#include <cassert>
#include <cmath>
using namespace std;
typedef long long ll;
template <typename _Tp>
void read(_Tp &a, char c = 0, int f = 1) {
for(c = getchar(); !isdigit(c); c = getchar()) if(c == '-') f = -1;
for(a = 0; isdigit(c); a = a * 10 + c - '0', c = getchar()); a *= f;
}
template <typename _Tp>
void write(_Tp a) {
if(a < 0) putchar('-'), a = -a;
if(a > 9) write(a / 10); putchar(a % 10 + '0');
}
const int N = 1e4 + 5;
char a[N], b[N];
int d[N];
void init() {
memset(d, 0, sizeof(d));
}
int main() {
int T;
read(T);
for (int _T = 1; _T <= T; _T++) {
init();
int n;
scanf("%s", a + 1);
scanf("%s", b + 1);
n = strlen(a + 1);
for(int i = n; i >= 1; i--) {
if(a[i] != b[i]) {
d[i] = d[i + 1] + 1;
} else {
d[i] = d[i + 1];
}
}
int cd, sd;
cd = sd = 0;
printf("Case %d: ", _T);
for(int i = 1; i <= n; i++) {
if(a[i] == b[i]) {
putchar('a');
continue;
}
for(int x = 'a'; x <= 'z'; x++) {
int d1 = a[i] != x;
int d2 = b[i] != x;
cd = d1 - d2;
int L = -d[i + 1] + sd + cd;
int R = d[i + 1] + sd + cd;
if(L <= 0 && R >= 0) {
putchar(x);
sd += cd;
if(i == n) {
assert(L == 0 && R == 0);
}
break;
}
}
}
puts("");
}
return 0;
}
|