Contest Info

date: 2018.03.03 13:00-18:00

practice link

Solutions

A. Three Arrays

题目大意： 有三个单调不降的数列\(\{a_n\},\{b_n\},\{c_n\}\)，长度分别为\(1\le n_a,n_b,n_c\le 5\times10^5\). 给定正整数\(d\)，求三元组\((i,j,k)\)，满足\(1\le i\le n_a,1\le j\le n_b,1\le k\le n_c\)，且\(|a_i-b_j|\le d,|a_i-c_k|\le d,|b_j-c_k|\le d\)，的数量。

题解：

枚举\(a_i\)，满足\(|a_i-b_j|\le d,|a_i-c_k|\le d\)，的\(j,k\)分别在区间\([L_{ab},R_{ab}]\)和\([L_{ac},R_{ac}]\)。

对于每个\(b_j\)预处理出\(L_j\)和\(R_j\)，使得\(\forall k(|b_j-c_k|\le d\to k \in [L_j,R_j])\)。

则问题转化为对于\(j\in [L_{ab},R_{ab}]\)，统计\(k\in [L_{ac},R_{ac}]\land k\le R_j\)的个数减去\(k\in [L_{ac},R{ac}]\land k <L_j\)的个数即可。

通过预处理前缀和与二分查找，可以做到\(O(n\log{n})\).

D. Elevator

题目大意：

有\(n\le2\times10^5\)个人要乘电梯，第\(i\)个人在时刻\(t_i\le10^9\)（单调不降）时到达电梯门口（floor0），要前往第\(a_i\le10^9\)层。

假设电梯向上或向下一层的时间为1，电梯的容量为无穷大，乘客上下电梯和开关电梯门的时间为0。

求电梯将所有人送到对应的楼层并返回floor0的最短时间。

题解：

很容易想到一个动态规划，令\(f[i]\)表示将前\(i\)个人都送到对应楼层并返回的最短时间。

则有转移方程\(\displaystyle f[i]=\min_{j<i}\{\max(f[j],t[i])+2\times\max_{j<k\le i}a_k\}\)。

考虑如何优化这个转移。

如果连续的一段\([l,r]\)满足\(a_l,\cdots,a_{r-1}\le a_r\)，那么显然\([l,r)\)的人和第\(r\)个人绑定，答案不会更差。

因此先用单调栈维护一个\(a_i\)单调下降的序列，只考虑将这些人送到即可。

于是转移方程变为\(\displaystyle \min_{j<i}\{\max(f[j],t[i])+2\times a[j+1]\}\).

注意到\(f\)和\(t\)都是单调不降的，因此可以利用cdq分治。

随着\(i\)增大，\(f[j]\le t[i]\)的分界线不断右移

• 对于分界线左边的转移，为\(\min\{t[i]+2\times a[j+1]\}\)，又\(a\)单调递减，直接用最大的\(j\)去更新即可；

• 对于分界线右边的转移，为\(\min\{f[j]+2\times a[j+1]\}\)，预处理一个后缀最优值进行转移即可；

时间复杂度\(O(n\log{n})\).

F GCD

题目大意：给你 \(n\) 个 \(10^{18}\) 以内的正整数，给定非负整数 \(k\le\frac{n}{2}\)，问删去不超过 \(k\) 个数后，剩下的数的最大公约数最大能是多少。

题解：显然我们任取一个数，至少有 \(\frac{n-k}{n}\ge\frac{1}{2}\) 的概率在最优的 \(n-k\) 个数中。又有最终答案是这 \(n-k\) 个数的最大公约数，所以如果我们取到了这样的数，那么答案一定在这个数的约数中，容易知道答案一定是这些约数中最大的，且能够整除 \(n\) 个数中至少 \(n-k\) 个的那个约数。假如我们取 \(T\) 次，那么没有取到的概率小于等于 \((\frac{n-k}{n})^{T}\)，当 \(T\) 大于等于 \(20\) 的时候错误率已经在百万分之一以下。

下面我们考虑取到一个数后如何对它进行分解。首先我们计算出 \(10^{6}\) 以内的质数，并用它们来试除取到的这个数，设除剩下的数为 \(x\)，那么 \(x\) 有如下几种情况：\(1,p,p_{1}p_{2},p^{2}\)。之后我们将 \(x\) 与 \(n\) 个数分别做 \(gcd\)，若得到了一个 \((1,x)\) 的整数，那么我们就可以完成对后两种情况的分解。若没有得到这样的整数，在 \(x>1\) 时，我们直接将 \(x\) 看做一个质因子。第二种情况显然没有问题，而对于第三四种情况，相当于 \(p_{1}p_{2},p^{2}\) 在 \(n\) 个数中要么不出现，要么整体出现（即不单独出现 \(p_{1},p_{2},p\)），故不论如何进行 \(gcd\) 运算，它们都会同时出现/不出现，可以将它们看做一个质数。

下面考虑怎样求出每个约数能整除多少个数。暴力试除显然会 T，注意到对于 \(n\) 个数中的每个数，能够整除它的是它与取到的数的 \(gcd\) 的约数，于是我们可以用多维后缀和来统计，每一维代表一个质因子。具体实现时先把所有 \(gcd\) 求出并加 \(1\)，然后从后往前累加即可。

J Subsequence Sum Queries

题目大意：给你 \(n\) 个数和 \(q\) 次询问，每次询问一个区间，问这个区间中有多少子序列的和能被 \(m\) 整除。

题解：定义 \(f_{i}(x)=1+x^{a_{i}}\)，对于一个询问 \([l,r]\)，设 \(g(x)=\prod_{i=l}^{r}f_{i}(x)\)，那么显然答案为 \(\sum_{i=0}^{\infty}[x^{mi}]g\)。于是我们可以把这些多项式当做一个关于 \(x^{m}\) 的循环多项式来处理，答案即为 \([x^{0}]g\)。考虑到 FFT 的常数，我们暴力进行乘法，复杂度为 \(\mathcal{O}(m^{2})\)，特别地，进行关于 \(f_{i}(x)\) 的乘法时，由于只有两项非 \(0\)，复杂度为 \(\mathcal{O}(m)\)。我们离线处理所有询问，采用分治的办法，处理到一个区间时，从中点往左、右分别做 \(f_{i}\) 的后、前缀积，这部分的总时间复杂度为 \(\mathcal{O}(nm\log n)\)，对于跨过中点的询问，我们可以 \(\mathcal{O}(m^{2})\) 求出答案，其它的则分别到左右子树中处理，这部分的总时间复杂度为 \(\mathcal{O}(qm^{2})\)。

复杂度 \(\mathcal{O}(nm\log n+qm^{2})\)。