吉比特2018春招技术类笔试试卷编程题 - 题解

吉比特的编程题倒是不难，但是它的选择题和填空题是真的多。。。

由于没有拍题目，所以我就按照我的记忆来描述一下题目了。

第一题

题目

判断两个数，换成二进制格式，输出多少个位置不一样

解析

这题很基础，取出每一位上的二进制，用异或比较就行了。看代码。

代码

#include <bits/stdc++.h>

using namespace std;

int main()
{
    for (int n1, n2; cin >> n1 >> n2; ) {
        int ans = 0;
        unsigned int n_1 = n1, n_2 = n2;
        for (int i = 0; i < 32; i++) {
            ans += (n_1 & 1) ^ (n_2 & 1);
            n_1 >>= 1;
            n_2 >>= 1;
        }
        cout << ans << endl;
    }
    return 0;
}

第二题

题目

n个三维空间点，判断最多多少个空间点在同一条直线上

解析

这题尽量不要用斜率做，用向量做是最好的，那么问题就转化成了如何判断两个向量共线；

只要两个向量对应系数成比例，那么这两个向量就共线；

由于n达到了2000，那么三层for循环枚举三个点的算法是行不通的，因此，换一种思路，假设两个向量共线，且这两个向量的起点是同一个点，那么这说明三点就共线了；

因此，我们把空间点排序，排序函数：

bool operator<(const Point &other) const {
        if (x != other.x)
            return x < other.x;
        if (y != other.y)
            return y < other.y;
        if (z != other.z)
            return z < other.z;
    }

这样可以保证待会我们以一个点作为起点去构造其他向量的时候能保证向量都在第一卦限；

由于共线向量对应系数成比例，因此，我们直接把共线的向量统一化成最简的形式，即三个分量没有除了1没有其他公约数，这样就可以用一个map来保存最简式，最后求出共线最多的最简式的数量加一就是答案。

时间复杂度：O(n2logn)$O(n^{2}logn)$。

代码

#include <bits/stdc++.h>

using namespace std;

#define gcd __gcd

struct Point {
    int x, y, z;
    Point() {}
    Point(int x, int y, int z) : x(x), y(y), z(z) {}

    bool operator<(const Point &other) const {
        if (x != other.x)
            return x < other.x;
        if (y != other.y)
            return y < other.y;
        if (z != other.z)
            return z < other.z;
    }
};

typedef pair<pair<int, int>, int> Node;

int main()
{
    for (int n; cin >> n; ) {
        vector<Point> points;
        for (int i = 0, x, y, z; i < n; i++)
            cin >> x >> y >> z, points.push_back(Point(x, y, z));
        sort(points.begin(), points.end());

        int ans = 0;
        for (int i = 0; i < n; i++) {
            map<Node, int> mp;
            for (int j = i + 1; j < n; j++) {
                int vx = points[j].x - points[i].x;
                int vy = points[j].y - points[i].y;
                int vz = points[j].z - points[i].z;
                int g = gcd(gcd(vx, vy), vz);
                mp[make_pair(make_pair(vx / g, vy / g), vz / g)]++;
            }
            int sum = 0;
            for (auto it = mp.begin(); it != mp.end(); ++it)
                sum = max(sum, it->second);
            ans = max(sum, ans);
        }
        cout << ans + 1 << endl;
    }
    return 0;
}