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)$。

NFLSPC #2 Matrix 题解

2019-11-29 16:20:19 By wzy

不难发现合法矩阵的充要条件是每条从右上到左下的斜线上,没有相邻两个颜色相同的格子。

(应该很好证,就不说了)

于是答案就是 $k^{n+m-1}(k-1)^{(n-1)(m-1)}$,快速幂即可。

wzy Avatar