携程笔试第一场题解

1.直接模拟
2.从小到大排序,从后往前遍历i,每次取i~n这段数组看看答案会不会更大,即不断更新ans=max(ans, a[i] + n - i + 1)。
3.先预处理每个数的质因子个数a[i]。对a数组求前缀和。然后枚举长度为k的滑动窗口往后移动,更新答案
4.树形dp,记dp[i]为从结点i往下走的路径为偶数的方案数。可以发现,只有所有数都为偶数时,这些数的gcd才可能为偶数,因此只需要判断数的奇偶性就行,不用去算gcd。dfs每个结点u,枚举以u为路径最高点时路径为偶数的方案数,累加起来就是答案。对于每个偶数结点u,dp[u]=u的儿子的dp和 + 1,这样就完成了dp的更新;累加答案的话,就是枚举u的每个儿子dp[i],和他左边儿子的dp和sum,ans+=sum*dp[i],然后sum+=dp[i],因为以u为最高点的话,u左边和u右边的路径是可以组合起来的;

第四题可能讲的不是很清楚,但属于树形dp挺常见的类型
全部评论
树形dp好难
点赞 回复 分享
发布于 2025-03-27 03:30 江苏
可以问一下第四题为什么偶数个奇数之和不满足条件吗?
点赞 回复 分享
发布于 2025-03-13 22:33 湖北
第四题思路一样,但是只过了5%
点赞 回复 分享
发布于 2025-03-13 21:42 广东

相关推荐

我是秋招面的抖音电商部门,从八月开始给我打电话约面试,当时有加对应的hr微信,前几轮还好,从三面开始就是拖半个月一下在推进,面了三轮以后拖了一个月说再加一个交叉面,面完过了半个多月问hr,hr说她离职了不管我了,我连自己的流程在哪里都不清楚。在官网投诉了三次(前两次正常反馈问题,字节你像听不懂话一样),今天下午突然有其他部门约我面试,说在人才库里看见我简历了觉得很匹配,我拒了说不想面了。过了一会,声称原来那个部门的hr负责人给我回电话,表示抱歉,说因为北京hc不够了把我流程释放了,前面的hr是实习生离职了,没有和我对接非常抱歉,如果有想法可以帮我推荐给其他部门。那么我问你:1. 从八月等到11月,三个月时间我前面不断确认还有没有hc,给我的回复都是有hc,没hc你面什么呢?2. 作为一个大厂你流程这么一坨?让实习生对接校招流程,实习生离职了对应的候选人就不管了?不是我主动问我的流程就这样一直被卡?3. 还说我面评没问题,帮我推荐其他部门,现在各个大厂都开奖了,你还让我从头开始面?我前面面了你们三个月啊,孩子饿死了开始装得想负责了。4. 你们官网的流程反馈对应的人员是理解能力有问题吗,一个问题我投诉三次才能看明白是吗?套话一堆在哪里随便选了个常用语就给我回复了?不想开可以直接把入口关了
奋斗的小码农a:字节流程就是恶心死人,一次字节广告5面挂一次字节抖音电商6面挂,最后那个面试官装都不装了直接分屏聊天还外放语音家里真的私募了
秋招吐槽大会
点赞 评论 收藏
分享
评论
点赞
4
分享

创作者周榜

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