拼多多笔试 0526 24届算法

有点伤感秋招不努力，都要毕业了这个时间点还在做笔试，按道理应该是去度假的。

第一题题意： 给定一个长度为n (n < 1e5) 的序列以及一个数m(1 < m < 1e5)，序列中每个数的范围为0~1e9，求所有的位置p使得序列前p个数包含k组1~m的所有值。比如n=9，m=4，序列为[2, 3, 4, 1, 5, 1, 2, 3, 4]，答案输出4和9。
第一题做法：搞个数组存一下1~m出现的次数，标记表示一下有多少0变到1，每次加1，每当标记加到m，数组所有值减1，标记每当1变到0时减1。时间复杂度O(n)。

第二题题意：给定一个长度为n (n < 2e5）的01字符串以及操作次数m (<1e9)，每个操作选择位置x，使得字符串位置x和位置x+1不变，其余位置全部翻转（0变为1，1变为0）。求操作完毕之后字符串对应二进制的最小值。
第二题做法：首先转化一下题意，操作可以变为：一、先将字符串所有位置翻转m次，二：进行m次翻转相邻两个位置的操作。对于第一步操作：当m为偶数时不变，奇数时翻转；对于第二步操作，从左到右贪心，为1时翻转。多余的操作就只动最后一位。时间复杂度O(n)

第三题题意：给定一个长度为n (n < 1e5) 的数组，进行q(<1e5)次对原数组的查询，问最小进行几次操作使得第k大的数为x (<1e9)，每次操作可以选择数组的某个数加1。
第三题做法：（第k大等价于第l = n+1-k小）首先对数组进行排序，然后求前缀和，对于每次查询，二分查找找到第一个比x大的位置pos，答案为(pos - l + 1) * x - sum[pos] + sum[l - 1]。时间复杂度O(nlogn + qlogn)

第四题题意：给定p, q, n，(p, q <= n < 1e18)，表示容量为n的容器，一开始存储为0，每次可以加p(剩余容量大于等于p)或者减去q(容器已有至少为q)，当存在既不能加p也不能减q的情况输出Yes，否则No。
第四题做法：分类讨论一下，虽然表达式一样。当p > q时，No的情况为 p + q - gcd(p, q) > n。当p < q时，No的情况为 q + p - gcd(p, q) > n。时间复杂度O(log n)。