出题人题解 | #最小相似度#

最小相似度

https://ac.nowcoder.com/acm/problem/22563

原题解链接:https://ac.nowcoder.com/discuss/157310

此题可以用FWTFWT通过,但是出题时的想法是一道BFSBFS就可过的题。

MM最大只有2020,如果把每个二进制串看成一个状态,最多只有220=10485762^{20}=1 048 576个状态。

我们把开始给定的所有二进制串看成起始点,每一步搜索对二进制串进行一个二进制位的翻转对全部状态进行BFSBFS,设搜到的步数最大的状态步数为XX,则答案就是MXM-X

复杂度O(N2M)O(N 2^M)


#include<bits/stdc++.h>
using namespace std;
int deep[1<<26];
void solve(){
    queue<int> q;
    int n,m,ans=0;
    char s[30];
    scanf("%d %d",&n,&m);
    memset(deep,-1,sizeof(int)*(1<<(m+1)));
    for(int i=0;i<n;i++){
        scanf("%s",s);
        int f=0;
        for(int j=0;j<m;j++){
            f+=(1<<j)*(s[j]-'0');
        }
        if(deep[f]==-1) {
            deep[f]=0;
            q.push(f);
        }
    }
    while(!q.empty()){
        int u=q.front();
        q.pop();
        ans=max(ans,deep[u]);
        for(int i=0;i<m;i++){
            if(deep[u^(1<<i)]==-1){
                deep[u^(1<<i)]=deep[u]+1;
                q.push(u^(1<<i));
            }
        }
    }
    if(n>300000) printf("!!!\n");
    printf("%d\n",m-ans);
}
int main()
{
    solve();
}
全部评论

相关推荐

不愿透露姓名的神秘牛友
07-07 13:46
点赞 评论 收藏
分享
07-07 12:47
门头沟学院 Java
码农索隆:竟然还真有卡体检报告的
点赞 评论 收藏
分享
Southyeung:我说一下我的看法(有冒犯实属抱歉):(1)简历不太美观,给我一种看都不想看的感觉,感觉字体还是排版问题;(2)numpy就一个基础包,机器学习算法是什么鬼?我感觉你把svm那些写上去都要好一点。(2)课程不要写,没人看,换成获奖经历;(3)项目太少了,至少2-3个,是在不行把网上学习的也写上去。
点赞 评论 收藏
分享
码农索隆:单休一个月少休息4天,一年就是48天,平时节假日,别人3天假期,单休的两天
点赞 评论 收藏
分享
评论
点赞
收藏
分享

创作者周榜

更多
牛客网
牛客网在线编程
牛客网题解
牛客企业服务