admin管理员组文章数量:1622635
题意:给你n个长度为k的01串,求一个串,让这个串和其他各个串相同位置上相同字符的总数的最大值最小。
题解:首先对于一个串(假设10110),对于它能走到的串有5个分别是,00110,11110,10010,10100,10111,也就是只有一位与原串不一样的串。然后我们对于所有的源串,我们bfs,找到(1<<20)个串中,距离这些源串最远的串,就是匹配数目最大值最小的串。
AC代码:
#include<stdio.h>
#include<queue>
#include<string.h>
using namespace std;
char a[25];
int dist[(1<<20)];
queue<int>que;
int main()
{
memset(dist,-1,sizeof(dist));
int n,k;
scanf("%d%d",&n,&k);
for(int i=0;i<n;i++)
{
scanf("%s",a);
int now=0;
for(int g=0;g<k;g++)
if(a[g]=='1')
now|=(1<<g);
que.push(now);
dist[now]=0;
}
int ans,ma=0;
while(!que.empty())
{
int K=que.front();
que.pop();
for(int i=0;i<k;i++)
{
int to=K^(1<<i);
if(dist[to]!=-1)continue;
dist[to]=dist[K]+1;
que.push(to);
if(ma>dist[to]);
{
ma=dist[to];
ans=to;
}
}
}
for(int i=0;i<k;i++)
printf("%d",ans%2),ans/=2;
printf("\n");
}
本文标签: 想法GymDDistinctiveBFScharacter
版权声明:本文标题:Gym 101572 DDistinctive Character [bfs+想法] 内容由热心网友自发贡献,该文观点仅代表作者本人, 转载请联系作者并注明出处:https://www.elefans.com/xitong/1728870751a1177248.html, 本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如发现本站有涉嫌抄袭侵权/违法违规的内容,一经查实,本站将立刻删除。
发表评论