2023-10-07 21:33 已编辑 门头沟学院 Java
关注
美团笔试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即可。
有没有兄弟是这个思路做出来的求教，另求第五题好节点的解法。 #美团# #美团笔试#
题目意思可以解释为，任选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即可。
有没有兄弟是这个思路做出来的求教，另求第五题好节点的解法。 #美团# #美团笔试#
全部评论
梦之泪_伤
湖南大学 C++
第四题我这样做的，ac了
她与offer皆过客_我和大厂都无缘
武汉大学 Java
第五题拆分成树形DP+找一个最大10^14的数的因子数，但是这个数太大，哪怕sqrtn 都超时，可能要用到记忆化搜索，然后没时间了……
牛客666221198号
蚌埠坦克学院 Web前端
第一二题可以说下思路吗大佬
牛客73481006号
中国科学技术大学 Web前端
可以说一下美丽串的思路吗
相关推荐
投递中国农业发展银行等公司10个岗位 >
查看15道真题和解析