admin管理员组文章数量:1622638
(好巧妙的题,根本不会转化。。。
题目大意:给n个01串,构造一个01串使得与其他串的相似度最大值最小。
思路:bfs
相似度最大值最小,也就是说不匹配度最小值要最大,对于001来说,011、101、000与它的距离为1,我们把所有原串作为起点,然后同时放进队列跑最短路,跑过的01串就直接跳了,因为它肯定与之前某原01串的不匹配度是最小的,跑出来最远的01串,就是不匹配度值最大,此时它的dis表示与某个01串的最近距离,即不匹配最小值最大了。
主要注意一下这个bfs是多个起点就好理解了,巧妙枚举了所有串,所以复杂度为O(2^k)
#include <cmath>
#include <cstring>
#include <algorithm>
#include <map>
#include <list>
#include <queue>
#include <vector>
#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <deque>
using namespace std;
typedef long long ll;
#define _for(i,a,b) for(int i=(a) ;i<=(b) ;i++)
#define _rep(i,a,b) for(int i=(a) ;i>=(b) ;i--)
#define scd(v) scanf("%d",&v)
#define scdd(a,b) scanf("%d %d",&a,&b)
#define endl "\n"
#define IOS ios::sync_with_stdio(false)
#define pb push_back
#define all(v) v.begin(),v.end()
#define int long long
#define odd(x) x&1
#define mst(v,a) memset(v,a,sizeof(v))
#define all(v) v.begin(),v.end()
#define lson p<<1 ,l,mid
#define rson p<<1|1,mid+1,r
#define ls p<<1
#define rs p<<1|1
const int N=1e5+10;
int n,k;
int ans;
int dis[1<<21];
queue <int > q;
signed main()
{
//!!
// freopen("data.txt","r",stdin);
//!!
IOS;
mst(dis,-1);
int mx=-1;
cin>>n>>k;
_for(i,1,n)
{
char s[100];
cin>>(s+1);
int temp=0;
_for(j,1,k)
{
temp = (temp<<1) + s[j]-'0';
}
q.push(temp);
dis[temp]=0;
}
while(!q.empty())
{
int x = q.front();
q.pop();
for(int i=0 ;i<k ;i++)
{
int y = x^(1<<i);
if( dis[y]!=-1) continue;//访问过的跳过
dis[y] = dis[x] + 1;
q.push(y);
if( dis[y] > mx )
{
mx = dis[y];
ans = y;
}
}
}
_rep(i,k-1,0)
{
cout<<( (ans>>i)&1 );
}
}
本文标签: Gymcharacterdistinctive
版权声明:本文标题:Gym 101572 D Distinctive Character 内容由热心网友自发贡献,该文观点仅代表作者本人, 转载请联系作者并注明出处:https://www.elefans.com/dianzi/1728870572a1177229.html, 本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如发现本站有涉嫌抄袭侵权/违法违规的内容,一经查实,本站将立刻删除。
发表评论