PDD 服务端研发工程师笔试 0914

#pdd##拼多多求职进展汇总##拼多多#

四道题 40min

比某需要手写输入输出的简单 我说的（）

11:35 一更
怎么这 性格测试 也要双机位 太抽象了

12:01 二更

t1 字符串
从A串构建B串，方法为：A串每个长度为2的子串连接成一起
给B串，反推A串

t2 发货
n, m, x
n天可以发货，一共要发m个货， 每天最多发x次
ai 表示第i天发货多少钱
bj 表示第j个包裹要在第j天或之前发货
求发完货最少需要多少钱

t3 水晶
n个水晶，每个水晶能量为ai

求多少个子串满足 子串size = SUM(a[i..j])

t4 序列分数
一个长度为n的序列，q次查询
每次给出x和y，可以进行任意次交换操作

然后
求sum(a[0..(int)(n / x)]) - sum(a[0..(int)(n / y)])可能的最大值
样例n = 7, x = 2, y = 3 即(a2 + a4 + a6) - (a4 + a6)

题解

t1
去掉尾部，输出奇数位的字符串
然后加上尾部

t2
贪心 + 懒删除（？）
排序包裹从小到大处理
小根堆维护当前最低的价格，同时记录可以在这个价格发货的天数的出现次数，暴力塞就完事
然后判次数是否已经耗尽，耗尽就弹出

t3
易知求prefix_sum[i] = prefix_sum[j - 1] + (i - j + 1)
推出 prefix_sum[i] - i - 1 = prefix_sum[j - 1] - j
蛤希表维护后者，O1查询

t4
贪心，放左边的越大越好，放右边的越小越好
维护升序、降序两个排序后的序列的前缀和

左边的个数为 n / x 右边的个数为 n / y（废话）
但是存在重复
重复应该是 n / 最小公约数(x, y)
即 n / (x * y / gcd(x, y))
去掉重复的个数后
用前缀和O1取最大的 - 最小的