4.26腾讯算法岗笔试总结
第一题
没写出来太丢脸了,题目写了背包两个字,然后我就死活在01背包里面出不来了。脑子一团乱果断下一题。
其实第一题只要看每个怪的收益是否能弥补体力损失就行了,能就打,不能就不打。
0分
第二题
求抛物线y2=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; }
AC
第三题
n个人排排坐,每个人说1-m中的一个数,如果相邻两个人说一样的数就冲突。求冲突的种类数。
数据范围比较大。
纯数学题。
推公式推出来答案是 mn-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; }
AC
这题我还挺有把握,没想到怎么交都是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; }
AC