腾讯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暑期实习##腾讯##实习##笔经#
「端到端耗时缩减30-40%」要给出确切数字和绝对值。从1000ms降到600ms是降了40%，从100ms降到60ms也是降了40%，但这两个含义完全不一样。其他也是，涉及到数据，准备好证据，口径统一，面试会问
「熟练」「熟悉」「了解」混在一起用，读起来很乱。而且「了解前端需求」最好改成「具备前后端协作经验」
查看9道真题和解析