快手笔试 快手笔试题 0329
笔试时间：2024年03月29日 备注：第二题太难暂无题解
历史笔试传送门：2023秋招笔试合集
第一题
题目：消灭怪物得最高分
一款2D游戏，你作为玩家可以释放一个技能，从而摧毁所选中的释放位置AABB[W,H]范围内的所有小怪。现在地图上有N(N ≤ 10000)个怪物，用整数Xi,Yi(其值在[0,4000])表示怪物在地图上的位置，以及该怪物被摧毁可获得对应的分数Vi。将作用范围为[W,H]的技能作用在不同位置，可以获得不同的分数值，请设计程序计算最大的分数值Vm。
输入描述
第一行3个正整数为怪物数目N和AABB的长度W、宽度H；
接下来N行每行3个正整数，分别为Xi、Yi、Vi；
输出描述
释放该技能摧毁掉地图上怪物可获得的最大分数。
样例输入一
10 21 21
264 107 123
55 337 226
247 358 376
292 100 198
227 228 215
48 144 195
219 306 183
85 342 265
282 214 363
114 373 286
样例输出一
376
样例输入二
10 20 20
155 161 84
97 193 42
11 5 100
47 105 14
127 196 114
135 81 73
158 142 4
138 36 178
119 46 128
38 200 68
样例输出二
306
参考题解
二位前缀和。套用二维前缀和的模板即可。枚举所有可能的释放技能的位置，使用二位前缀和快速求得区间的值。
C++：[此代码未进行大量数据的测试，仅供参考]
#include <iostream>
#include <vector>
using namespace std;
int max_score(int n, int w, int h, const vector<tuple<int, int, int>>& monsters) {
const int MX = 4005;
vector<vector<int>> pres(MX, vector<int>(MX, 0));
// 填充每个怪物的分数到对应的位置上，并计算前缀和
for (const auto& monster : monsters) {
int x, y, v;
tie(x, y, v) = monster;
pres[x][y] += v;
}
// 计算二维前缀和
for (int i = 1; i < MX; ++i) {
for (int j = 1; j < MX; ++j) {
pres[i][j] += pres[i - 1][j] + pres[i][j - 1] - pres[i - 1][j - 1];
}
}
// 遍历所有可能的技能释放位置，计算可以得到的分数，并保留最大值
int ans = 0;
for (int i = w; i < MX; ++i) {
for (int j = h; i < MX; ++i) {
int score = pres[i][j] - pres[i - w][j] - pres[i][j - h] + pres[i - w][j - h];
ans = max(ans, score);
}
}
return ans;
}
int main() {
int n, w, h;
cin >> n >> w >> h;
vector<tuple<int, int, int>> monsters;
for (int i = 0; i < n; ++i) {
int x, y, v;
cin >> x >> y >> v;
monsters.emplace_back(x, y, v);
}
int max_score_val = max_score(n, w, h, monsters);
cout << max_score_val << endl;
return 0;
}
Java：[此代码未进行大量数据的测试，仅供参考]
import java.util.Scanner;
public class MaxScore {
public static int maxScore(int n, int w, int h, int[][] monsters) {
final int MX = 4005;
int[][] pres = new int[MX][MX];
// 填充每个怪物的分数到对应的位置上，并计算前缀和
for (int[] monster : monsters) {
int x = monster[0], y = monster[1], v = monster[2];
pres[x][y] += v;
}
// 计算二维前缀和
for (int i = 1; i < MX; i++) {
for (int j = 1; j < MX; j++) {
pres[i][j] += pres[i - 1][j] + pres[i][j - 1] - pres[i - 1][j - 1];
}
}
// 遍历所有可能的技能释放位置，计算可以得到的分数，并保留最大值
int ans = 0;
for (int i = w; i < MX; i++) {
for (int j = h; j < MX; j++) {
int score = pres[i][j] - pres[i - w][j] - pres[i][j - h] + pres[i - w][j - h];
ans = Math.max(ans, score);
}
}
return ans;
}
public static void main(String[] args) {
Scanner scanner = new Scanner(System.in);
int n = scanner.nextInt();
int w = scanner.nextInt();
int h = scanner.nextInt();
int[][] monsters = new int[n][3];
for (int i = 0; i < n; i++) {
monsters[i][0] = scanner.nextInt();
monsters[i][1] = scanner.nextInt();
monsters[i][2] = scanner.nextInt();
}
int maxScoreVal = maxScore(n, w, h, monsters);
System.out.println(maxScoreVal);
}
}
Python：[此代码未进行大量数据的测试，仅供参考]
def max_score(n, w, h, monsters):
MX = 4005
pres = [[0] * MX for _ in range(MX)]
# 填充每个怪物的分数到对应的位置上，并计算前缀和
for x, y, v in monsters:
pres[x][y] += v
# 计算二维前缀和
for i in range(1, MX):
for j in range(1, MX):
pres[i][j] += pres[i - 1][j] + pres[i][j - 1] - pres[i - 1][j - 1]
# 遍历所有可能的技能释放位置，计算可以得到的分数，并保留最大值
ans = 0
for i in range(w, MX):
for j in range(h, MX):
# 根据前缀和公式计算当前区域的分数
score = pres[i][j] - pres[i - w][j] - pres[i][j - h] + pres[i - w][j - h]
ans = max(ans, score)
return ans
# 示例输入
n, w, h = map(int, input().split())
monsters = []
for _ in range(n):
x, y, v = map(int, input().split())
monsters.append((x, y, v))
max_score_val = max_score(n, w, h, monsters)
print(max_score_val)
第二题
题目：圆形周长
游戏的UI渲染中，表现为若干矩形区域的多层级覆盖绘制操作。每个UI渲染区域都是一个矩形，并且都是和屏幕边框平行或垂直的。每个渲染的矩形区域也可以部分或全部被其他区域覆盖。所有矩形并集的边界的长度称为周长。
输入描述
第一行输入数组的长度n（n范围在0到5000）
接下来每行输入矩形的左下和右上的坐标点x1,y1,x2,y2
输出描述
当前图形的周长。
样例输入一
20
0 0 20 20
5 5 15 15
8 8 12 12
-5 -5 25 25
30 0 40 20
35 5 45 15
38 8 42 12
25 -5 35 25
0 25 20 35
5 30 15 40
8 33 12 37
-5 20 25 40
30 25 40 35
35 30 45 40
38 33 42 37
25 20 35 40
15 15 25 25
18 18 22 22
10 10 30 30
-10 -10 50 50
样例输出一
240
样例输入二
50
0 0 5 5
5 5 8 8
8 8 12 12
-5 -5 25 25
30 0 40 20
35 5 45 15
38 8 42 12
25 -5 35 25
0 25 20 35
5 30 15 40
8 33 12 37
-5 20 25 40
30 25 40 35
35 30 45 40
38 33 42 37
25 20 35 40
15 15 25 25
18 18 22 22
19 18 30 30
-10 -10 50 50
4 4 6 6
3 3 7 7
6 6 9 9
-3 -3 13 13
15 0 25 10
18 5 22 15
21 8 25 12
10 -5 20 15
0 15 10 25
3 18 7 22
6 21 9 25
-3 10 13 30
15 15 25 25
18 18 22 22
10 1 30 3
-10 -10 -5 -5
-5 -5 55 55
20 29 30 35
23 23 27 27
15 15 35 35
-20 -20 60 60
样例输出二
320
参考题解
C++：[此代码未进行大量数据的测试，仅供参考]
Java：[此代码未进行大量数据的测试，仅供参考]
Python：[此代码未进行大量数据的测试，仅供参考]
第三题
题目：最短区间
有一个含N个整数的序列，对任意给定得M个整数（可能出现重复值）,求一个最短区间，要求该区间包含这M个整数值，并输出该区间长度。
输入描述
第一行输入N
第二行输入N个整数
第三行输入M
第四行输入M个整数
输出描述
输出最短区间的长度。
样例输入
2756
107 691 9538 8452 8463 1802 9306 8789 896 283 4963 8257 6713 7419 6353 2618 8498 9456 370 56 5335 9094 3121 2169 3067 52 7786 2168 637 5982 3438 3138 426 5692 1386 4181 7971 1658 3667 2410 6480 849 8581 5380 1700 7158 188 1753 1491 2321 8818 7729 2706 5969 1210 7933 5455 9887 7324 3561 9936 9104 5219 1829 1184 3199 3795 5680 567 1674 975 6742 25 1707 5402 4317 194 8921 1388 5706 4832 1440 8135 4345 2434 2063 4475 5212 31 8657 8007 3203 5610 367 5424 5181 469 6516 2279 6302 2692 4560 4678 1954 1987 9680 9931 5905 9562 3262 2025 916 4000 9189 5547 6423 2078 2889 9034 6607 2101 9716 2433 4253 3602 9507 2415 147 2225 931 3004 4039 5793 5862 3568 2006 4214 7418 4560 8395 3252 8028 8442 1008 6939 2696 7860 3428 2510 9557 2512 4669 2824 8399 2787 48 7633 788 7749 863 93 2644 1723 1522 1862 2258 9636 809 8251 2944 9569 7441 5257 9434 8489 8933 1289 8306 2539 3927 2378 3244 4037 8511 4129 3722 4676 8563 9198 4075 29 3560 2944 9839 4844 1560 1739 7726 8075 9908 2570 9034 7590 3339 2880 994 5980 5900 6083 3273 9400 6665 9179 6262 5936 5501 1031 2221 526 2415 1409 7598 3822 9959 5507 2684 2823 6064 4041 9073 6653 798 5337 7680 3606 1026 3969 123 6236 6909 2816 5142 3379 7793 5416 2684 4811 6798 9314 1344 647 8859 9618 4118 5199 35 508 2259 5076 9891 696 8707 3570 3232 8882 7322 490 2846 9685 3229 3313 5215 4376 9601 1763 2568 2441 484 8764 9051 3386 4987 4937 2560 794 300 6202 325 9301 4397 2298 9768 4174 4636 8530 1826 2460 2848 6235 8550 4498 3392 2770 2330 3348 4323 2497 1958 3847 7703 1868 8235 4584 4566 6714 1126 4144 4566 373 8388 2934 1376 8610 9832 3029 2164 2740 5611 2255 1130 8414 2531 659 988 6137 9095 4779 6194 341 6034 7609 2446 9699 3047 6707 2410 8882 2964 7724 6478 5528 7273 2149 4694 7716 8858 3588 499 6146 5715 1380 5489 5262 1052 2029 9225 9212 9070 2341 1320 7943 2277 6711 8416 3801 8742 7716 61 6699 7730 2903 1194 2685 3820 1852 2293 1208 3031 8260 7841 194 8755 8178 1227 7362 554 1946 6911 3764 2374 2171 2251 5839 2806 4682 4916 5525 8833 9729 1048 6075 8650 8824 8404 1595 5892 6643 8567 8566 5943 7227 9062 2301 7907 6850 1793 417 7653 5361 5686 5833 1848 7332 7989 6917 9918 6665 4084 1121 5087 100 5348 2508 4657 7943 1699 1817 5145 8048 2659 3317 3057 6755 3562 8618 1834 1290 3692 2484 5300 7770 23 1891 2428 2280 2285 6416 7780 7276 887 2179 8601 4805 2151 2148 6562 6028 6431 576 1492 1757 160 2414 14 3652 9110 2339 225 628 1570 6739 9391 2446 9992 985 1769 9472 2571 7465 7969 2748 357 5188 3191 2282 7099 7964 9810 2160 1855 2136 3101 3153 344 7929 1557 8036 6304 2622 6560 2616 2061 7014 7696 1508 5730 2597 4087 9987 2726 5544 6701 9855 5893 9212 9232 7901 5046 811 4492 427 7293 6729 1931 4549 4466 8750 8143 573 5810 1829 2574 1932 1012 6725 8156 2084 206 7709 9087 1833 4152 4021 7599 384 961 3746 2589 8421 66 2203 3638 2067 2128 8858 3735 5184 5766 9957 9331 2471 6658 4894 6563 8490 7950 1639 590 7383 7522 6042 265 8250 3624 8616 1696 500 4624 2560 2917 8603 5446 7698 9384 2258 1344 8996 9753 1226 8396 7910 2090 6552 7946 1649 2312 825 7157 5413 4987 3924 6312 4355 2140 1103 974 168 1895 1381 8779 5388 3665 9062 921 3513 1276 559 5526 6352 2248 5771 1260 7928 8028 2346 1600 7272 1861 2706 6592 6823 446 1539 3574 7074 257 1951 8642 1870 1277 1978 920 9007 3769 2878 5445 3752 6263 7074 8088 1636 2812 1612 6942 6612 6160 6533 7918 1833 9345 3756 3431 9765 1773 5069 6374 1197 8415 9283 2124 4802 7561 5627 3072 625 5956 2828 4417 2103 8707 9684 2511 7064 2991 8468 2778 3986 5678 799 4491 5214 6085 1599 9602 487 7344 8
剩余60%内容，订阅专栏后可继续查看/也可单篇购买
持续收录字节、腾讯、阿里、美团、美团、拼多多、华为等笔试题解，包含python、C++、Java多种语言版本，持续更新中。
查看3道真题和解析
投递逸仙电商等公司10个岗位