Codeforces 101572 D - Distinctive Character

D - Distinctive Character

思路：bfs

使最大的匹配数最小，转换一下，就是使最小的不匹配数最大，用bfs找最大的距离

代码：

#pragma GCC optimize(2)
#pragma GCC optimize(3)
#pragma GCC optimize(4)
#include<bits/stdc++.h>
using namespace std;
#define fi first
#define se second
#define pi acos(-1.0)
#define LL long long
//#define mp make_pair
#define pb push_back
#define ls rt<<1, l, m
#define rs rt<<1|1, m+1, r
#define ULL unsigned LL
#define pll pair<LL, LL>
#define pii pair<int, int>
#define piii pair<pii, int>
#define mem(a, b) memset(a, b, sizeof(a))
#define fio ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);
#define fopen freopen("in.txt", "r", stdin);freopen("out.txt", "w", stout);
//head

const int N = 1e5 + 5;
queue<int> q;
int dis[N*15];
int main() {
    fio;
    int n, k, ans;
    string s;
    cin >> n >> k;
    mem(dis, -1);
    for (int i = 1; i <= n; i++) {
        cin >> s;
        int now = 0;
        for (int j = 0; j < k; j++) if(s[j] == '1') now |= 1<<j;
        q.push(now);
        dis[now] = 0;
        ans = now;
    }
    int mx = 0;
    while(!q.empty()) {
        int now = q.front();
        q.pop();
        for (int i = 0; i < k; i++) {
            int nxt = now^(1<<i);
            if(dis[nxt] == -1) {
                dis[nxt] = dis[now] + 1;
                q.push(nxt);
                if(dis[nxt] > mx) {
                    mx = dis[nxt];
                    ans = nxt;
                }
            }
        }
    }
    for (int i = 0; i < k; i++) {
        if(ans & (1<<i)) cout << 1;
        else cout << 0;
    }
    cout << endl;
    return 0;
}