admin管理员组

文章数量:1622541

Step1 Problem:

给你n行，k位的 只包含’0’,’1’的字符串。
输出一个只包含’0’,’1’的字符串，和这些源串各个位不同个数最少的串要求各个位不同个数尽可能的多（多个解输出任意一个即可）
数据范围：
1<=n<=1e5, 1<=k<=20

Step2 Involving algorithms:

BFS && 状态压缩

Step3 Ideas:

01001 只改变一个不一样得到的结果有
11001，00001，01101，01011，01000
我们以输入串为源点，向外bfs，最远的即是结果。

Step4 Code:

#include<bits/stdc++.h>
using namespace std;
const int N = 1e6+1e5;
int dist[N];
char s[25];
int main()
{
    int n, k;
    while(~scanf("%d %d", &n, &k))
    {
        memset(dist, -1, sizeof(dist));
        queue<int> q;
        for(int i = 0; i < n; i++)
        {
            scanf("%s", s);
            int u = 0;
            for(int j = 0; j < k; j++)
            {
                if(s[j] == '1') u = u|(1<<j);
            }
            q.push(u);
            dist[u]= 0;
        }
        int Max = 0, ans;
        while(!q.empty())
        {
            int u = q.front(); q.pop();
            for(int i = 0; i < k; i++)
            {
                int v = u^(1<<i);
                if(dist[v] == -1) {
                    dist[v] = dist[u] + 1;
                    q.push(v);
                    if(dist[v] > Max) {
                        Max = dist[v];
                        ans = v;
                    }
                }
            }
        }
        //printf("%d\n", ans);
        for(int i = 0; i < k; i++)
        {
            if(ans & (1<<i)) printf("1");
            else printf("0");
        }
        printf("\n");
    }
    return 0;
}

本文标签： 状态ampBFSGymcharacter

版权声明：本文标题：【BFS &amp;&amp; 状态压缩】Gym - 101572D Distinctive Character 内容由热心网友自发贡献，该文观点仅代表作者本人， 转载请联系作者并注明出处：https://m.elefans.com/dianzi/1728870744a1177247.html， 本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如发现本站有涉嫌抄袭侵权/违法违规的内容，一经查实，本站将立刻删除。