9/22拼多多笔试

第四题

第四题：     对于每枚棋子它最终所在列只和它初始所在列、左右操作有关；它最终所在行只和它初始所在行、上下操作有关。于是将上下操作抽取出来、左右操作抽取出来分开处理。 求列的值（只考虑左右操作）:    记"左" 对答案的影响为 -1    记"右" 对答案的影响为 1 然后遍历所有的左右操作，对操作统计一个前缀和sum。如果第 i 列+ sum < 1，那么它的结果将和第 i+1列相同，并查集合并第 i 列和第 i +1 列（将第 i 列合并到第 i+1 列）；如果第 i 列 + sum >Y，那么它的结果将和第 i-1列相同，并查集合并第 i列和第 i-1列（将第 i 列合并到第 i-1 列）。那么第 i 列最后的结果就是它的祖先初始所在列+sum（祖先没有被合并，说明祖先并不会“碰壁”）。 特殊情况：合并到只剩一个列了，说明所有列的结果都相同，直接暴力模拟一遍左右操作对该列的影响即可。 求行的值同上。

第三题，你怎么做的呀

应届生可国央企内部推，合适的联系我

AK思路总结帖： 第一题，直接暴力二分前缀和； 第二题，注意到颜色数目k<=14, 所以n+m-1 > k，最终答案肯定是0，所以其他情况直接dfs 暴力搜索就可以； 第三题，根据身高建立队列，这个首先需要建立一个答案的队列，然后从前往后按照个数进行插入就可以，复杂度n平方； 第四题，移动棋子，由于M，N个数都是1e5，所以肯定不能一个一个暴力挪动，由于所有棋子的移动操作都是相同的，那么从起点（p, q）到终点(x, y)，就是p == x + delta_x, q == y + delta_y,  首先假设你有一个无限大的矩阵，你站在（0，0）处，然后一步步移动，就可以得到最后的所在的位置，也就是两个方向上的偏移量， 但是这里的移动操作遇到越界的情况，会跳过，所以在上面的移动过程中，你还需要记录一个你在两个方向上能够到达的最大值和最小值，从而根据这个最大最小值判断有无超出矩阵边界。这是因为，如果你移动过程中越过了边界，但又移动了回来，所以你会在移动回来的方向上浪费掉了越界的那些距离，因为右边的时候他们是不动的，这等价于你需要反方向移动越界的长度，这里画一画图就可以明白了。所以这个在两个方向上的坐标就是一个起点到终点的改变量，一个越界长度的反向的改变量的和。复杂度O(M+N)

第三题测试用例是啥啊 有人还记得吗

感觉第四题数据有点水。。加了个行列标记去重水过去了...

第二题怎么做啊大佬们

有人帮忙看看有啥问题吗，思路比较清奇但测了几个都是对的，0%通过率😂

说实在,第三题我连题目都没怎看明白,这站位啥意思,看不懂,直接跳4去了,做完回来看3还是不懂,直接交卷,懒得废话

第四题：排序 + 懒标记线段树 https://paste.ubuntu.com/p/cysnBYC9QX/

想问问力扣有类似吗

第三题 推排序 0% 是平台不让自己定义一个类吗？还是什么 哪位大佬说一下能不能自己定义Student类

最后一道题有人截图了嘛？想知道测试用例的结果，上下左右好像没搞清楚😂

第二题dfs超时，没超时的是怎么优化的啊

蹲一个第四题

hxd讲讲第四道

想问一下大佬们第一题怎么做的。。用了二分查找还是超时了。。。😅

估计大部分都是3.2道了

3.2道，最后一题不知道咋做