饿了么0412笔试题

更新：官网一看进度回退简历挂了，情理之中吧，应该是没有HC了，不过AK了怎么的给我个kpi面也行吧

吐槽一下，这选择题怎么还有行测题。。。
第一题
签到题，统计不同合数和质数的数量
方法：放到set集合里，删去1，最后返回set集合大小即可。

第二题
定义f(i,j)表示数组arr从索引i到索引j的所有数的或
问i到j之间有没有r，使得f(i,r) = k

暴力会超时，用点小方法可以提前返回-1或者break
首先，如果arr[i] > k，直接返回-1，肯定没有，因为或是单调不递减的
其次，在从l到r遍历的过程中，发现累或的值 > k了，直接break，返回-1，同样是因为单调不递减的
使用这两个方法可以通过67%的用例，最后再加一个前缀或数组
定义一个前缀或数组prefix，prefix显然是单调不递减的
在开始遍历前，判断一下如果prefix[r] < k，直接返回-1，这样是可以通过全部用例的

第三题
有一个无环无向图，每条边有一个权值，小苯可以删除一条边并获得这条边的权值，最后的连通量为2，求小苯能获得的最大权重。

克鲁斯卡尔最小生成树的变种题，使用并查集实现
首先计算所有边的权值总和total，
然后按给定的边按权值从小到大排列
然后遍历每条边u,v,w，如果u，v连通的，跳过
否则res += w并加入并查集。
最后判断一下连通量是不是2，不是的话输出-1，是的话输出total - res即可。
并查集需要进行路径压缩，不然会超时。