admin管理员组文章数量:1622635
题意:输入n个长度为m的字符串(n<1e5,m<20),规定两个字符串相似值为两个字符串相同的个数,找一个串,使得该串与其他串的最大特征值要最小
题解:两个字符串有n个不同那么他们距离就为n,以这n个字符串开始,第一层到这n个字符串相似值最小值最大为1,同理。。要找到最大的,只要找到最后一层就可以,以这n个为起点,BFS遍历整个图最后的那个点就是最远的
#include <bits/stdc++.h> #define maxn 2001000 #define INF 0x3f3f3f3f typedef long long ll; using namespace std; char s[maxn]; int a[maxn], n, m, dir[maxn], t; queue<int>q; int main(){ scanf("%d%d", &n, &m); for(int i=0;i<n;i++){ scanf("%s", s); t = 0; for(int j=0;j<m;j++) t = t*2+s[j]-'0'; q.push(t); dir[t] = 1; } for(int i=0;i<m;i++) a[i] = (1<<i); while(!q.empty()){ t = q.front(); q.pop(); for(int i=0;i<m;i++){ int temp = a[i]^t; if(dir[temp] == 0){ q.push(temp); dir[temp] = 1; } } } for(int i=m-1;i>=0;i--){ if((t>>i)&1) printf("1"); else printf("0"); } printf("\n"); return 0; }
转载于:https://wwwblogs/Noevon/p/8366452.html
本文标签: gym101572Ddistinctivecharacter
版权声明:本文标题:gym101572D Distinctive Character 内容由热心网友自发贡献,该文观点仅代表作者本人, 转载请联系作者并注明出处:https://www.elefans.com/dianzi/1728870493a1177220.html, 本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如发现本站有涉嫌抄袭侵权/违法违规的内容,一经查实,本站将立刻删除。
发表评论