Topic gate
The main idea of the topic is:
Given n n n n 01 strings, let you construct a string so that the strings and the similarity between these strings as low as possible. If the two strings correspond to the same position, the similarity degree is increased by one.
Ideas:
You can get any 01 strings after changing each part of the 01 string. I want all strings to end up in the same 01 string. We will change the meaning of the question to make the highest degree of similarity as low as possible, that is, to make the lowest degree of dissimilarity as high as possible, and each 01 string changeOnce changed, it is equivalent to adding one degree of dissimilarity, and when BFS passes a state for the first time, it gets the lowest degree of similarity for all strings (because the other 01 strings must have a larger number of steps to this 01 string, not the lowest). So it’s about the original 01 string two.The decimal digits are converted into decimal digits, queued, and each step changes one of them, updating the values of each state. Because the 01 string has a maximum of 2.kSo the time complexity is 2.k。
#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(); } }