米哈游笔试 2024.8.17

记录一下秋招参加的第二场笔试，难度不大

1. 购买原石，月卡 or 直接买？

   暴力贪心一下就行

2. m名工人，第i个区间 ，计算有多少个区间满足完全被其他区间覆盖？

   首先通过差分+前缀和求出每个位置被多少个区间覆盖，并将只有一个区间的对应位置（独苗）按顺序记录下来，最后通过二分查找判断每个区间内是否存在独苗，若是，则表示其无法被其他区间覆盖。

3. 有一个长为n的数组a，询问q次，每次询问 有多少个连续的子数组包含x

   正难则反，考虑每次询问 有多少个子数组不包含x

   首先，我们需要记录数组中每个数出现的下标位置，针对一次询问，可以通过二分查找到大于等于l的x出现的最小下标，以及小于等于r的x出现的最大下标，中间这些x的出现下标将 分割成一个个子数组，答案即为 子数组个数 - 被分割出的每个子数组的子数组个数。后者可以通过前缀和优化 O(1) 求得。