admin管理员组

文章数量:1622625

题目大意：
给你两个数字n,k
再给你n个长度为k的01字符串
让你给出一个长度为k的01字符串
并且这个字符串与这n个字符串每一个字符串相同位数的数字的最大值要尽可能的小

思路：
bfs
我们可以设n个字符串一开始的距离为0
然后对于每个字符串，当变动其中一个位数的数字的时候距离+1
比如：110，这个时候距离为0，则010,100,111距离为1
当后面的字符串改动正好是前面字符串已经改动或者出现过的时候
因为bfs一直维护的是最短的距离，这个时候就直接跳到下个循环就好了（因为距离不会再增大了）
我们找最远距离的字符串就是答案
时间复杂度是O(2k)

AC代码：

#include<bits/stdc++.h>

using namespace std;

int dis[(1<<20)];
queue<int>q;
int main()
{
    memset(dis,-1,sizeof(dis));
    int n,k,temp;
    cin>>n>>k;
    for(int i=0; i<n; i++)
    {
        string s;
        cin>>s;
        temp=0;
        for(int j=0; j<k; j++)temp|=((s[j]-'0')&1)<<(k-j-1);
        q.push(temp);
        dis[temp]=0;
    }
    int ans=0,mmax=0;
    while(!q.empty()){
        int x=q.front();
        q.pop();
        for(int i=0;i<k;i++){
            temp=x^(1<<i);
            if(dis[temp]!=-1)continue;//因为bfs维护的是最短距离，遇见前面出现过的直接跳过就OK了
            dis[temp]=dis[x]+1;
            if(dis[temp]>mmax){//记录最大距离
                mmax=dis[temp];
                ans=temp;
            }
            q.push(temp);
        }
    }
    for(int i=k-1;i>=0;i--)printf("%d",(ans>>i)&1);
}

本文标签： Gymcharacterdistinctive

版权声明：本文标题：Gym - 101572D D - Distinctive Character 内容由热心网友自发贡献，该文观点仅代表作者本人， 转载请联系作者并注明出处：https://www.elefans.com/xitong/1728870394a1177209.html， 本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如发现本站有涉嫌抄袭侵权/违法违规的内容，一经查实，本站将立刻删除。