8.27 米哈游笔试

2小时，10单选，15多选，3编程。

选择题考点涉及NAT、TCP、UDP、DNS、IGMP、RIP、vector、auto、enum、结构体、B+树、sql语句、get/post、文件共享方式、进程切换等。

• 第一题

题意：在二维坐标系上，有人和2只怪物，人的起始位置在（1，1），怪物分别在（x0，y0）和（x1，y1）。人有起始生命值H，每秒可以选择上下左右方向移动一格，如果当前格子上有怪物，也可以花费1秒和怪物战斗。怪物的起始战斗力为h[i]，每隔a[i]的时间会提升b[i]（1≤a[i], b[i]≤1e5）。如果战斗时人的剩余血量≥怪物战斗力，人可以扣除怪物战斗力数值的血量来打败怪物。求人打败两只怪物后剩余的最大生命值，如果无法打败则输出“yingyingying”。

题解：只有两种策略，先打怪物1再打怪物2，或先打怪物2再打怪物1。各算一下，取最大值。（注意怪物的战斗力可能增长到爆int）

• 第二题

题意：有n（≤1e5）个数的数组，A和B两人进行博弈。开始时在数组中随机一个位置，接下来每人要选一个位置在上一个数左边且比上一个数小的数，无法选择的人输。求先手赢的概率，用分数表示。

题解：如果初始随机数x的左边存在小于x的数，A只要选择左边最小的一个，B就无法再选了，A必赢；否则A必输。统计一下有多少个这样的x，x/n（除掉最大公约数）即为答案。

• 第三题

题意：给出一棵n（≤1e5）个点的树，每个点上有一个字符m或h或y。求树上所有路径组成的字符串中，包含mhy子串的数量。

题解：假设根节点字符为h，子节点为m的子树大小=【x，y，z】，子节点为y的子树大小=【a，b，c】，那么对答案的贡献为（x+y+z）*（a+b+c）。那么dfs统计子树大小，再在每个字符为h的节点上按该公式计算，就能得到总的答案。

————————————————————————

update

9.7收到了拒信，要么就流转到测试开发那边，麻。

真就路过条狗都给我丢一份测评+笔试啊，做完再挂我。