携程笔试 3.13

四个编程题，一题 20 分第一题签到题，每隔i个输出一个字母第二题贪心题，数组排序之后从最后一个开始往回涂黑，每次更新最大值第三题质因数分解+滑动窗口，用埃氏筛法预处理，然后滑动窗口计算最大值，但是只得了 23？第四题应该是dfs，建树之后标记奇偶节点，然后dfs遍历求解实习加班，赶着回来做的，已老实#实习# #大厂# #软件开发笔面经# #没有实习经历，还有机会进大厂吗# #携程# #携程求职进展汇总#

第一题：模拟第二题：排序，从前往后比哪里 当前数 x 大于当前数的个数(nums.length - i) 取最大值第三题：计算质因数 + 滑动窗口第四题：多个数计算gcd + dfs: 超时了，只过了50%@*zfffz* 提供的优化思路：题目要求多个数gcd为偶数，实际上就是每个数为偶数即可如果对你有用的话，求个花花

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挺常见的类型

携程笔试主要分三关：一、携程行测笔试携程校园招聘笔试内容为行测，题型包括：言语理解、数字运算、图形推理，其中图形推理包括平面类和空间类。1、言语理解主要测查报考者运用语言文字进行思考和交流、迅速准确地理解和把握文字材料内涵的能力。常见的题型有：阅读理解、言语推理。2、数字运算每道题给出一段材料，包括图表和文字，要求报考者熟练运用加、减、乘、除等基本运算法则，并利用其他基本数学知识，准确迅速地计算或推出结果，难度不大。3、图形推理携程的校招笔试中图形推理主要分为两类——平面图形和空间图形。平面图形类主要包括：既位置类、样式类、属性类和数量类；其中位置类题的特征是各图图形元素组成相同，整体或局部位...