题解：CF193C Hamming Distance

· · 题解

题解：CF193C Hamming Distance

考试考到这道题思路想对了，思路想错了。

注：本题解使用 AI 进行笔误检查和学术问题检查，保证本人功劳为 AI 的五倍及以上。

题就不读了，较为简洁。

我们发现这 4 个字符串的每一个相同位都与其他的位没有关联，于是我们可以采取切片处理，将这四个字符串的切片单独进行计算。

我们设第一个字符串全部为 \texttt{a}（理由：我们可以通过将一个切片中的 \texttt{a} 和 \texttt{b} 同时颠倒来构造其他组合且不会破坏任何汉明距离的约束，因此直接假设和其余组合是等价的）。我们枚举后三个字符串的所有切片组合，并分别求出对汉明距离的贡献：

注：我们用 0 代表 \texttt{a}，1 代表 \texttt{b}，定义每一种组合 (x,y,z)（对应 t_1 至 t_7 这七个切片组合），h_{l,r} 表示 h(s_l,s_r)。

计数 组合 (x,y,z) s2 s3 s4 对汉明距离的贡献（都是加 1）
t_0 (0,0,0) \texttt{a} \texttt{a} \texttt{a} 无贡献（所有距离加 0）
t_1 (0,0,1) \texttt{a} \texttt{a} \texttt{b} h_{1,4}, h_{2,4}, h_{3,4}
t_2 (0,1,0) \texttt{a} \texttt{b} \texttt{a} h_{1,3}, h_{2,3}, h_{3,4}
t_3 (0,1,1) \texttt{a} \texttt{b} \texttt{b} h_{1,3}, h_{1,4}, h_{2,3}, h_{2,4}
t_4 (1,0,0) \texttt{b} \texttt{a} \texttt{a} h_{1,2}, h_{2,3}, h_{2,4}
t_5 (1,0,1) \texttt{b} \texttt{a} \texttt{b} h_{1,2}, h_{1,4}, h_{2,3}, h_{3,4}
t_6 (1,1,0) \texttt{b} \texttt{b} \texttt{a} h_{1,2}, h_{1,3}, h_{2,4}, h_{3,4}
t_7 (1,1,1) \texttt{b} \texttt{b} \texttt{b} h_{1,2}, h_{1,3}, h_{1,4}

于是可以列出方程：

\begin{cases} a = t_4 + t_5 + t_6 + t_7\\ b = t_2 + t_3 + t_6 + t_7\\ c = t_1 + t_3 + t_5 + t_7\\ d = t_2 + t_3 + t_4 + t_5\\ e = t_1 + t_3 + t_4 + t_6\\ f = t_1 + t_2 + t_5 + t_6\\ \end{cases}

将方程两两组合消元，得：

\begin{cases} \frac{a + b - d}{2} = t_6 + t_7\\ \frac{a + c - e}{2} = t_5 + t_7\\ \frac{b + c - f}{2} = t_3 + t_7\\ \end{cases}

我们发现六个方程有七个未知数，所以其中一个为自由变量，我们选择 t_7 作为自由变量：

\begin{cases} t_3 = \frac{b + c - f}{2} - t_7\\ t_5 = \frac{a + c - e}{2} - t_7\\ t_6 = \frac{a + b - d}{2} - t_7\\ t_1 = \frac{e + f - a - b}{2} + t_7\\ t_2 = \frac{d + f - a - c}{2} + t_7\\ t_4 = \frac{d + e - b - c}{2} + t_7\\ \end{cases}

我们开始推导出 t_7 的范围：[\max\{0, (a+b-e-f)/2, (a+c-d-f)/2, (b+c-d-e)/2\},\min\{\frac{a + b - d}{2}, \frac{a + c - e}{2}, \frac{b + c - f}{2}\}]。

