8.17 网易雷火笔试+美团笔试

网易雷火
第一题做了一个小时 ac 100%
第二题做了一个半小时 并查集 ac 100%
三四直接寄

美团
单选 10道 三道不确定
1、定义一个文法：S -> aSb | α（空串）
非科班表示压根没听说过文法是个什么东西
2、系统调用
a、系统调用的调用程序和被调用程序运行在不同的状态 √
b、发生系统调用时，调用程序会转换为被调用程序状态 ？？？啥意思
c、系统调用完成后，会对进程做优先权分析 √
d、系统调用可以嵌套 √
3、二级页表中，页目录表的最少记录数
好久没看了，忘了

Coding 3道
吸取网易的教训，直奔最后一道，很好，做了一个多小时还没 ac，寄

给定一个数组
小美第一步：任选数组的某一子数组（不为空），将其元素 × k
小团第二步：对第一步得到的数组，任选其某一子数组（不为空），将其元素 × k
第三步：计算数组元素总和 sum
小美的目的是让最后的 sum 最大，小团的目的是让最后的 sum 最小

乍一看，还挺简单的，把我骗进来杀了

这道题是真的怪啊，关键就在于小美要考虑的东西太多了
对于小团第二步而言，数组已经定了，直接 dp 选择和最小的子数组就好
但是对于小美第一步，如果只是单纯地选择和最大的子数组，有可能会同时减小第二步子数组的最小和
所以把两步割裂开，分别简单地选择最大和子数组或者最小和子数组，就相当于两个局部最优，得不到全局最优
并且 k 有可能是负数，逻辑还得反过来再写一遍

这么一看，小美城府真是太深了，一个礼拜后再会会小美