4.26 拼多多笔试

四个题,笔者睡过头了,只有1h时间,拼尽全力只答了2.45...

本来想当怯战蜥蜴的,但是一想到下一次笔试在半个月后,这个恐怖的罚时让笔者不能接受,最后硬着上了...

答的很烂,但是笔者真燃尽了...

T1 95%

有n个任务,要么占用a个token和b的时间,要么占用c的token和d的时间,任务可以不做

现在有m的token和t的时间,问你最多能做多少个任务.

由于实在没什么时间了,笔者写的dfs,意外发现好像是正解...

但是只有95%是hyw???笔者代码这么烂的吗dfs常数巨大???

(assert测了一下就是T在最后一个点了,但是有两个点是50个物品的,笔者不会卡时,不然有可能特判最后一个点卡过去...真是不择手段了)

T2 0%

有m个槽位,每个槽位上放一个热度值.

有n个新闻,每个新闻只能放在热度值 的范围内.最后问你最多能多少个新闻.

排序然后set乱搞一下就过了...笔者会T2但是没时间写了,喜提爆零.

T3 100%

给你一个地图( )和一堆关系,关系为 意思是a拼图在b拼图的xx方向...

保证拼图联通(不需要通过形状拟合拼图),保证信息不冲突.

直接还原即可,但是这个题的方位是 LRUB 不是LRUD,特别注意一下即可...

T4 50%

给一颗有根树.树上可以自己标关键节点,关键节点距离是一棵树上从一个点出发向根走到最近的关键节点所经过的边数(自己就是关键节点边数为0)的最大值,问在标定关键节点最多为k的情况下最小的关键节点距离是多少...

笔者本来认为是单纯搜一个dep然后用类似取模的方式加起来就行,一交才发现不对...

后续:感觉这个题是个神秘二分,d越小消耗的k越大,有单调性能直接二分...

然后二分的时候搜索子树未被覆盖的点的深度最大值...

总结

不该睡觉...不该沉迷Mr.Beast的视频...

感觉其实是能3.95的,但真没时间调了,活该.