NFLSPC #3 G 计算几何 题解

2020-11-26 16:39:11 By wzy

引理:答案为 $2n-2-$ 凸包上的点数。

首先证明这是答案的下界。设最外层凸包点数为 $l_1$,把这些点去掉,对于剩下的点再求一次凸包得到第二层凸包点数 $l_2$……以此类推,我们可以把这些点划分成 $k$ 个相互包含的凸包,点数分别为 $l_1,l_2,\cdots,l_k$。

对于相邻两层凸包之间的部分进行三角剖分,可以得到 $l_i+l_{i+1}$ 个三角形,最里面的凸包直接三角剖分,因此总共有 $(l_1+l_2)+(l_2+l_3)+\cdots+(l_{k-1}+l_k)+(l_k-2)=2n-2-l_1$ 个三角形,这些三角形两两没有交,因此这是答案的下界。

其次,存在一个构造可以达到这个下界。

随机一个向量 $p$,使得任意两个蓝点构成的向量不与 $p$ 平行,令 $|p| \rightarrow 0$,同时在每个点 $+p$ 和 $-p$ 位置放两个点,可以证明这 $2n$ 个点满足要求。

这是因为把一个三角形的三个角平移到一起刚好可以覆盖 $180$ 度,根据抽屉原理必然有一个点落在这里。

但是 $2n$ 个点多了,我们把所有在凸包外面的红点删掉(注意凸包最两侧的点可以删掉 $2$ 个红点),因此剩余的总点数恰好为 $2n-2-$ 凸包点数。

证毕。

上述引理的证明过程也给出了构造。复杂度瓶颈在于 spj,是 $O(n^3 \cdot ans)$ 的。

Bonus:把 spj 的复杂度降为 $O(n^2(n+ans))$。

NFLSPC #2 题解合集

2019-11-29 17:01:03 By wzy

NFLSPC #2 Game 题解

2019-11-29 16:51:32 By wzy

引理:两人若都采取最优操作方案,那么 Alice 的胜率等价于所有格子等概率随机颜色后,左边和右边连通的概率。

证明:

如果 Alice 在一个回合前知道 Bob 将会走哪个格子,那么假设他当前的策略也选这个格子,这样至少能够达到引理中胜利的概率,即所有格子颜色随机上下连通的概率。

同理,对于 Bob 来说也能够使用此策略达到“所有格子颜色随机左右连通的概率”的胜率。

因此考虑令 $x$ 为最终的期望得分,从 Alice 来看,$x \ge E($格子随机分配$)$,从 Bob 来看,$x \le E($格子随机分配$)$,因此 $x=E($格子随机分配$)$。

因此只需要计算所有格子颜色随机时,上下连通和左右连通的概率,插头 dp 即可。

NFLSPC #2 Magic 题解

2019-11-29 16:44:15 By wzy

先转曼哈顿,如果所有点的 $y=0$ 的话,那么任意一个匹配必然都经过 $x$ 的中位数(最大值的充要条件)。

取 $x$ 坐标的中位数 $a$ 和 $y$ 坐标的中位数 $b$ 得到点 $(a,b)$,然后以这个点为中心划分成一个十字,左上和右下匹配,左下和右上匹配即可。

假设 $n=2k$ 为偶数,那么左半边和右半边都有 $k$ 个,上半边和下半边也都有 $k$ 个。设左上有 $p$ 个,则右下有 $k-(k-p)=p$ 个,可以进行一一匹配;同理,左下也可以和右上进行一一匹配。

$n$ 为奇数时就记一下两维的前缀和,暴力计算出最优解应该删掉哪个点即可。复杂度瓶颈在 sort 上,$O(n \log n)$。

NFLSPC #2 LinQin 题解

2019-11-29 16:36:45 By wzy

$type=0$ 是给莫队的,$m \le 10^5$ 是给按序列分块的(不过好像没卡掉)

做法 1

把区间排序,最后的答案必然在相邻两项中产生。不妨考虑值域分块,即按照值所在的范围把原序列划分为若干个子序列。

不妨令块大小为 $B$,经过这样的划分之后,一次询问必然能分成 $\frac{n}{B}$ 个区间,每个区间在对应的值域块内。

对于每个值域块,用区间 dp 预处理出答案,复杂度 $O(nB)$;对于跨块的情况,不难发现只需要计算某个区间最大值和最小值,st 表即可。

因此总复杂度 $O(nB+\frac{nm}{B})$,$B=\sqrt {nm}$ 最优,复杂度 $O(n\sqrt m)$。

做法 2

考虑从前向后扫统计以当前位置结尾,每个位置作为开头的答案。不妨假设大的元素必然是靠后的那个,考虑找到当前前缀中最大的、且比当前位置小的数字,它能够产生一个前缀的贡献;再找到最大数字到当前数字这个区间中最大的、且小于当前的数字……一个一个更新计算贡献即可,贡献大概是个区间 set,可以用线段树维护。

这样的做法会被卡到 $O(n^2logn)$,因此可以思考一下性质。假设当前元素为 $x$,找到的最大值为 $a$,$a$ 右边找到的最大值为 $b(b < a < x)$。如果 $b$ 和 $x$ 计算了贡献,那么 $b$ 必须满足 $a \ge \frac{x+b}{2}$ 才能进行更新,否则 $a,b$ 会产生更优的贡献。

因此总共只需要更新 $O(\log 10^9)$ 个元素,强制在线可以用主席树维护区间 set,总复杂度 $O(n\log n\log 10^9)$。

wzy Avatar