NCPC2017 Distinctive Character bfs+思维

本文主要是介绍NCPC2017 Distinctive Character bfs+思维，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

7632: Distinctive Character

时间限制: 1 Sec 内存限制: 128 MB Special Judge
提交: 69 解决: 23
[提交] [状态] [讨论版] [命题人:admin]

题目描述

Tira would like to join a multiplayer game with n other players. Each player has a character with some features. There are a total of k features, and each character has some subset of them.
The similarity between two characters A and B is calculated as follows: for each feature f, if both A and B have feature f or if none of them have feature f, the similarity increases by one.
Tira does not have a character yet. She would like to create a new, very original character so that the maximum similarity between Tira’s character and any other character is as low as possible.
Given the characters of the other players, your task is to create a character for Tira that fulfils the above requirement. If there are many possible characters, you can choose any of them.

输入

The ﬁrst line of input contains two integers n and k, where 1 ≤ n ≤ 105 is the number of players (excluding Tira) and 1 ≤ k ≤ 20 is the number of features.
Then follow n lines describing the existing characters. Each of these n lines contains a string of k digits which are either 0 or 1. A 1 in position j means the character has the j’th feature, and a 0 means that it does not have the j’th feature.

输出

Output a single line describing the features of Tira’s character in the same format as in the input.
If there are multiple possible characters with the same smallest maximum similarity, any one of them will be accepted.

样例输入

样例输出

题意：给n个长度为m的字符串，只有0和1，求一个字符串使和其他字符串在相同位置字母相同的总数的最大值最小

思路：记录每个字符串，推进队列中，dis数组记录原字符串改变了几位，第一次访问的一定就是最小的那个，然后在这些里面找

到最大的

代码：

#include <bits/stdc++.h>using namespace std;
const int maxn = 1e5 + 10;
int dis[1 << 21];
queue<int> que;int main() {int n, m;scanf("%d%d", &n, &m);string s;memset(dis, -1, sizeof(dis));for (int i = 0; i < n; i++) {cin >> s;int v = 0;for (int j = 0; j < m; j++) {if (s[j] == '1') {v |= (1 << j);}}que.push(v);dis[v] = 0;}int ans = 0, maxx = 0;while (!que.empty()) {int val = que.front();que.pop();for (int i = 0; i < m; i++) {int neww = val ^(1 << i);if (dis[neww] != -1) continue;que.push(neww);dis[neww] = dis[val] + 1;if (dis[neww] > maxx) {maxx = dis[neww];ans = neww;}}}for (int i = 0; i < m; i++) {if (ans & (1 << i)) cout << "1";else cout << "0";}puts("");return 0;
}

这篇关于NCPC2017 Distinctive Character bfs+思维的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！