腾讯历年秋招笔试真题

如需获取完整资料，请点击下方链接领取《2024校招笔试真题秘籍》（实时更新中）

不收费，3人组团即可一块免费领取！限量免费10000个名额

手机端点击免费领取：https://www.nowcoder.com/link/campus_xzbs2

电脑端请扫码领取：

1、小Q爬塔

【题目描述】小Q正在攀登一座宝塔，这座宝塔很特别，塔总共有n层，但是每两层之间的净高却不相同，所以造成了小Q爬过每层的时间也不同。如果某一层的高度为x，那么爬过这一层所需的时间也是x。

小Q还会使用一种魔法,每用一次可以让他向上跳一层或两层,但是每次跳跃后小Q都将用完魔法力,必须爬过至少一层才能再次跳跃(你可以认为小Q需要跳两次一层才休息，最后也可以跳到塔外即超过塔高，跳是不消耗时间的)。

小Q想用最短的时间爬到塔顶,希望你能告诉他最短时间是多少.

输入描述:

第一行一个数n (n<=10000),表示塔的层数.

接下来的n行每行一个数h(1 <= h <=100),表示从下往上每层的高度.

输出描述:

一个数,表示最短时间

输入样例：

5

3

5

1

8

4

输出样例：

1

【解题思路】

p[i]表示到达第i层的最短时间，并且到达第i层的方式是爬。

t[i]表示到达第i层的最短时间，并且到达第i层的方式是跳。

到达第i层的方式采用爬还是采用跳。

情况1.到达第i层的方式是爬：

那么到达第i-1层的方式可以使爬也可以是跳，从两者中选最小。

p[i]=min{p[i-1],t[i-1]}+a[i]

情况2.到达第i层的方式是跳：

那么可以从第i-1层起跳，也可以从第i-2层起跳。并且到达第i-1层和i-2层的方式只能选爬（到第i层是跳），所以在两者中选最小。

t[i]=min{p[i-1],p[i-2]}

最后在p[n]和t[n]中选最小者做结果

【参考代码】

#include <bits/stdc++.h>
using namespace std;
int p[10005], t[10005];
int main() {
	int n, m, x;
	cin >> n;
	for(int i = 1; i <= n; i++) {
		cin >> x;
		p[i] = min(p[i - 1], t[i - 1]) + x;
		if(i == 1) continue;
		t[i] = min(p[i - 1], p[i - 2]);
	}
	cout << min(p[n], t[n]) << endl;
	return 0;
}

2、妞妞的问题

【题目描述】妞妞公主新得到了一块黑白棋盘。这块棋盘共有n行m列，任意相邻的两个格子都是不同的颜色（黑或白），坐标为(1,1)的格子是白色的。

这一天牛牛来看妞妞公主时，妞妞公主正望着这块棋盘发呆。牛牛看妞妞公主闷闷不乐的样子，便对妞妞公主说：“只要你告诉我n和m，我能马上算出黑色方块和白色方块的数量。”

“这太简单了。”妞妞公主想了一会儿，“我会在这n行m列中选择一个左下角坐标为(x0,y0)。右上角坐标为（x1,y1）的矩形，把这个矩形里的共（x1-x0+1）*(y1-y0+1)个方块全部涂白。你还能马上算出黑色方块和白色方块的数量吗？”

“这太简单了。”牛牛自信一笑，“你可以在执行涂白操作后再选一个左下角坐标为（x2,y2），右上角坐标为(x3,y3)的矩形，把这个矩形里的方块全部涂黑。我依然能马上算出黑色方块和白色方块的数量。”

妞妞公主终于惊讶地睁大了眼，于是抛出了她的T次提问。

聪明的牛牛当然会做了，但是他想把这个问题交给你，请帮牛牛算出每次提问棋盘的黑白方块数目吧。

输入描述:

第一行一个整数T，表示妞妞公主一共提问了T次。

接下来3*T行，

第（1+3*i）行两个整数n，m。表示第i次提问时棋盘的大小；

第（2+3*i）行四个整数x0，y0，x1，y1。表示第i次提问时涂白操作选取的两个坐标。

第（3+3*i）行四个整数x2，y2，x3，y3。表示第i次提问时涂黑操作选取的两个坐标。

1<=T<=10000，1<=x<=n<=1000000000，1<=y<=m<=1000000000，x0<=x1，y0<=y1，x2<=x3，y2<=y3。

输出描述:

共T行，每行两个整数分别表示白色方块的数量和黑色方块的数量。

输入样例：

3

1 3

1 1 1 3

1 1 1 3

3 3

1 1 2 3

2 1 3 3

3 4

2 1 2 4

1 2 3 3

输出样例：

0 3

3 6

4 8

【解题思路】

格子的个数可以快速维护，然后对应维护出来即可。

【参考代码】

#include <bits/stdc++.h>
using namespace std;
long long x[8], y[8];
int main() {
	int T;
	long long n, m, black, white, a, b, c, d, e;
	scanf("%d", &T);
	while(T--) {
		scanf("%lld%lld", &n, &m);
		black = n * m / 2;
		white = n * m - black;
		for(int i = 0; i <= 3; i++)
			scanf("%lld%lld", &x[i], &y[i]);
		if((x[0] + y[0]) & 1)
			d = ((x[1] - x[0] + 1) * (y[1] - y[0] + 1) + 1) / 2;
		else d = (x[1] - x[0] + 1) * (y[1] - y[0] + 1) / 2;
		white += d;
		black -= d;
		if((x[2] + y[2]) & 1)
			d = (x[3] - x[2] + 1) * (y[3] - y[2] + 1) / 2;
		else d = ((x[3] - x[2] + 1) * (y[3] - y[2] + 1) + 1) / 2;
		white -= d;
		black += d;
		a = max(x[0], x[2]);
		b = max(y[0], y[2]);
		c = min(x[1], x[3]);
		d = min(y[1], y[3]);
		if(c < a || d < b) e = 0LL;
		else{
			if((a + b) & 1)
				e = ((c - a + 1) * (d - b + 1) + 1) / 2;
			else e = (c - a + 1) * (d - b + 1) / 2;
		}
		white -= e;
		black += e;
		printf("%lld %lld\n", white, black);
	}
	return 0;
}

3、小Q的最小值序列

【题目描述】小Q得到了一个长度为 n 的序列 A，A中的数各不相同。对于A中的每一个数 Ai，求：min(1≤j<i)|Ai−Aj|

以及令上式取到最小值的 j（记为 P_i）。若最小值点不唯一，则选择使 Aj 较小的那个。

输入描述:

第一行一个整数n，第二行n个数。

输出描述:

n-1行，每行2个用空格隔开的整数。分别表示当i取2~n时，对应的min(1≤j<i)|Ai−Aj|和Pi的值

输入样例：

3

1 5 3

输出样例：

4 1

2 1

【解题思路】

维护一个单调的链表，边读边算边输出，这样每一个数进来时，都能保证链表里的数下标比它小，那么插入后用它两边的数计算答案即可

【参考代码】

#include <bits/stdc++.h>
using namespace std;
const int N = 1e5 + 5;
const int inf = 1e9;

struct P {
	int value;
	int pos;
};
P a[N];
int cmp(P x, P y) {
	return x.value < y.value;
}
int b[N], b2[N]