美团笔试10.7

前三题签到题,第四题有一些思路,但是想出来的时候时间来不及了。
题目意思可以解释为,任选2个集合,其并集的大小之和,除以n(n-2)/2,即为最终答案。
举例n=3,集合分别为
A:11,12,13
B:12,13
C:13,14,15
存在3个并集,
A并B 11,12,13 
B并C 12,13,14,15
A并C 11,12,13,14,15
考虑所有数字出现的情况。
11:A
12:AB
13:ABC
14:C
15:C
对于11在集合出现的次数为1次,最终他在并集中贡献了多少呢?应该是1*(n-1)=2次,也就是,选取A,再任选其余(n-1)个集合。
对于12在集合中出现次数为2次,其贡献为2*(n-1)-C22=3次,其中2*(n-1)意思是对于X并Y,X可以在12出现的2个集合中选一个,n-1为Y的可选个数,但需要减去重复选项,也就是C22个。
同理对于13,贡献次数应为3*(n-1)-C32=3次
因此该题解法为,对于每一个数字在集合中出现的次数为x,则其在并集中出现的次数为x*(n-1)-Cx2,其中C12=0。求和后除以Cn2即可。
有没有兄弟是这个思路做出来的求教,另求第五题好节点的解法。 #美团# #美团笔试#
全部评论
第四题我这样做的,ac了
2 回复 分享
发布于 2023-10-07 21:47 湖南
可以说一下美丽串的思路吗
点赞 回复 分享
发布于 2023-10-08 00:24 安徽
第一二题可以说下思路吗大佬
点赞 回复 分享
发布于 2023-10-07 21:39 香港
第五题拆分成树形DP+找一个最大10^14的数的因子数,但是这个数太大,哪怕sqrtn 都超时,可能要用到记忆化搜索,然后没时间了……
点赞 回复 分享
发布于 2023-10-07 21:38 湖北

相关推荐

2025-12-08 16:04
门头沟学院 Java
本人本科末9,今年大三。大一大二一直玩,什么都没学到,在大学混日子混了两年,每天不是在打农就是在steam。大三开学时一个和自己玩的好的同学去实习了,才发现自己白白浪费了两年的时间,如果真不冲一下就真去京东,阿里,美团送外卖了今年9月份开始学Java,一开始一直跟着黑马视频看,后面发现看视频效率太低了,时间根本不够,就开始主要看文档和看书了。这几个月一直在学,真的尽力了,希望暑期前能找一份好点的实习。我简历上面的项目大多没有指标,但是实际上我是真没多少时间去做项目,我基本主要是动手只做了外卖和天机,黑马点评和12306我都是只是看了项目。主要是自己的时间真的不多,但是这样子自己的代码能力确实比较差。而且自己也没有做过实际的工程,我顶多用jmeter测试一下接口tps啥的,比如使用Redis管道提升了一点性能,减少Redis交互,这种值得写上去吗?需不需要具体到某些数字求求各位佬给一些建议,看看简历怎么优化?项目介绍是不是不够详细?没有具体到业务方面。项目会不会提到大致实现原理导致面试官一看简历就知道怎么实现就没有问的欲望?专业技能一些字段是不是要加粗,是不是写太啰嗦了?有没有必要压缩内容变成一页?两页的话是不是都要把两页填地满满的。
给秋招一个交代:一页简历最好,网上做的项目放面试官眼里都是玩具,简历上不需要强调有什么难点,记住就行防止真的问。然后背八股,多投多面试就行
点赞 评论 收藏
分享
评论
1
3
分享

创作者周榜

更多
牛客网
牛客网在线编程
牛客网题解
牛客企业服务