昨天 20:57 门头沟学院 golang 发布于浙江
关注
美团8.16笔试（进度2.25/3）
第一题：贪心，不难发现在位数限制范围内，只要n个数在某一位上并不都为1，那么该为一定可以通过 或 加到该位不为1的数上，所以答案就是总和+所有并不都为1的数位的总和（例如[110,111,100]二进制表示，所有并不都为1的位数的总和为011）。
第二题：贪心，开个unordered_map<int,pair<int,int>>维护该数在<a,b>数组中的个数。从堆中不断弹出最大的元素然后将差值通过g(x)的方式往下缩即可。（优化方式1：记得判断该数是否已经进过堆，优化方式2：map改unordered_map）
第三题：不会，打的暴力，请教各位大佬了
ps：笔者未使用ai，也不清楚是否可以使用ai
第二题：贪心，开个unordered_map<int,pair<int,int>>维护该数在<a,b>数组中的个数。从堆中不断弹出最大的元素然后将差值通过g(x)的方式往下缩即可。（优化方式1：记得判断该数是否已经进过堆，优化方式2：map改unordered_map）
第三题：不会，打的暴力，请教各位大佬了
ps：笔者未使用ai，也不清楚是否可以使用ai
全部评论
lc1111
门头沟学院 嵌入式软件工程师
第一题就是按照这个思路写的，不知道哪里出问题了，只通过了20%
我不是鼠鼠
门头沟学院 后端
为啥你们第一题那么多公式都会，不用ai能做下来真的天赋异禀 牛客360500701号
mark一下
林聪123
西安电子科技大学 C++
第三题我的想法是离散化后维护正序对数组，本质上题目要求的就是对于每个 i，i 右侧的正序对数量，但正序对需要满足一个前提是不能超过 a[i]。
所以逆序遍历，维护一个 f[x] 表示截至目前为止，正序对最大值为 x 的正序对数量，那么遍历到 i 的时候，此时的贡献就是 f 数组的 1 ~ a[i] - 1 这一段的区间求和，因为这一段的正序对就没超过 a[i]。
接着就是要更新 f 数组，也就是说要把 a[i] 也给***去，插的时候比较直观的就是 a[i] 会对 a[i] + 1 ~ n 这一段产生贡献，也就是对这一段区间 +1，但问题是这一段有的点还不存在，那么是没有贡献的，所以我们在线段树上维护一个“节点打开数量”，初始所有节点都是“关闭”的，每次打开一个新的点，然后因为维护了这个数量，所以区间 +1 对区间 sum 只会生效这个数量那么多，然后就做完了
偶就要搞开发
门头沟学院 Java
mark一下
求你们别卷了的西红柿很爱吃鸡腿
哈尔滨工业大学 Java
第一题我也是一样的思路不知道为啥只过了92，可能有什么地方要转long没转吧。第二题我是用优先队列做的，最后卡在95%超时了。第三题完全不会只剩十分钟直接暴力还过了41，反而第三题是最好拿分的。
青提睡觉
中南大学 C++
佬，太强了
相关推荐
昨天 20:50
中南财经政法大学 大数据开发工程师 点赞 评论 收藏
分享
昨天 20:54
中山大学 算法工程师 sunyuheng3...：第三题如果做过三维偏序就很简单，用cdq+树状数组就行，考虑对[l，r]时贡献，i位于[l，mid]，k位于[mid+1，r]，然后分类讨论下j位于左右的求值方法即可。
投递美团等公司10个岗位 点赞 评论 收藏
分享
昨天 19:54
门头沟学院 机械设计/制造 点赞 评论 收藏
分享
