题型描述

推公式

题目大意

定义两个 $01$ 串相邻当且仅当两个字符串只有一个字符不同。现在规定 $01$ 串长度是 $n$ ，在所有的 $2^n$ 个 $01$ 串中给出三个被感染的 $01$ 串，这些 $01$ 串每轮会把相邻的所有字符串感染，问经过多少轮之后，所有的 $01$ 串都被感染。

数据范围

$2<=n<=2\cdot10^5$

题解

首先定义两个字符串的距离：
由于一个字符串与相邻的字符串只有一个字符不同
所以当两个字符串有 $n$ 个字符不同的时候，定义它们距离为 $n$

显然，每个长度为 $n$ 的字符串都有一个距离为 $n$ 的反串与之对应
对于感染的过程。

不难发现只有一个感染源的时候，以这个感染源开始感染，一直到这个感染源的尽头才能够全部感染，答案显然为 $n$。

我们任取三个感染源之一 $A$ 作为根，那么其余的感染源都在 $A$ 的感染路径上。

考虑如何做才能缩短感染的路径，同时保证感染进行完全：

为了确保感染进行完全，其他的感染源必须回到感染起点或者感染终点，之后再掉头感染一遍。
回到起点肯定会浪费更多之间，因为起点已经开始感染，所以肯定要去到感染终点，之后掉头向起点的方向感染。

这样就能形成一个相遇问题，减少走完全程需要的步骤。
而剩余的两个感染源中，我们选取离 $A$ 最远的感染源，记录距离为 $k$
则答案显然为 $floor(\frac{n+(n-k)}{2})$

推导到这里发现答案只与 $k$ 有关
而由于 $A$ 是任取的，所以实际上的 $k$ 应为三个感染源两两之间距离的最大值。

代码

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int maxn=1e5+10;
const ll mod=1e9+7;

void solve(){
    int n;
    cin>>n;
    string s1,s2,s3;
    cin>>s1>>s2>>s3;
    int cnt1=0,cnt2=0,cnt3=0;
    for(int i=0;i<n;++i){
        if(s1[i]!=s2[i])cnt1++;
        if(s3[i]!=s2[i])cnt2++;
        if(s1[i]!=s3[i])cnt3++;
    }
    int mx=max(cnt1,max(cnt2,cnt3));
    cout<<(2*n-mx)/2<<'\n';
}
int main() {
    ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);
    int T=1;
    cin>>T;
    while (T--) {
        solve();
    }
    return 0;
}