饿了么春季2025届实习生笔试 编程题AK

第一题：

• 求一个数组的素数与合数的数量和
• 写个素数筛，数组元素去重后求数量和

第二题：

• 一个长度为1e5的正整数数组，定义f（L, R）表示区间[L, R]元素的或，即a_l | a_l+1 | ... | a_r ，有1e5次询问，每次询问一个区间[l, r]中是否存在一个下标x，使得f（l, x）= k，输出最小的x，若不存在输出-1
• 或是存在的关系，具有单调性，把数字拆成二进制后对每一个二进制位判断，以下举例来说明
• 数组元素为1，2，3，4，5，二进制为001，010，011，100，101，用二维动态数组将每个1所对应的下标保存下来，即0：{1, 3, 5}，1：{2，3}，2：{4，5}
• 查询的数字也用二进制表示，二分判断每一个1是否存在于[l，r]区间内并取最小下标，答案就是每个最小下标的最大值
• 注意判断一下不存在的位，比如数字1（001）无法用数字5（101）表示

第三题：

• 一个点数为2e5的带边权图，每删一条边则获得该边的权值，问将整个图变成两个连通块可以获得的最大权值是多少，若无法变成两个连通块输出-1
• 先要用最小生成树获得最小连通图的最大代价
• 若此时
• 连通块数量 > 2，输出-1
• 连通块数量 = 2，输出答案
• 连通块数量 = 1，再删一条剩下边中权值最大的那条