显而易得，\max\{0, (a+b-e-f)/2, (a+c-d-f)/2, (b+c-d-e)/2\} 必须不大于 \min\{\frac{a + b - d}{2}, \frac{a + c - e}{2}, \frac{b + c - f}{2}\}，否则为无解。

方程列出来了，我们就来寻找一下条件来判断是否有解。因为 t_i 必须为非负整数，得出：a + b - d、a + c - e、b + c - f 都为非负整数且为二的倍数。此外，要使 t_1,t_2,t_4 为整数，e + f - a - b、d + f - a - c、d + e - b - c 也必须为偶数。

因为 t_i 为切片类型，所以一个切片长度为 1，最终的长度为 t_0+t_1+t_2+t_3+t_4+t_5+t_6+t_7，将 t_1+t_2+t_3+t_4+t_5+t_6 的表达式代入求和，可验证 t_1+t_2+t_3+t_4+t_5+t_6 = \frac{d + e + f}{2}，为常数（与 t_7 无关），且 t_0 显然应取 0 以使长度最小。因此总长度最小等价于使 t_7 最小，即 t_7=\max\{0, (a+b-e-f)/2, (a+c-d-f)/2, (b+c-d-e)/2\}。

我们最后按顺序将切片一次读入四个字符串中（具体参考表格），输出即可，代码如下（vjudge 远程通过记录）：

#include<bits/stdc++.h>
using namespace std;
#define int long long
int p[8];
signed main(){
    for(int i=1;i<=6;i++){
        scanf("%lld",&p[i]);
    }
    int s1=p[1]+p[2]-p[4];
    int s2=p[1]+p[3]-p[5];
    int s3=p[2]+p[3]-p[6];
    int k1=p[1]+p[2]-p[5]-p[6];
    int k2=p[1]+p[3]-p[4]-p[6];
    int k3=p[2]+p[3]-p[4]-p[5];
    if(s1<0||s2<0||s3<0||s1&1||s2&1||s3&1){
        printf("-1");
        return 0;
    }
    if(k1&1||k2&1||k3&1){
        printf("-1");
        return 0;
    }
    int p1=(p[1]+p[2]-p[4])/2;
    int p2=(p[1]+p[3]-p[5])/2;
    int p3=(p[2]+p[3]-p[6])/2;
    int pulow=max({0ll,k1/2,k2/2,k3/2});
    int puhigh=min({p1,p2,p3});
    if(pulow>puhigh){
        printf("-1");
        return 0;
    }
    int t7=pulow;
    int t3=p3-t7;
    int t5=p2-t7;
    int t6=p1-t7;
    int t1=t7-k1/2;
    int t2=t7-k2/2;
    int t4=t7-k3/2;
    int len=t1+t2+t3+t4+t5+t6+t7;
    printf("%lld\n",len);
    string a="",b="",c="",d="";
    for(int i=1;i<=len;i++){
        a+="a";
    }
    for(int i=1;i<=t1+t2+t3;i++){
        b+="a";
    }
    for(int i=1;i<=t4+t5+t6+t7;i++){
        b+="b";
    }
    for(int i=1;i<=t1;i++){
        c+="a";
    }
    for(int i=1;i<=t2+t3;i++){
        c+="b";
    }
    for(int i=1;i<=t4+t5;i++){
        c+="a";
    }
    for(int i=1;i<=t6+t7;i++){
        c+="b";
    }
    for(int i=1;i<=t1;i++){
        d+="b";
    }
    for(int i=1;i<=t2;i++){
        d+="a";
    }
    for(int i=1;i<=t3;i++){
        d+="b";
    }
    for(int i=1;i<=t4;i++){
        d+="a";
    }
    for(int i=1;i<=t5;i++){
        d+="b";
    }
    for(int i=1;i<=t6;i++){
        d+="a";
    }
    for(int i=1;i<=t7;i++){
        d+="b";
    }
    cout<<a<<"\n"<<b<<"\n"<<c<<"\n"<<d;
    return 0;
}

完结撒花！！！