admin管理员组文章数量:1622541
【题意】
给你n个01串,问你找到一个串,使得这个串与其他串的最大相似度最小。
【思路】
对应为相同得分,求最大最小。可以转化为不同得分,求最小最大。
从一个串开始,可以一步变为其他串的有k种。比如01001,得到一分有11001,00001,01101,01011,01000,这几种情况,那么我们多源bfs,维护每个点最小被访问的距离长度,那么由bfs性质可知,max(dis[i])的值就是所有点中最小的距离的最大值。
【代码】
#include<stdio.h>
#include<queue>
#include<string.h>
using namespace std;
char s[25];
int dis[(1 << 20)];
queue<int>que;
int main(){
memset(dis, -1, sizeof(dis));
int n, k;
scanf("%d%d", &n, &k);
for (int i = 0; i<n; i++){
scanf("%s", s);
int now = 0;
for (int j = 0; j < k; j++)
now = now * 2 + s[j] - '0';
que.push(now);
dis[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 (dis[to] != -1)continue;
dis[to] = dis[K] + 1;
que.push(to);
if (ma<dis[to]){
ma = dis[to];
ans = to;
}
}
}
for (int i = k-1; i >=0; i--) {
if (ans&(1 << i))printf("1");
else printf("0");
}
//scanf("%d", &n);
}
本文标签: 思维distinctiveGymBFS多源
版权声明:本文标题:【Gym - 101572Distinctive Character 】【多源bfs+思维】【好题】 内容由热心网友自发贡献,该文观点仅代表作者本人, 转载请联系作者并注明出处:https://www.elefans.com/dongtai/1728870513a1177222.html, 本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如发现本站有涉嫌抄袭侵权/违法违规的内容,一经查实,本站将立刻删除。
发表评论