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