网易互娱笔试 网易互娱笔试题 0518
笔试时间：2025年5月18日 暑期实习
第一题
在网易的《决战！平安京》这款多人在线战术竞技游戏中，式神的技能机制决定其战场表现。
某位式神有一独特技能，释放后进入无敌状态，持续T秒（若i秒释放，[i, i + T) 内无敌）， 无敌状态结束后，技能需C秒冷却才能再次释放。在团战中，式神需在多个时间点释放技能应对攻击和击杀敌人， 但受冷却时间限制，需合理安排技能释放时间，以在无敌状态下击杀尽可能多敌人。
给定无敌状态持续时间T、技能冷却时间C、技能释放时间点列表（可能因冷却限制，某些时间点无法释放）、 以及击杀敌人的时间点列表，计算单次无敌状态下的最大击杀数。
输入描述
输入第一行为整数P，表示有P组独立测试数据。每组数据包括三行： 第一行包含四个整数，分别为无敌状态的持续时间T（1 ≤ T ≤ 1000）、 技能的冷却时间C（1 ≤ C ≤ 1000）、技能释放的时间点列表的长度N（1 ≤ N ≤ 100000）、 以及击杀敌人的时间点列表的长度M（1 ≤ M ≤ 100000）。 第二行包含N个整数，表示技能释放的时间点列表，按升序排列。 第三行包含M个整数，表示击杀敌人的时间点列表，按升序排列。 所有时间点均为非负整数，且不超过10^9。
输出描述
对于每组数据，输出一个整数，表示单次无敌状态下的最大击杀数。
样例输入
1
5 10 2 10
0 15
1 2 3 4 5 6 7 8 9 10
样例输出
4
解释： 无敌持续时间 T=5 秒，冷却时间 C=10 秒。 可选释放时刻为 0 秒和 15 秒；击杀事件发生在时刻 1,2,3,4,5,6,7,8,9,10。 如果在 0 秒 释放，无敌区间为 [0, 5) 秒，能覆盖时刻 1, 2, 3, 4 这 4 次击杀；时刻 5 由于位于区间右端点（不包含）则不算。 释放后技能进入冷却，到 0+5+10=15 秒 才能再次释放——此时击杀列表中已无新的击杀事件。 如果一开始选在 15 秒 释放，无敌区间为 [15, 20)，同样覆盖不到任何击杀。 因此，单次无敌状态能击中的最多击杀数就是 4。
参考题解
利用释放时间和击杀时间均为升序的特点，用双指针在每次合法释放时刻构造一个 [t0, t0+T) 的窗口，快速统计窗口内击杀事件数；同时维护 next_avail 表示技能冷却结束的最早时刻，跳过无法释放的点。整体时间复杂度 O(N+M)，只需一次线性扫描即可完成。
C++：
// C++ 版本
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
int p;
cin >> p;
vector<int> answers(p);
for (int tc = 0; tc < p; tc++) {
ll t, c;
int n, m;
cin >> t >> c >> n >> m;
vector<ll> releases(n), kills(m);
for (int i = 0; i < n; i++) {
cin >> releases[i];
}
for (int i = 0; i < m; i++) {
cin >> kills[i];
}
ll next_avail = 0;
int max_hits = 0;
int left = 0, right = 0;
// kills 已经排好序，releases 也假定输入有序
for (ll t0 : releases) {
if (t0 < next_avail) continue;
next_avail = t0 + t + c;
// 移动 left 到第一个 ≥ t0 的位置
while (left < m && kills[left] < t0) {
left++;
}
// 移动 right 到第一个 ≥ t0 + t 的位置
while (right < m && kills[right] < t0 + t) {
right++;
}
max_hits = max(max_hits, right - left);
}
answers[tc] = max_hits;
}
for (int x : answers) {
cout << x << "\n";
}
return 0;
}
Java：
// Java 版本
import java.io.*;
import java.util.*;
public class Main {
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
int p = Integer.parseInt(br.readLine().trim());
int[] answers = new int[p];
for (int tc = 0; tc < p; tc++) {
StringTokenizer st = new StringTokenizer(br.readLine());
long t = Long.parseLong(st.nextToken());
long c = Long.parseLong(st.nextToken());
int n = Integer.parseInt(st.nextToken());
int m = Integer.parseInt(st.nextToken());
long[] releases = new long[n];
long[] kills = new long[m];
st = new StringTokenizer(br.readLine());
for (int i = 0; i < n; i++) {
releases[i] = Long.parseLong(st.nextToken());
}
st = new StringTokenizer(br.readLine());
for (int i = 0; i < m; i++) {
kills[i] = Long.parseLong(st.nextToken());
}
long nextAvail = 0;
int maxHits = 0;
int left = 0, right = 0;
// 两个数组假定均已按非降序输入
for (long t0 : releases) {
if (t0 < nextAvail) continue;
nextAvail = t0 + t + c;
while (left < m && kills[left] < t0) {
left++;
}
while (right < m && kills[right] < t0 + t) {
right++;
}
maxHits = Math.max(maxHits, right - left);
}
answers[tc] = maxHits;
}
BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
for (int x : answers) {
bw.write(x + "\n");
}
bw.flush();
}
}
Python：
def main():
p = int(input())
res = []
for _ in range(p):
t, c, n, m = map(int, input().split())
releases = list(map(int, input().split()))
kills = list(map(int, input().split()))
next_avail = 0
max_hits = 0
left = right = 0
for t0 in releases:
if t0 < next_avail:
continue
next_avail = t0 + t + c
while left < m and kills[left] < t0:
left += 1
while right < m and kills[right] < t0 + t:
right += 1
hits = right - left
if hits > max_hits:
max_hits = hits
res.append(str(max_hits))
print("\n".join(res))
if __name__ == "__main__":
main()
第二题
小易是游戏开发工程师，开发像素风格游戏，为提升视觉效果，给游戏地形和物体添加精细渲染效果.但现有渲染算法处理三角形区域时边缘有锯齿现象。为解决此问题，采用超采样技术（Supersampling）， 该技术将每个像素划分为多个子区域，在每个子区域中心点采样，根据采样结果决定像素最终颜色。小易需编写算法，统计每个像素中被给定三角形覆盖的采样点情况，用于后续渲染处理。在渲染图像的平面直角坐标系中，给定由顶点A、B、C构成的三角形。每个像素被均匀划分为S×S个子区域，子区域中心点作为采样点，判断是否被三角形覆盖（在三角边上也视为覆盖）。每个像素中被三角形覆盖的采样点数量最少为0（像素完全在三角形外），最多为S²（像素完全在三角形内）。 小易需统计所有像素（共N×M个）中，被该三角形覆盖的采样点数量分布情况。输出1行共S² + 1个整数，第i（i = 0...S²）个整数表示恰好包含i个被三角形覆盖的采样点的像素数量。
输入描述
第一行包含三个整数N、M、S，表示平面尺寸和超采样倍数。其中1 ≤ N, M ≤ 1000，1 ≤ S ≤ 10。
接下来三行，每行两个浮点数，分别表示顶点A、B、C的坐标(x, y)。其中0 ≤ Ax, Bx, Cx ≤ N，0 ≤ Ay, By, Cy ≤ M。
输出描述
输出1行共S² + 1个整数，其中第i（i = 0...S²）个整数表示恰好包含i个被三角形覆盖的采样点的像素数量，相邻整数用空格隔开。
样例输入
3 3 2
0 0
2 0
0 2
样例输出
6 0 0 2 1
参考题解
我们先根据三角形顶点 A→B、B→C、C→A 的向量叉积确定其朝向（顺时针或逆时针），然后对每个像素遍历其 S×S 个子采样点（中心坐标为像素左上角加 (u+0.5)/S、(v+0.5)/S），通过对三条边向量与点向量的叉积判断该采样点是否位于三角形内部（含边界），统计每个像素被三角形覆盖的采样点数量并累加到大小为 S²+1 的直方图中，最终输出即为每种覆盖数的像素个数。整个过程时间复杂度约为 O(N·M·S²)。
C++：
Java：
Python：
import sys def main(): data = sys.stdin.read().split() it = iter(data) width = int(next(it)) height = int(next(it)) S = int(next(it)) ax = float(next(it)); ay = float(next(it)) bx = float(next(it)); by = float(next(it)) cx = float(next(it)); cy = float(next(it)) v_ab_x = bx - ax; v_ab_y = by - ay v_bc_x = cx - bx; v_bc_y = cy - by v_ca_x = ax - cx; v_ca_y = ay - cy orient = v_ab_x * (cy - ay) - v_ab_y * (cx - ax) ccw = orient > 0 eps = 1e-12 max_samples = S * S histogram = [0] * (max_samples + 1) for py in range(height): for px in range(width): cover_count = 0 for sub_row in range(S): sample_y = py + (sub_row + 0.5) / S for sub_col in range(S): sample_x = px + (sub_col + 0.5) / S v_pa_x = sample_x - ax; v_pa_y = sample_y - ay v_pb_x = sample_x - bx; v_pb_y = sample_y - by v_pc_x = sample_x - cx; v_pc_y = sample_y - cy c_ab = v_ab_x * v_pa_y - v_ab_y * v_pa_x c_bc = v_bc_x * v_pb_y - v_bc_y * v_pb_x
剩余60%内容，订阅专栏后可继续查看/也可单篇购买
2025打怪升级记录，大厂笔试合集 C++, Java, Python等多种语言做法集合指南
查看4道真题和解析
美团公司氛围 2508人发布