Contest Info

date: 2018.11.17 12:51-17:51

practice link

Solutions

B. Craters

题目大意：

二维平面上有\(n\le2\times10^5\)随机的整点，求最大三角形的面积。

题解：

最大三角形一定是凸包上的点组成的，先求个凸包，因为数据随机，凸包上的点个数很少，暴力枚举一下就行。

C. MSTrikes back!

题目大意：

略。

题解：

五个点的连通状态只有\(52\)种，打表发现生成器的周期为\(54\)，于是矩阵乘法快速幂搞定。

时间复杂度\(O(s^3\log{n}+T\cdot s^2\cdot2^{5})\).

D. Skyscrapers

题目大意：

略。

题解：

每次二分找到会影响的区间，用线段树维护\(a_i-i\)和\(a_i+i\)，然后暴力删除即可。

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

F. Buddy Numbers

签到题。

H. Generator

签到题。

I. Addition

题目大意：

略。

题解：

等价于求大于\(x\)的按位取反后的二进制数的个数，直接Trie.

时间复杂度\(O(nm)\).

K. GCD on the segments

题目大意：给你一个数列 \(a\)，要求你将它分成尽可能多互不相交的区间，使得每个区间的 \(\gcd\) 相同，并求出这样的方案数。

题解：枚举 \(\gcd\)。将所有不被 \(\gcd\) 整除的数删去，对剩余的每个区间单独求解。问题转化为划分为尽可能多的区间使得 \(\gcd=1\)。

显然如下的贪心是正确的：从第一个数开始，选取尽可能少的数使得 \(\gcd\) 为 \(1\)，然后从后面一个数开始继续贪心。

那么我们可以用 \(dp1[i]\) 表示从 \(i\) 开始选取，最多有多少个区间。

然后用 \(dp2[i]\) 表示从 \(i\) 开始（\(i\) 必选），选取 \(dp1[i]\) 个区间的方案数。枚举 \(i\) 对应的右端点，以及下一个左端点即可。注意下一个左端点 \(j\) 的 \(dp1[j]\) 必须恰好等于 \(dp1[i]-1\)，否则不满足最大值的要求。之后用前缀和优化即可。

时间复杂度 \(\mathcal{O}(n\log^{2}n+n\max\{\sigma(a_{i})\})\)。

L. Fibonacci Equation

签到题。