admin管理员组

文章数量:1622631



题目大意：


给出N个长度为K的01串，现在让我们构造出来一个长度为K的01串，使得这N个串和构造出来的串的最大相似度最小。

相似度定义为两个字符串相等的位子的个数。


思路：


①因为长度并不大，而且N也不大 ，解题的时候总会想偏。


②其实这个题我们只要一遍Bfs即可，设定Vis【i】表示二进制串在十进制表示下为数字i的字符串是否遍历到了。

那么对于一个串101111来说，其距离为1的串有：001111 111111 100111 101011 101101 101110

那么过程中我们维护一下距离原来串最远的那个串是谁就行了。


时间复杂度O（2^k*k）；


Ac代码：

#include<stdio.h>
#include<string.h>
#include<queue>
using namespace std;
struct node
{
    int val,step;
}now,nex;
int vis[2000000];
char a[110000][22];
int n,k;
void Bfs()
{
    memset(vis,0,sizeof(vis));
    queue<node>s;
    for(int i=0;i<n;i++)
    {
        int sum=0;
        for(int j=0;j<k;j++)
        {
            if(a[i][j]=='1')sum+=(1<<j);
        }
        vis[sum]=1;
        now.val=sum,now.step=0;
        s.push(now);
    }
    int maxn=-1;
    int val=0;
    while(!s.empty())
    {
        now=s.front();
        s.pop();
        if(now.step>maxn)
        {
            maxn=now.step;
            val=now.val;
        }
        for(int i=0;i<k;i++)
        {
            if((now.val&(1<<i))>0)
            {
                nex.val=now.val-(1<<i);
            }
            else nex.val=now.val+(1<<i);
            if(vis[nex.val]==0)
            {
                vis[nex.val]=1;
                nex.step=now.step+1;
                s.push(nex);
            }
        }
    }
    int i=0;
    char ans[25];
    memset(ans,'0',sizeof(ans));
    while(val)
    {
        ans[i++]=val%2+'0';
        val/=2;
    }
    for(int i=0;i<k;i++)
    {
        printf("%c",ans[i]);
    }
    printf("\n");
}
int main()
{
    while(~scanf("%d%d",&n,&k))
    {
        for(int i=0;i<n;i++)scanf("%s",a[i]);
        Bfs();
    }
}






本文标签： 思维GymdistinctiveBFScharacter

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