admin管理员组文章数量:1622542
题目
题意: 给你n个长度都为k的01串(n<=1e5 k<=20) 让你输出一个长度为k的 与所有串最大相同值最小的 一个01串。
这不就是求与所有串差异值最小最大的那个串。就可以多源多终点bfs了。因为是差异值最小，所以vis过可以弹出嘻嘻嘻。有一个差异值相当于多走了一步。这样队列里最多2^ k个串，不会爆的，只会入队这个操作进行2^k次，不会T的。
#include<bits/stdc++.h>
using namespace std;
const int N=2e6+5,INF=20;
using namespace std;
struct node{int sta,step;};
queue<node>q;int ans[N],vis[N],n,k;
char s[25];int r[25];
inline void bfs(){
while(!q.empty()){
node cur=q.front();q.pop();
for(int i=1,nexsta;i<=k;++i){
nexsta=cur.sta+r[i]*(((cur.sta>>(i-1))&1)?(-1):(1));
if(vis[nexsta]) continue;
q.push((node){nexsta,cur.step+1}),vis[nexsta]=1,ans[nexsta]=cur.step+1;
}
}
}
int main(){
scanf("%d%d",&n,&k);r[1]=1;
for(int i=2;i<=k;++i) r[i]=r[i-1]*2;
int t=pow(2,k);//t个终点
for(int i=0;i<=t-1;++i) ans[i]=INF;
for(int i=1;i<=n;++i){
scanf("%s",s+1);int res=0;//注意res放for(i:1-n)里面res=0要保证每次都初始化
for(int i=k,j=1;i>=1;--i,++j){
if(s[i]-'0') res+=r[j];
}
q.push((node){res,0}),vis[res]=1,ans[res]=0;
}
bfs();
int dex,mx=0;
for(int i=0;i<=t-1;++i)
if(ans[i]>mx) dex=i,mx=ans[i];
for(int i=k-1;i>=0;--i) printf(((dex>>i)&1)?"1":"0");
}
本文标签： characterdistinctiveBFS多源
版权声明：本文标题：Distinctive Character(多源bfs) 内容由热心网友自发贡献，该文观点仅代表作者本人， 转载请联系作者并注明出处：https://m.elefans.com/dianzi/1728870624a1177235.html， 本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如发现本站有涉嫌抄袭侵权/违法违规的内容，一经查实，本站将立刻删除。
发表评论