Gym - 101572D Distinctive Character bfs 思维

题目传送门

题目大意：

给出n个01串，让你构造一个字符串，使这个字符串和这些字符串中相似程度最高 尽可能低。如果两个字符串对应位置相同，则相似程度加一。

思路：

每一个01串更改自己的一部分后，都可以得到任何的01串。我希望所有的字符串最后能变成相同的01串。我们将题意转化一下，使相似程度最高的  尽可能低，也就是使不相似程度最低的 尽可能高，而每一个01串改变一次之后，就相当于不相似程度加一，当bfs第一次经过一个状态后，就得到了这个状态对于所有字符串的最低相似程度（因为其他01串到这个01串的步数肯定更大，就不是最低的了）。所以就是讲原来的所有01串二进制转化成十进制数字，塞进队列，每一步都是改变其中某一位，更新每一个状态的值。由于01串最多有2个，所以时间复杂度就是2。

#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 = ; int x = ; char s = getchar();

    while (s<'' || s>'') { if (s == '-')f = -; s = getchar(); }

    while (s >= ''&&s <= '') { x = x *  + s - ''; s = getchar(); }x *= f;

    return x;

}

const int maxn = ;

int  vis[( << )+],dis[(<<)+];

char s[];

int main() {

    int n, k;

    cin >> n >> k;

    int tot = ( << k);

    queue<int>q;

    CLR(dis, -);

    for (int i = ; i <= n; i++)

    {

        scanf("%s", s);

        int temp = ;

        for (int j = ; j < strlen(s); j++)

        {

            temp = (temp << ) + s[j] - '';

        }

        dis[temp] = ;

        q.push(temp);

    }

    while (!q.empty()) {

        int st = q.front();

        q.pop();

        for (int i = ; i < k; i++)

        {

            int now = st ^ ( << i);

            if (dis[now] == -)

            {

                dis[now] = dis[st] + ;

                q.push(now);

            }

        }

    }

    int maxx = -,ans;

    for (int i = ; i < tot; i++)

    {

        if (dis[i] > maxx) {

            ans = i;

            maxx = dis[i];

        }

    }

    stack<int>s;

    while (ans > ) {

        s.push(ans % );

        ans /= ;

    }

    while (s.size() < k) {

        s.push();

    }

    while (s.size()) {

        printf("%d", s.top());

        s.pop();

    }

}