Coming soon: English version of this article in progress
2024年3月17日10:00-12:00，米哈游春招/暑期实习笔试。
总限时两小时，各个题型没有分别的限时，可以随时修改。
10道单选（20分），10道不定项选择（20分），3道编程题（60分）。
选择题均为计算机基础相关（408、数据库、Linux)
编程题使用ACM模式，即需要自己处理输入输出。语言不限，可以用本地IDE。
Note: 我的思路及解法较为笨拙，且不敢保证正确性。抛砖引玉，敬请指正。
单项选择题
共10道，每道2分，共20分。
- 二叉树遍历顺序
- 信号量上限下限
- 栈&队列
- 图 邻接矩阵
- 进程 就绪队列
- IP地址 掩码
- SQL语句 SELECT
- SQL语句 INSERT JOIN
- IP 地址 等长子网划分
- TCP 报文 序号
不定项选择题
共10道，每道2分，共20分。
- C++ 类中的 static 成员变量
- KMP 空间复杂度
- 上三角矩阵 空间利用
- Linux 启动项判断
- /etc/rc.local
- /root/.bashrc
- lilo grub
- /etc/rc.d/rc*.d
- Linux 文件系统 inode (index node) 携带的信息 文件后缀名
- 信号量
- 最坏时间复杂度为
O(n)查找算法 - 进程调度触发条件 非抢占式
- TCP 协议提供的服务
- 同步传输/异步传输的区别
编程题
共3道，每道20分，共60分。
Q1 转圈圈
时间限制：3000 MS
内存限制：589824 KB
题目描述
黑塔是一个喜欢转圈圈的女孩子。
有一天，黑塔遇到了n个怪物，第i个怪物的生命值为h_i。
由于被守护者之影禁用了普通攻击，黑塔现在只能使用E技能攻击敌人。具体地说，黑塔每次使用E技能，会对敌方全体造成E点伤害。
除此之外，每当一个怪物的生命值首次减小到其最大生命值的50%及以下（含50%）时，如果敌方尚有怪物存活（生命值大于零），那么黑塔就会自动释放一次追加攻击“转圈圈”，对敌方全体造成R点伤害。如果一次攻击同时使多个敌人满足以上条件，那么黑塔也会连续释放多次“转圈圈”，直到“转圈圈”次数耗尽或者敌人全部倒下为止。在“转圈圈”结束之前，黑塔无法再次使用E技能。
作为天才俱乐部#83的天才，黑塔只用了0.0114514秒就算出了自己需要使用多少次E技能才能击败这些怪物，以及在这个过程中她会释放多少次“转圈圈”。她觉得这个问题太简单了，于是将其留给了你作为课后习题。
输入描述
第一行一个正整数T，表示有T组数据。
对于每一组数据，第一行一个正整数n，表示怪物的数量；
第二行n个正整数hy;hzhn，表示每个怪物的生命值；
第三行两个正整数E,R，分别表示黑塔E技能的伤害和“转圈圈”的伤害。
1<=n<=10^5
1<=T<=10
1<=h_i, E, R<=10^9。
输出描述
对于每一组数据，输出一行两个正整数cntE， cntR，分别表示黑塔使用E技能的次数和“转圈圈”的次数。
样例输入
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
3
5
100 50 60 80 70
25 10
5
100 50 60 80 70
20 20
5
100 200 300 4000 5000
50 1000
样例输出
1
2
3
4
5
2 5
2 3
1 5
提示
对于第一组数据：
初始怪物生命值为［100,50,60,80,70］；
黑塔使用E技能，怪物生命值变为［75,25,35,55,45］；
怪物2生命值小于等于50%，触发一次转圈圈，怪物生命值变为［65,15,25,45,35];
怪物3,5生命值小于等于50%，触发两次转圈圈，生命值变为［45,0,5,25,15];
怪物1,4触发两次转圈圈，生命值变为［25,0,0,5,0］；
使用E技能，生命值变为［0,0,0,0,0］，战斗结束，一共使用2次E，5次转圈圈。
对于第二组数据：
初始怪物生命值为［100,50,60,80,70］；
黑塔使用E技能，怪物生命值变为［80,30,40,60,50］；
再次使用E，生命值变为［60,10,20,40,30］；
怪物2,3.4,5触发四次转圈圈，但是只转3次所有怪物就全部被击杀，因此一共使用2次E，3次转圈圈。
对于第三组数据：
初始生命值为［100,200,300,4000,5000］
使用E技能, [50,150,250,3950,4950]
怪物1触发一次转圈圈，［0,0,0,2950,3950］
怪物2，3触发两次转圈圈，［0,0,0,950,1950］
怪物4，5触发两次转圈圈，［0,0.0.0,0］，战斗结束，一共使用1次E，5次转圈圈。
My Solution (X)
暴力模拟。超时，只通过了45%。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
# WRONG!
# 通过 45%，错误解法，超时
T = int(input())
for _ in range(T):
n = int(input())
h = list(map(int, input().split()))
e, r = map(int, input().split())
# T = 1
# n = 5
# h = [100, 200, 300, 4000, 5000]
# e, r = 50, 1000
cntE = cntR = 0
h.sort()
damage = 0 # 总伤害
circle = [False] * n # 是否转过圈
for i in range(n):
if damage >= h[i]: # dead
continue
need_to_E = 0
if damage * 2 < h[i]: # 一直E，等到血量最少的减半为止
need_to_E = int((h[i] / 2 - damage - 0.1) // e) + 1
damage += need_to_E * e
cntE += need_to_E
if need_to_E == 0: # 不E不能转圈
need_to_E = 1
damage += e
cntE += 1
for j in range(i, n):
if damage * 2 < h[j]: # 伤害不到血量一半，说明后面的无法转圈
break
if damage >= h[-1]: # all dead
break
if damage * 2 >= h[j] and not circle[j]: # 转圈
circle[j] = True
damage += r
cntR += 1
print(cntE, cntR)
Correct Solution
1
Q2 捉拿岁阳
时间限制：3000MS
内存限制：589824KB
题目描述
岁阳是一种不具固定形体的能量生物。一些不怀好意的岁阳会扰乱正常的社会秩序。
现在，藿藿被委派捉拿岁阳。
藿藿会选择一个点 (x1, y1)，以 (0, 0) 为左下角，(x1, y1) 为右上角，平行于坐标轴，构成一个矩形陷阱，如果岁阳位于这个矩形内部或边界上，就可以成功捉拿岁阳。岁阳的位置被记作 (x2, y2)。
下面，给出坐标（x, y）的构成方法：
给定一个长度为n的整数序列a，和一个长度为m的整数序列b，从a中选择其中一个数字作为x，从b中选择一个数字作为y，这样可以得到一组坐标（x, y）。
藿藿所选择的 (x1, y1) 和岁阳的位置 (x2, y2) 均通过上述办法产生。
你的任务是计算在所有可能的情形中，藿藿能够成功捉拿岁阳的情形数量。
输入描述
第一行两个整数n和m，分别表示数组a 和b的长度。
第二行 n个整数 a1, a2, ⋯, a_n，表示序列 a。
第三行 m 个整数b1, b2, ⋯, b_m，表示序列 b。
对于全部数据，
1 ≤ n, m ≤ 5 * 10^4
1 ≤ a_i, b_j ≤ 10^9
输出描述
输出一行，一个整数，表示答案。
样例输入
1
2
3
4
5
3 3
1 2 3
1 1 3
样例输出
1
42
提示
当藿藿选择的位置是（1，1），岁阳选择的位置是（1，3）时，藿藿无法成功捉拿岁阳。
当藿藿选择的位置是（2，3），岁阳选择的位置是（2，1）时，藿藿可以成功捉拿岁阳。
类似的情况共有 42 种，因此输出42。
My Solution (X)
暴力累加。超时，只通过了55%。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
# WRONG!
# 通过 55%，错误解法，超时
n, m = map(int, input().split())
a = list(map(int, input().split()))
b = list(map(int, input().split()))
# n, m = 3, 3
# a = [1, 2, 3]
# b = [1, 1, 3]
a.sort()
b.sort()
ans = 0
for i in range(n):
for j in range(m):
x = i
# 需要用二分找到i最右边的相同数字a[x]，此处暂暴力
while x < n and a[x] == a[i]:
x += 1
y = j
while y < m and b[y] == b[j]:
y += 1
ans += x * y
print(ans)
Correct Solution
1
Q3 启动机器
时间限制：3000MS
内存限制：589824KB
题目描述
在潜入下层工厂后，蓬莱寺九霄在其中一个房间中发现了N（1≤N≤5000）台机器。这些机器排成一排，从左到右依次编号为1、2、… 、N。且每台机器都有一个能量值，编号为i的机器的能量值为a_i（-10^12 ≤ a_i ≤ 10^12）。现在蓬莱寺九霄想要启动其中一些机器。在简单尝试后，她发现若两台启动的机器之间没有其他任何其他启动的机器，则这两台机器会尝试连接；但是若一台机器左右两边都有机器尝试与其连接，且左右两台机器能量值的平均值大于等于中间这台机器的能量值，则会使得中间的机器系统崩溃。
现在所有的机器都已恢复关机状态，九霄想知道的是，在不引发机器系统崩溃的情况下，最多可以同时启动多少台机器？
输入描述
输入的第一行包括一个整数N，表示机器的数量。
第二行包括N个整数 a1、a2、… 、a_N，表示这 N 台机器的能量值。
输出描述
输出只包括一行，即最多可以同时启动的机器数量。
样例输入
1
2
3
5
1 2 3 2 1
样例输出
1
4
提示
样例解释
在这一情景中，蓬莱寺九霄可以选择启动编号为1、2、4、5的机器。
数据范围
1 ≤ N ≤ 5000
-10^12 ≤ a_i ≤ 10^12
My Solution (X)
很搞笑。我没有思路，直接面向测试用例输出了 4，居然通过了 18%。
1
2
3
4
5
6
7
8
9
10
# WRONG!
# 通过 18%，错误解法
n = int(input())
a = list(map(int, input().split()))
# n = 5
# a = [1, 2, 3, 2, 1]
print(4)
Correct Solution
1
Others
据测开同学表示，编程题第三题是SQL题。