腾讯4.26数据分析笔试题题解整理
4.26，腾讯笔试，凉！！！
一同阵亡的牛友们也请节哀顺变！！
说下我的体验吧～～～
全程梦游，死卡第二题，回过头看没想到最后三题才是最简单的，然而我只来得及做第五题了。。
这次是真得被狠狠教训了，在此做个总结吧：做笔试还是要有策略，特别是编程题不要卡题(心态很容易崩)，题目难度不一定是按顺序来的，你都不知道后面是什么题，如果是送分题不得狠狠打脸，拿到题目最好过一下,对题目有一个整体把控，然后由简至易，前面ac顺利就会越做越顺，一旦卡题钻牛角尖就无了
凭记忆整理一份笔试题及题解，若有不对之处请牛友们评论区指正
题目1：打怪游戏，假设玩家初始金币无限，每枚金币可以购买m血量，
有n只怪，打第i只怪消耗血量ci，打死可收益wi枚金币，玩家可以选择打或者不打某只怪，
求玩家在该游戏中可收益的最大金币数(要减去购买血量的金币)
1 <= n <= 1000，1 <= m <= 1e9，1 <= w <= 100，1 <= c <= 1e6
时间复杂度O(n)#include <bits/stdc++.h> using namespace std; typedef long long ll; const int maxn = 1e3; struct ghost { int c; int w; }; ghost gh[maxn]; int main() { int n, m; while (~scanf("%d%d", &n, &m)) { for (int i = 0; i < n; i++) { scanf("%d%d", &gh[i].c, &gh[i].w); } ll energy = 0; int coins = 0; for (int i = 0; i < n; i++) { if (1ll * gh[i].w * m > gh[i].c) { energy += gh[i].c; coins += gh[i].w; } } int ans = coins - energy / m; if (energy % m != 0) ans -= 1; printf("%d\n", ans); } return 0; }题目2：几何题，求y^2 = 2AX和y=Bx+C所围区域面积
1 <= A, B <= 100，-100 <= C <= 100
这题有毒，以后笔试再也不碰几何题了。。。不敢了#include <bits/stdc++.h> using namespace std; int main() { int ca; int a, b, c; scanf("%d", &ca); while (ca--) { scanf("%d%d%d", &a, &b, &c); int root = 4 * a * a - 8 * a * b * c; if (root <= 0) printf("0.0\n"); else if (b == 0) printf("0.0\n"); else { double t = 2 * a - 2 * b * c; double x_max = (t + sqrt(root)) / (2 * b * b), x_min = (t - sqrt(root)) / (2 * b * b); if (a > 0) { double s1 = 2.0 / (6 * a) * (2.0 * a * x_max) * sqrt(2.0 * a * x_max) - 0.5 * (x_max + 1.0 * c / b) * sqrt(2 * a * x_max); if (x_max == x_min) printf("%.10lf\n", 2 * s1); else if (a * -1.0 * c / b >= 0){ double s2 = 2.0 / (6 * a) * (2.0 * a * x_min) * sqrt(2.0 * a * x_min) + 0.5 * (-1.0 * c / b - x_min) * sqrt(2 * a * x_min); printf("%.10lf\n", s1 + s2); } else { double s2 = -2.0 / (6 * a) * (2.0 * a * x_min) * sqrt(2.0 * a * x_min) + 0.5 * (x_min + 1.0 * c / b) * sqrt(2 * a * x_min); printf("%.10lf\n", s1 + s2); } } else { swap(x_max, x_min); double s1 = -2.0 / (6 * a) * (2.0 * a * x_max) * sqrt(2.0 * a * x_max) - 0.5 * (-1.0 * c / b - x_max) * sqrt(2 * a * x_max); if (x_max == x_min) printf("%.10lf\n", 2 * s1); else if (a * -1.0 * c / b >= 0) { double s2 = -2.0 / (6 * a) * (2.0 * a * x_min) * sqrt(2.0 * a * x_min) + 0.5 * (x_min + 1.0 * c / b) * sqrt(2 * a * x_min); printf("%.10lf\n", s1 + s2); } else { double s2 = 2.0 / (6 * a) * (2.0 * a * x_min) * sqrt(2.0 * a * x_min) + 0.5 * (-1.0 * c / b - x_min) * sqrt(2 * a * x_min); printf("%.10lf\n", s1 + s2); } } } } return 0; }题目3：n个房间里各有一个犯人，每个人从m个不同数字中取一个数，若相邻
两个房间的犯人取得数字相同则有矛盾，对产生矛盾的可能数计数
1 <= n <= 1e12，1 <= m <= 1e8
这题应该是最简单的了，求出通项公式然后快速幂，通项公式：，总方案数减去无矛盾方案数
时间复杂度：常数级#include <bits/stdc++.h> using namespace std; typedef long long ll; const int mod = 100003; ll quick_pow(ll v, ll n) { ll ans = 1; while (n > 0) { if (n & 1) ans = ans * v % mod; n >>= 1; v = v * v; } return ans; } int main() { ll n, m; while (~scanf("%lld%lld", &n, &m)) { ll a = quick_pow(m, n - 1); ll b = quick_pow(m - 1, n - 1); printf("%lld\n", m * (a - b + mod) % mod); } return 0; }题目4：若数组x和数组y满足x1+y1=x2+y2=x3+y3..，则称x和y是对子
输入n，k，接着输入n个k长数组，对这n个数组可构成的对子数计数
1 <= n <= 1e6，2 <= k <= 10
这题需要找出对子之间的潜在关系：对于x和y两个数组，若x和y是对子，则有x1+y1=x2+y2=x3+y3...，也就是说数组对应位置元素和都为x1+y1，那么有x和y中元素应满足如下条件
x1, x1 + a, x1 + b...
y1, y1 - a, y1 - b...
因此只需维护每个数组与其第一个位置元素的差构成的数组，若两个数组的差数组互为相反数则构成对子。其中，对于相反数是自己的0构成的差数组要单独处理
时间复杂度O(nklogn)#include <bits/stdc++.h> using namespace std; typedef long long ll; map<vector<int>, int> mp; int main() { int n, k; while (~scanf("%d%d", &n, &k)) { for (int i = 0; i < n; i++) { vector<int> vec(k - 1, 0); int fv, v; scanf("%d", &fv); for (int j = 1; j < k; j++) { scanf("%d", &v); vec[j - 1] = v - pv; } mp[vec]++; } ll ans = 0; vector<int> neg(k - 1, 0); if (mp.find(neg) != mp.end()) { ll cnt = mp[neg]; ans += cnt * (cnt - 1) / 2; mp.erase(neg); } ll pcnt = 0; for (auto it = mp.begin(); it != mp.end(); it++) { for (size_t i = 0; i < it->first.size(); i++) neg[i] = -it->first[i]; if (mp.find(neg) != mp.end()) { ll cnt = mp[neg]; pcnt += cnt * it->second; } } ans += pcnt / 2; printf("%lld\n", ans); } return 0; }题目5：朋友圈，若A和B在同一个圈子，B和C在同一个圈子，则A和C在同一个圈子，求人数最多的圈子中的总人数
输入n对关系(x, y)，其中1 <= n <= 1e5，1 <= x, y <= 1e7
裸的并查集题目，但是这里有一个细节问题，关系者编号到达1e7，而关系数只有1e5，直接建1e7个并查集节点，跑多个测试集时会超时，所以需要对关系者编号进行离散化处理，离散化之后最多2e5个并查集节点，估计这也是很多牛友使用并查集也没有100% ac的问题所在
时间复杂度O(nlogn)#include <bits/stdc++.h> using namespace std; const int MAX_N = 2e5 + 5; int par[MAX_N], cnt[MAX_N]; unordered_map<int ,int> umap; void init(int n){ for(int i = 0;i < n;i++){ par[i] = i; cnt[i] = 1; } } int fd(int x){ if(par[x] == x) return x; else return par[x] = fd(par[x]); }//查找根节点 void disjoint(int x,int y){ if(fd(x) == fd(y)) return; cnt[par[y]] += cnt[par[x]]; par[par[x]] = par[y]; }//合并 int main() { int ca; scanf("%d", &ca); while (ca--) { int n; scanf("%d", &n); int x, y; init(2 * n + 5); umap.clear(); int cntv = 0; for (int i = 0; i < n; i++) { scanf("%d%d", &x, &y); if (umap.find(x) == umap.end()) { ++cntv; umap[x] = cntv; } if (umap.find(y) == umap.end()) { ++cntv; umap[y] = cntv; } disjoint(umap[x], umap[y]); } int ans = 0; for (int i = 1; i <= cntv; i++) { ans = max(ans, cnt[fd(i)]); } printf("%d\n", ans); } return 0; }
