腾讯20200426笔试(代码已更新完)-总结
笔试一共5道编程题,趁着还热乎,先把记着的记录下来,题目的总体感觉应该是中等,但是加上复杂度的要求,我感觉是挺难的,我写了三道题,本地测试用例都过了,但是跑的时候只过了30,40和0,对没有错,有一道本地测试过了,但是用例为0,简直是天要亡我,感觉像我这种小菜,能写出来已经很累了,看着本地通过,结果百分之0的感觉,真的是~难受~
算了,还是要加紧刷题,争取早日在写出来的基础上优化复杂度,一步一脚印,下面上正题:
1.游戏背包问题
Q:游戏里面一共有n个怪物,杀死第i个怪物需要花费Ci的血量,同时将获得Wi的金币,在一开始,需要用金币买血,当场的血只能管当场,求一场战役最多能获得多少金币。
IN: 第一行 n m(怪物的个数和每个金币能购买的血量) 例1: 3 2 例2:1 2
接下来n行 Ci Wi (花费Ci的血量,获得Wi的金币) 例1:1 1;1 10; 3 1 例2:3 1
OUT: (开局花费1个金币买两滴血,打第一个和第二个怪物) 例1: 10 例2:0(当打怪物的收益比花费低时,可以不选择打怪物)
#include <iostream> using namespace std; #define NUMBER_ANIMAL 1000 int animal_feature[NUMBER_ANIMAL][2]; int main0() { int n, m; // animal number, coin purchasing power cin >> n >> m; int tmp0, tmp1; for (int i = 0; i < n; i++) { cin >> tmp0 >> tmp1; animal_feature[i][0] = tmp0; animal_feature[i][1] = tmp1; } int max_coin_earn = 0; int blood_cost = 0; for (int i = 0; i < n; i++) { tmp0 = animal_feature[i][0]; tmp1 = animal_feature[i][1]; if ((tmp0 < tmp1 * m)) // cost < earn { blood_cost += tmp0; max_coin_earn += tmp1; } } int min_coin_cost = ceil(double(blood_cost) / m); max_coin_earn -= min_coin_cost; cout << max_coin_earn << endl; return 0; }
2.封闭图形的面积
Q:求抛物线Y2=2AX与直线Y=BX+C所围成的封闭图形面积,若不存在则输出0
IN: 第一行:输入的测试组数: 1
接下来n行用例: 1 1 -6
OUT: 面积 :31.24811(具体数字忘了)
#include<iostream> using namespace std; int main() { int num; cin >>num; while (num--) { double a, b, c; cin >> a >> b >> c; double sum = 0; //double sum1 = 0; double deta = 4 * a * (a - 2 * b * c); if (deta <= 0)sum = 0; else { double x1, x2; double deta1 = sqrt(deta); x1 = a / b + 0.5 * deta1 / b; x2 = a / b - 0.5 * deta1 / b; sum = x1 * (x1 * (0.5 * b - x1 / (6 * a)) - c / b) - x2 * (x2 * (0.5 * b - x2 / (6 * a)) - c / b); //sum1 = (0.5 * x1 * x1 / b - c * x1 / b - x1 * x1 * x1 / (6 * a)) - (0.5 * x2 * x2 / b - c * x2 / b - x2 * x2 * x2 / (6 * a)); } cout << sum << endl; } return 0; }第二题代码写出来了,但是不知道哪里有问题,和标准答案一直对不上,结果和手算的差不多,嗯~可能当局者迷,过段时间再来看看好了
十分钟后追加:找到问题了,算deta的时候,把公因子4约了,真的是手残党~
3.监狱数字冲突
Q:n个房间排在一起,编号1~n,每个房间内都有一个人,现在每个人都要选择1~m的数字,若相邻的房间内选择的数字是一样的,就会发生冲突,问发生冲突的情况有多少种
IN:第一行:2 3
OUT: 6((1,1,1) (1,1 2) (1 2 2) (2 1 1) (2 2 1) (2 2 2) )
#include<iostream> #include<algorithm> using namespace std; #define BASE 100003 int main() { int m; long long n; cin >> m >> n; int number_diff = 0; int number_total = 0; int round_diff = 0; int round_total = 0; for (long long int i = 0; i < n; i++) { if (i == 0) { number_diff = m; number_total = m; } else { number_diff *= (m-1); number_total *= m; } if (number_diff > BASE) { round_diff = floor(double(number_diff) / BASE); number_diff -= round_diff * BASE; } if (number_total > BASE) { round_total = floor(double(number_total) / BASE); number_total -= round_total * BASE; } round_diff = 0; round_total = 0; } int number_same; if (number_total >= number_diff) { number_same = number_total - number_diff; } else { number_same = number_total + BASE - number_diff; } cout << number_same << endl; return 0; }
4.完美的数字对
Q:n个物品,每个物品有k个属性,第i个物品的第j的属性用ai,j表示,两个不同的物品i,j若是符合ai,1+aj,1 = ai,2+aj,2=......=ai,k+aj,k,求完美对的个数
IN:第一行:n k (n物品数,k个属性) 5 3
接下来n行:ai,1 ,......,ai,k(i物品的k个属性 )2 11 21;19 10 1;20 11 1;6 15 24;18 27 36
OUT: 3 (1+3,2+4,2+5)
#include<iostream> using namespace std; #define Num 1001 int n, k, num; int str[Num][Num]; int multi[Num]; int total[Num][Num]; int main() { multi[Num] = { 0 }; total[Num][Num] = { 0 }; while (cin >> n) { cin >> k; for (int i = 0; i < n; i++) { for (int j = 0; j < k; j++) { cin >> num; str[i][j] = num; } } for (int i = 0; i < n - 1; i++) { for (int j = i + 1; j < n; j++) { for (int p = 0; p < k; p++) { multi[p] = str[i][p] + str[j][p]; } for (int p = 1; p < k; p++) { if (multi[p] != multi[p - 1]) { total[i][j] = 0; break; } else //else if (multi[p] == multi[p - 1]) { total[i][j] = 1; } } } } int sum = 0; for (int i = 0; i < n; i++) for (int j = 0; j < n; j++) { sum = sum + total[i][j]; } cout << sum << endl; } return 0; }
5.朋友圈人数
Q:现在又107个用户,依次编号,现在有m对关系,每一对关系用一组(x,y)表示,及x,y是属于一个圈子的,若AB在一个圈子,BC在一个圈子,那么ABC就在一个圈子,问最多的一个圈子内有多少个用户。
IN:第一行:T (多少组测试用例) 2
第二行: n (当前用例有多少个关系对)4
接下来n行:x y (关系对) 1 2;3 4;5 6;1 6;
第2+n+1行: n (当前用例有多少个关系对)4
接下来n行:x y (关系对) 1 2;3 4;5 6;7 8;
OUT: 4(第一组结果) 2(第二组结果)
#include<iostream> #include<algorithm> using namespace std; int a[10000001], b[100001]; struct kk { int l, r; }s[100001]; int cmp(int x, int y) { return x > y; } int find(int x) { int r = x, j; while (x != a[x]) x = a[x]; while (r != x) { j = a[r]; a[r] = x; r = j; } return x; } int join(int x, int y) { int fx = find(x); int fy = find(y); if (fx != fy) { a[fy] = a[fx];//fy就是a[fx]的啦 b[a[fx]] += b[fy];// fy的朋友圈也归fx了 return 1; } else return 0; } int main() { int n, i, j, t; while (cin>>n) { int m = 0; if (n == 0) { cout << 1 << endl; continue; } t = 0; int max = 0; memset(b, 0, sizeof(b)); for (i = 1; i <= n; i++)//输入所有朋友圈关系 { cin >> s[i].l >> s[i].r; if (s[i].l > max) max = s[i].l; if (s[i].r > max) max = s[i].r; } for (i = 1; i <= max; i++)// 初始化朋友圈,都只有自己1 { a[i] = i; b[i] = 1; } for (i = 1; i <= n; i++)//是否合并 { join(s[i].l, s[i].r); } for (i = 1; i <= max; i++) { if (b[i] > m)// 找最大朋友圈 { m = b[i]; } } cout << m << endl; } return 0; }
题目大概的意思差不多就是这些,先占个坑,详细的明天再更。
2020.04.27:题目更新了,接下来就是更新代码了~
2020.04.28:代码初版更新完毕~
#腾讯2021暑期实习##腾讯##实习##笔经#