2024-03-24 拼多多笔试 250/400

拼多多是真的难啊

第一题 100%
有n，m，k，d四个数，n表示数组的大小。Alice可以选择删除d个数，Bob可以选择将m个数 *（-k）；其中Alice希望总和尽量大，Bob希望总和尽量小，假设双方都很聪明，输出最终的结果。
由于数字都是正数，最开始Alice不操作的情况下，Bob会调整最大的m个数，当Alice可以删除的时候，用滑动窗口从大往小维护即可
第二题 100%
题意有点复杂，但是就是字符串模拟
第三题 50%
有3e5个点组成的DAG图，定义一个超级点：点本身 + 能到达该点的点数 + 该点能到达的点数之和 = n
想了半天没想出来解法，最后暴力过了50%，bool vis[]定义成int vis[]时间戳的形式可以省去每次清空数组的时间
第四题 0%

PS：第三题转换成无向图就是求割点，笔试的时候想起来感觉不对劲又没写了；一个大佬给了另一种解法，正反建图拓扑排序，当队列只有一个点并且被减少过入度的点都入队了，那么该点的左半边可以到达他，反过来跑的时候就可以判断右半边

#笔试经验##软件开发2024笔面经#

全部评论

推荐最新楼层

BatmanX

四川大学戏剧与影视学类

佬！

2 回复

发布于 03-24 21:36 四川

得物校园招聘部hr

得物app_前端工程师(准入职员工)

佬，看看帖，得物春招

2 回复

发布于 03-25 09:28 陕西

联易融

校招火热招聘中

官网直投

牛客927075895号

National University of Singapore 计算机类

第三题提供一种角度，直觉是所有的超级点都形成某种“bottleneck”结构。设dist[v]表示点v到任意出度为0的点的最长距离。那么任意点v是超级点当且仅当：(1) 不存在其他最长距离为dist[v]的点；(2) 对任意入度为0的点u，有dist[u] > dist[v]。

2 回复

发布于 03-25 18:12 广东

飞翎游侠

小米集团_AI实验室_后端开发(准入职员工)

很强了能做2.5道

1 回复

发布于 03-24 21:27 美国

kingge

中国科学技术大学计算机类

大佬，第一题思路能说详细点吗

1 回复

发布于 03-24 22:07 北京

雅鹿撒二

东南大学计算机类

第二题咋做的啊，佬

1 回复

发布于 03-24 23:06 江苏

牛客485316751号

华南理工大学计算机类

第三题是拓扑排序，记录下所有的点，以及入度跟下一节点的vector.然后拓扑排序，排序前遍历一遍，把起始点(也就是入度本来就为0)的设置一个初始值1.0，并记录下总初始流量，每个点平均将他的值分给所有下一节点，例如1-2 1-3 2-4 3-4，一开始只有1号点值为1，有两个出点，故2 3都加上0.5，2只有一个出点，4+0.5，3也是一个出点，4再+0.5最后，在拓扑排序过程中，看看有没有那一个点的值为一开始所有初始流量和，有的话那个点就是超级点，例如我这个样例中流量和为1.0，其中1，4都是1.0的流量，故1，4是超级点。拓扑排序n级别复杂度，唯一注意小数计算可能有精度丢失，判断相等时用范围判断

1 回复

发布于 03-25 11:35 广东

rockNSX

华中科技大学计算机类

第四题区间DP95%，dp[i][j]表示最少删完的次数，答案就是dp[0][n-1]

1 回复

发布于 03-25 11:55 湖北

内推公司合集

广联达_人力资源管理_HR

看看春招合集呀

1 回复

发布于 03-26 08:25 陕西