05-06 21:15 第一拖拉机制造厂拖拉机学院 哲学类
关注
携程笔试5.6
感觉前两题比较简单，后两题难度比较大，做完之后是100，100，20，0，也不知道能不能进面试
第一题很简单，给一个长宽，给两个符号，让输出一个矩阵，要求符号交替出现，每个符号周围（上下左右）不能是和当前符号相同的，比较简单，相信各位大佬也都能A，就不细说了。
第二题也不难，给一个正整数（非常长，可能有5000位），给一个k，给一个p，要求找到这个正整数中长度为k的一段数字的最大值，输出这个最大值%p的结果，也不很难。
第三题看起来很简单，但是实际有难度。给一个数组，长度为n，再给q组数据，每组数据两个数l,r，代表左右边界，要求输出数组第l位一直乘到第r位的乘积%6。1
相信各位牛友都能写出来，主要问题在于时间复杂度。如果使用最直接的方法算，n，q都到10^5时显然会超时，这也是一直卡在20%的原因。显然他是想让我们利用一些计算过的值，不要有太多重复计算，这可以大大减少时间复杂度，例如我们算过了10-20，在算10-21时直接用10-20的结果乘21就好了。
最开始试图直接打表，写完发现内存爆了，此路不通。
苦思冥想怎么能够实现重复利用，想到一种思路，我们可以分块，比如1-100000分成100块：1-1000、1000-2000、……、99000-100000，预先计算出每一段的结果，存起来，然后算q组数据的时候就可以利用了，比如0-2001，就可以利用1-1000、1000-2000这两段从而降低时间复杂度。
但是想了太久了，最后也没写完，也不知道可不可行，哎，还是题写的太少了，菜还是得练，刷题去了
这是鼠鼠做的第一个比较大的厂的笔试，本来还想着要不要推到下一批，想想算了，直接冲吧。也不知道能不能过
欢迎牛友们一起交流，本人四月底才开始申请暑期实习，希望能和各位大佬们多交流，早日收到满意offer！
第一题很简单，给一个长宽，给两个符号，让输出一个矩阵，要求符号交替出现，每个符号周围（上下左右）不能是和当前符号相同的，比较简单，相信各位大佬也都能A，就不细说了。
第二题也不难，给一个正整数（非常长，可能有5000位），给一个k，给一个p，要求找到这个正整数中长度为k的一段数字的最大值，输出这个最大值%p的结果，也不很难。
第三题看起来很简单，但是实际有难度。给一个数组，长度为n，再给q组数据，每组数据两个数l,r，代表左右边界，要求输出数组第l位一直乘到第r位的乘积%6。1
相信各位牛友都能写出来，主要问题在于时间复杂度。如果使用最直接的方法算，n，q都到10^5时显然会超时，这也是一直卡在20%的原因。显然他是想让我们利用一些计算过的值，不要有太多重复计算，这可以大大减少时间复杂度，例如我们算过了10-20，在算10-21时直接用10-20的结果乘21就好了。
最开始试图直接打表，写完发现内存爆了，此路不通。
苦思冥想怎么能够实现重复利用，想到一种思路，我们可以分块，比如1-100000分成100块：1-1000、1000-2000、……、99000-100000，预先计算出每一段的结果，存起来，然后算q组数据的时候就可以利用了，比如0-2001，就可以利用1-1000、1000-2000这两段从而降低时间复杂度。
但是想了太久了，最后也没写完，也不知道可不可行，哎，还是题写的太少了，菜还是得练，刷题去了
这是鼠鼠做的第一个比较大的厂的笔试，本来还想着要不要推到下一批，想想算了，直接冲吧。也不知道能不能过
欢迎牛友们一起交流，本人四月底才开始申请暑期实习，希望能和各位大佬们多交流，早日收到满意offer！
全部评论
讲文明的小黄鸭在思考
上海交通大学 计算机类
第三题线段树，第四题换根dp,不过逻辑有点复杂调了半天😂
送花
回复
分享
洞中千年修此身
中国科学院大学信息工程研究所 计算机类
第三题可以考虑因子分解，利用容斥原理，如果区间内的数能够分解出来2*3，则返回0，如果区间内有2 没有3，返回2，有3没有2，返回3，其他情况继续讨论，可以进一步考虑质数因子的个数。不过我只写了判断区间内部23的部分，过了35%。
送花
回复
分享
秋招专场
校招火热招聘中
官网直投
点我头像查看联想春招实习内推
联想信息产品(深圳)有限公司_系统开发工程师(准入职员工)
大佬过了吗
送花
回复
分享
冼杞然
四川农业大学 土木类
请教大佬第二题，这个数字长度特别长怎么算%p呢
送花
回复
分享
牛客437283432号
江南大学 电子信息类
请教第一题 为什么我超时了呜呜 用了两层for循环
送花
回复
分享
云月来
复旦大学 计算机类
第三题好像是线段树
送花
回复
分享
洞中千年修此身
中国科学院大学信息工程研究所 计算机类
第二题 python可以暴力过。非暴力的话，应该考虑使用滑动窗口来写。维护窗口内部的数字和，每次移位减去左端点最高位，加上右端点最低位，O(n) 时间复杂度。
送花
回复
分享
微雨闻孤馆
吉林大学 计算机类
第三题不是快速幂吗？对每个输入数据对6取模，输入数据的长度为n，建一个（n，6）的二维数组f，f［i］为0-i之间的012345每个数的个数，计算l和r之间的012345的个数，并进行快速幂，计算过程中需要对6取模，就可以了
送花
回复
分享
找个活干呗
东华大学 计算机类
这是暑期实习的难度？
送花
回复
分享
想被叫靓仔的鳄鱼等oc
北京理工大学 计算机类
一模一样😂
送花
回复
分享
hylll
华南理工大学 计算机类
大佬，第二题怎么做的？可以展开说下吗
送花
回复
分享
小李要上班
门头沟学院 计算机类
第一题用java为啥超时啊后面同样思路改成c才过的
后面同样思路改成c才过的
送花
回复
分享
鼠鼠1号
西安电子科技大学 计算机类
第三题dp爆内存，换线段树才过
第四题完全没思路，草草交卷
第四题完全没思路，草草交卷
送花
回复
分享
相关推荐
查看4道真题和解析
投递携程等公司9个岗位 >