Contest Info

date: 2019.02.16 10:00-15:00

practice link

Solutions

C. Concatenation

题目大意：给定一个小写字母串\(S\)，\(|S|\le5000\)，定义\(T(S)\)为\(S\)的所有子串（和子区间一一对应）按字典序从小到大排列后首尾相连成的串。\(m\le5000\)次询问，每次给出一个整数\(1\le a_i\le|T(S)|\)，问\(T(S)\)的第\(a_i\)个字符是多少。

题解：通过后缀自动机建立后缀树，同时预处理出子树总长度和每个节点的出现次数，然后从根开始二分找到要走的边，如果终止在这条边上，需要再二分这条边走了多少次，时间复杂度\(O(nm\log{n})\).

D. Dictionary

题目大意：给定一个长度为\(n\le3000\)的小写字母串。问有多少种方案，将其划分成若干个不相交的子区间，并且这些子区间的字符串字典序严格单调递增。

题解：令dp[i][j]表示前缀\(i\)，最后一个子区间长度为\(j\)的方案数。从小到大枚举\(i\)转移，用sais对前缀\(i\)的所有后缀排序，然后通过预处理sa和st表求lcp比较大小的方式和后缀\(i+1\)的所有前缀边归并边转移即可。时间复杂度\(O(n^2)\).

K. Rectangles

题目大意：给你一个 \(n\times n\)（\(n\le 300\)）的矩阵，元素在 \([-10^{9},10^{9}]\) 之间，求所有子矩形的 \(\frac{所有元素之和}{周长}\) 的最大值。

题解：容易想到，我们枚举一维的区间，然后二分答案，这样以后很容易 \(\mathcal{O}(n)\) check。复杂度为 \(\mathcal{O}(n^{3}\log\frac{A}{\varepsilon})\)。这个复杂度过高，我们现场没有卡过，但是似乎有人卡过去了。

这里介绍一种更好的二分方法，这种方法适用于：我们要做 \(n\) 次二分，取 \(n\) 次答案的最值，但是这 \(n\) 次二分并不需要按特定的顺序进行。

我们采取这样的策略，假设当前的最大值为 \(M\)，二分之前我们先 check 一下这次二分能否得到大于 \(M\) 的值，如果不能，显然这次二分就没有必要再做了。

考虑到如果这 \(n\) 次二分的答案是严格递增的，那么我们仍然要做 \(n\) 次二分，复杂度并没有变优。我们可以把这 \(n\) 次二分进行的顺序先 shuffle 一下，可以证明这样期望只需要做 \(\log n\) 次二分，复杂度降为了 \(\mathcal{O}(n+\log n\log A)\)，有了较大的改善。

本题采用这种方法，复杂度为 \(\mathcal{O}(n^{3}+n\log n\log\frac{A}{\varepsilon})\)，可以很容易通过。

L. Christmas Tree

题目大意：二维平面上有\(n\le50000\)个点，每个点有个高度\(h_i\)，两两不同。如果当前Vasya处于点\(i\)，而\([x_i-h_i,x_i+h_i]\times[y_i-h_i,y_i+h_i]\)范围中\(h_i\)最大的点\(j\not=i\)，那么 Vasya会移动到点\(j\)。问Vasya一开始在哪个点可以使得最终位置的高度最小。

题解：直接kd树判断每个点是否可以作为终点更新答案即可，时间复杂度\(O(n\sqrt{n})\).