admin管理员组文章数量:1622542
https://vjudge/problem/1131041/origin
题意:给定n个串,由01构成的串,
定义距离, 如果有两个串当只有1位不同时,定义距离为1, 2位不同为2。。。
问你 输出一个串,这个串与 n个串的 最大相似度尽可能的小。
想法:
异或操作也没想到。这样算路径很方便。
改动一个dis+1
#include <iostream>
#include <bits/stdc++.h>
using namespace std;
/* 思路是广搜,完全没有想到。
发现这道题的解空间 就在 0-pow(2,n)中。
而从很多地方一起 bfs的话,先到达的必然是最小的
(每次更新一个操作,算作距离)
并且这是多源 bfs,是从很多点bfs。
最后得到的结果肯定是 最长的。
*/
queue<int>q;
char a[300];
int dis[(1<<21)];
int main()
{ int m,n;
memset(dis,-1,sizeof(dis));
scanf("%d%d",&m,&n);
for(int i=0;i<m;i++){
scanf(" %s",a);
int num=0;
for(int j=0;j<n;j++){
if(a[j]=='1')
num|=(1<<j);
}
//cout<<num<<endl;
q.push(num);
dis[num]=0;
}
int rel;
while(!q.empty()){
int u=q.front();
q.pop();
for(int i=0;i<n;i++){
int ans=u^(1<<i);
if(dis[ans]!=-1) continue;
dis[ans]=dis[u]+1;
rel=ans;
q.push(rel);
}
}
//cout<<rel<<endl;
for(int i=0;i<n;i++){
if(i==0){
if((rel&(1<<i)))
printf("1");
else
printf("0");
}
else{
if((rel&(1<<i)))
printf("1");
else
printf("0");
}
}
printf("\n");
return 0;
}`这里写代码片`
第一次知道这样写,其实我是蒙蔽的,不过后来就还好。
本文标签: 多源GymcharacterdistinctiveBFS
版权声明:本文标题:Gym 101572 D- 多源bfs- Distinctive Character 内容由热心网友自发贡献,该文观点仅代表作者本人, 转载请联系作者并注明出处:https://www.elefans.com/dongtai/1728870738a1177246.html, 本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如发现本站有涉嫌抄袭侵权/违法违规的内容,一经查实,本站将立刻删除。
发表评论