牛客训练41D最小相似度bfs

最小相似度

　　题目大意：对于位数相同的两个二进制串，SIM(A,B)为它们的相似度，也就是A^B中0的个数。现在给定一堆串，找出一个T使得max{SIM(S₁,T),SIM(S₂,T),......,SIM(S_n,T)}最小，不过不用输出T，只需要输出那个最小值

正解应该是FWT，不过没学过，所以也没做出来，而给出的题解的是用bfs做的，还真没想到能够用搜索做，刚开始看也不理解，不过研究了一下还是，挺好理解的。

　　首先，也是为什么可以用bfs的一点，就是串的长度最大只到20，也就是2²⁰=1048576种状态，可以通过bfs来遍历，那接下来怎么搜，搜什么呢？

　　相似度是A^B中0的个数，但0的个数我们并不好控制，但我们可以控制1的个数,也就是不相似度usim。像（1<<i）就是1在第i位，其他位都是0，那么B=A^(1<<i)的话，B就是A不相似度为1的串,而再有C=B(1<<i)并且C!=A的话，C就是A不相似度为2的串，所以我们就可以像bfs一样一层一层的找到最大的不相似度。而对于多个串的话，就是多起点bfs了。

　　那为什么这样可以使，答案刚好是跟多个串的不相似度中的最大的呢？像A=111，B=001的话,A的最大不相似的串是000，但A要第3层才能遍历到000,B第1层就能遍历到000，这样像两边往中间逼近一样，能遍历到的最大的那个不相似度就是对于所有串来说的最大不相似度

　　最后，再拿长度减去最大不相似度就可以得到最小相似度了，详情见代码

 #include<cstdio>

 #include<cstring>

 #include<queue>

 using namespace std;

 const int N=<<;

 char s[];

 int n,m,usim[N];

 int main()

 {

     memset(usim,-,sizeof(usim));

     scanf("%d%d",&n,&m);

     queue<int> q;

     for(int i=;i<n;i++)

     {

         scanf("%s",s);

         int x=;

         for(int j=;j<m;j++)

             x=(x<<)|(s[j]-'');//将串转换成数字表示状态

         if(usim[x]==-)

         {

             usim[x]=;//自己和自己的不相似度为0

             q.push(x);//多起点

         }

     }

     int ans=;

     while(!q.empty())

     {

         int x=q.front();

         q.pop();

         if(usim[x]>ans)

             ans=usim[x];//找到最大不相似度

         for(int i=;i<m;i++)

         {

             int y=x^(<<i);//y是x第i位取反的结果

             if(usim[y]==-)

             {

                 usim[y]=usim[x]+;//所以y与起点串的不相似度就是x的+1

                 q.push(y);

             }

         }

     }

     printf("%d\n",m-ans);

     return ;

 }

再偷懒就就就自己打自己

巴特西

牛客训练41D最小相似度bfs

最新文章

热门文章