4.26腾讯算法岗笔试总结

第一题

没写出来太丢脸了，题目写了背包两个字，然后我就死活在01背包里面出不来了。脑子一团乱果断下一题。

其实第一题只要看每个怪的收益是否能弥补体力损失就行了，能就打，不能就不打。

0分

第二题

求抛物线y²=ax和直线y=bx+c围成的面积。直接积分推公式。

#include <iostream>
#include <cmath>
using namespace std;

int main() {
    int t;
    cin >> t;
    while (t--) {
        double a, b, c;
        cin >> a >> b >> c;
        double delta = 4 * a * (a - 2 * b * c);
        if (delta <= 0) {
            cout << 0 << endl;
        } else {
            double diff = sqrt(delta) / b;
            double sum = (2 * a - 2 * b * c) / b + 2 * c;
            double prod = 2 * c * c + 2 * c * (a - b * c) / b;
            double area = (-1.0 / 6.0 / a) * diff * (sum * sum - prod) + (1.0 / 2 / b) * sum * diff - c / b * diff;
            printf("%.7f\n", area);
        }
    }
    return 0;
}

第三题

n个人排排坐，每个人说1-m中的一个数，如果相邻两个人说一样的数就冲突。求冲突的种类数。

数据范围比较大。

纯数学题。

推公式推出来答案是 mⁿ-m*(m-1)^n-1 写一个快速幂就行。

#include <iostream>
using namespace std;

const long long M = 100003;

long long pow(long long a, long long b) {
    if (b == 0) return 1;
    long long k = pow(a, b / 2);
    long long ans = (k * k) % M;
    if (b % 2 == 1) {
        ans = (ans * a) % M;
    }
    return ans;
}

int main() {
    long long m, n;
    cin >> m >> n;
    cout << ((pow(m, n) - m * pow(m-1, n-1)) % M + M) % M;
    return 0;
}

第四题

这题我还挺有把握，没想到怎么交都是0分，讲一下思路。

注意到ai很小最多100，所以我们先排序，然后对每一种和（2~200），双指针O(N)求解。

（好像哈希表更简单）

0分

第五题

裸并查集，不用按秩合并也能过。

#include <iostream>
using namespace std;


const int N = 10000000;
int f[N+1], k[N+1];

int find(int x) {
    if (f[x] == x) return x;
    return f[x] = find(f[x]);
}

int main() {
    int t;
    cin >> t;
    while (t--) {
        int n;
        cin >> n;
        for (int i = 1; i <= N; ++i) f[i] = i, k[i] = 0;
        for (int i = 1; i <= n; ++i) {
            int x, y;
            cin >> x >> y;
            int xx = find(x), yy = find(y);
            f[xx] = yy;
        }
        for (int i = 1; i <= N; ++i) {
            k[find(i)]++;
        }
        int ans = 0;
        for(int i = 1; i <= N; ++i) {
            ans = max(ans, k[i]);
        }
        cout << ans << endl;
    }

    return 0;
}

#腾讯2021届暑期实习正式批笔试##笔试题目##腾讯#