admin管理员组文章数量:1622627
题目传送门
题目大意:
给出n个01串,让你构造一个字符串,使这个字符串和这些字符串中相似程度最高 尽可能低。如果两个字符串对应位置相同,则相似程度加一。
思路:
每一个01串更改自己的一部分后,都可以得到任何的01串。我希望所有的字符串最后能变成相同的01串。我们将题意转化一下,使相似程度最高的 尽可能低,也就是使不相似程度最低的 尽可能高,而每一个01串改变一次之后,就相当于不相似程度加一,当bfs第一次经过一个状态后,就得到了这个状态对于所有字符串的最低相似程度(因为其他01串到这个01串的步数肯定更大,就不是最低的了)。所以就是讲原来的所有01串二进制转化成十进制数字,塞进队列,每一步都是改变其中某一位,更新每一个状态的值。由于01串最多有2k个,所以时间复杂度就是2k。
#include<iostream> #include<cstdio> #include<cmath> #include<algorithm> #include<string.h> #include<sstream> #include<set> #include<map> #include<vector> #include<queue> #include<stack> #include<bitset> #define CLR(a,b) memset((a),(b),sizeof((a))) using namespace std; typedef long long ll; inline int rd() { int f = 1; int x = 0; char s = getchar(); while (s<'0' || s>'9') { if (s == '-')f = -1; s = getchar(); } while (s >= '0'&&s <= '9') { x = x * 10 + s - '0'; s = getchar(); }x *= f; return x; } const int maxn = 100010; int vis[(1 << 20)+10],dis[(1<<20)+10]; char s[30]; int main() { int n, k; cin >> n >> k; int tot = (1 << k); queue<int>q; CLR(dis, -1); for (int i = 1; i <= n; i++) { scanf("%s", s); int temp = 0; for (int j = 0; j < strlen(s); j++) { temp = (temp << 1) + s[j] - '0'; } dis[temp] = 0; q.push(temp); } while (!q.empty()) { int st = q.front(); q.pop(); for (int i = 0; i < k; i++) { int now = st ^ (1 << i); if (dis[now] == -1) { dis[now] = dis[st] + 1; q.push(now); } } } int maxx = -1,ans; for (int i = 0; i < tot; i++) { if (dis[i] > maxx) { ans = i; maxx = dis[i]; } } stack<int>s; while (ans > 0) { s.push(ans % 2); ans /= 2; } while (s.size() < k) { s.push(0); } while (s.size()) { printf("%d", s.top()); s.pop(); } }
转载于:https://wwwblogs/mountaink/p/9563956.html
本文标签: 思维GymdistinctiveBFScharacter
版权声明:本文标题:Gym - 101572DDistinctive Character bfs思维 内容由热心网友自发贡献,该文观点仅代表作者本人, 转载请联系作者并注明出处:https://m.elefans.com/dongtai/1728870487a1177219.html, 本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如发现本站有涉嫌抄袭侵权/违法违规的内容,一经查实,本站将立刻删除。
发表评论