万革始笔试第一题求指点

求问万革始笔试第一题的答案，暴力搜索正确率70%

大概描述是这样：

ID编号是一个K位的0/1字符串，定义两个ID间的距离是不一样的位的数目，例如 01000与10100距离是3.

现在已经有N个ID了，要找一个ID，使得它和已有ID间的最小距离最大，求字典序最小的ID

暴力搜索70%的方法如下，有什么别的思路么？求大佬指点~

#include <iostream>
#include <string>
#include <vector>
#include <cmath>

using namespace std;

int distance(string s1, string s2)
{
    int cnt = 0;
    for (int i = 0; i < s1.size(); ++i)
    {
        if (s1[i] != s2[i])
            cnt++;
    }
    return cnt;
}

int main()
{
    int n, k;
    cin >> n >> k;

    vector<string> s;
    for (int i = 0; i < n; ++i)
    {
        string x;
        cin >> x;
        s.push_back(x);

    }

    string res;
    int best = 0;

    for (int i = 0; i < pow(2,k); ++i)
    {
        string t;

        for (int j = 0; j < k; ++j)
        {
            if (i >> j & 0x1)
            {
                t = '1' + t;
            }
            else
                t = '0' + t;
        }

        int mini = INT_MAX;
        for (int j = 0; j < n; ++j)
        {
            int r = distance(t, s[j]);
            if ( r < mini )
            {
                mini = r;
            }
            if (r < best)
                break;
        }

        if (mini > best)
        {
            best = mini;
            res = t;
        }

    }
    cout << res << endl;
    return 0;
}

#万革始##笔试题目#

全部评论

推荐最新楼层

如意FRY

北京科技大学 Java

汉明距离

点赞回复分享

发布于 2018-09-15 22:40

ToDayLee

楼主

北京航空航天大学 C++

顶一顶，继续求大佬指点

点赞回复分享

发布于 2018-09-15 23:57

Why201808312259832

西南交通大学 Java

是超时了还是怎么回事

点赞回复分享

发布于 2018-09-16 00:11

牛客185544

门头沟学院

同做法，同超时

点赞回复分享

发布于 2018-09-16 09:27

尽梨了

北京邮电大学 C++

n和k的数据范围多大？

点赞回复分享

发布于 2018-09-16 09:54

悠乐橙

字节跳动_互娱研发_后台开发

第二题怎么做

点赞回复分享

发布于 2018-09-20 20:50

系统故障

中国音乐学院 C++

求会的大佬指点

点赞回复分享

发布于 2018-09-20 20:53

ToDayLee

楼主

北京航空航天大学 C++

第二题答案，可能不是最终答案，但整体思路没动过 #include <iostream> #include <vector> #include <unordered_map> #include <cmath> #define LL long long using namespace std; int main() { int n; cin >> n; vector<unordered_map<int,int>> t(9, unordered_map<int,int>()); vector<int> nums; for (int i = 0; i < n; ++i) { LL x; cin >> x; nums.push_back(x); LL base = 10; for (int j = 0; j < 9; ++j) { t[j][int((LL)(x)*(LL)(base) % (LL)(7))]++; base *= 10; } } int cnt = 0; for (int i = 0; i < n; ++i) { int base = 0; int x = nums[i]; do { base++; x /= 10; } while (x > 0); int remain = (7 - nums[i] % 7) % 7; if (t[base-1][remain] >= 2) if (((LL)(nums[i]) * (LL)(pow(10, base))) % 7 == remain) { cnt += t[base - 1][remain] - 1; } else cnt += t[base - 1][remain]; else if (t[base-1][remain] < 1) continue; else { if (((LL)(nums[i]) * (LL)(pow(10, base))) % 7 == remain) { continue; } else cnt++; } } cout << cnt << endl; return 0; }

点赞回复分享

发布于 2018-09-20 21:23