一二一站起来

全部题解-货物运输、货物分组、反杀

分类

题解(9)

/ 注册

题解-货物运输、货物分组、反杀

286 浏览 0 回复 2019-10-08

一二一站起来

+关注

T1 货物运输

部分分设置

对于30%我们可以直接暴力dfs是指数级复杂度。

对于50%的部分分，我留给某些可能的二分答案然后平方判断的做法。

对于一条链的情况，直接扫一遍就行。

正解思路

对于全部数据，我们首先对所有边按照边长排序。

然后对于一个连续的区间 $[l,r]$ 我们选了里面所有的边，代价是 $w[r]-w[l]$

我们枚举区间，然后使用并查集进行连通性判断。时间复杂度 $m^2\alpha(n)$

T2 货物分组

部分分设置

对于10%的数据，我们暴力枚举分组数以及分组情况。

对于30%的部分分，留给 $n^3$ 暴力DP

对于60%的部分分，我们稍后会介绍一个 $n^2$ 暴力DP

正解思路

首先考虑一个DP

$f[n][m]$ 表示前n个分成m组的最小花费。我们只要枚举 $k$ 之后 $f[n][m]=min\{f[k][m-1] m*(s(n)-s(k)) max(n~k 1)-min(n~k 1)\}$

这样转移是 $n^3$ 的。我们考虑使用先付代价来DP.

$f(n)$ 表示前n个分成若干组的最小代价。那么我们枚举k之后

$f(n)=min\{f[k] cost(k 1,n) sum\_all - sum(1~n)\}$

其中 $cost(l,r)$ 表示l~r的重量和加上其中最大值减最小值。

这样是 $n^2$ 的。

我们发现我们在转移过程中，可以用一个单调栈来维护最大值和最小值的变换，然后用线段树维护区间最值，就能每次 $\mathcal{O}(log\ n)$ 更新答案。

时间复杂度 $nlogn$

T3 反杀

部分分设置

对于 $10\%$ 的数据，我们暴力运算即可。

对于 $30\%$ 的数据，给一些有可能的与 $2^n$ 无关的做法。

对于 $50\%$ 的数据，给推出第一个式子的做法。

正解思路

对于这个式子，我们把他分开，分别计算左右两边，然后相乘就为答案。

我们先来看右半边，通过打表发现，它的取值只有0,-1,1三种。我们思考为什么会出现这种现象。

我们考虑对于式子 $f(x)=\sum_{k\leq m}\binom{m-k}{k}(-1)^k$ 我们使用扰动法找到它的递推式：

f(m)=\sum_{k\leq m}\binom{m-k}{k}(-1)^k\\ =\sum_{k\leq m}\binom{m-1-k}{k}(-1)^k \sum_{k\leq m}\binom{m-1-k}{k-1}(-1)^k\\ =\sum_{k\leq m}\binom{m-1-k}{k}(-1)^k \sum_{k 1\leq m}\binom{m-2-k}{k}(-1)^{k 1}\\ =\sum_{k\leq m-1}\binom{m-1-k}{k}(-1)^k \binom{-1}{m}(-1)^m-\sum_{k\leq m-2}\binom{m-2-k}{k}(-1)^k - \binom{-1}{m-1}(-1)^{m-1}\\ =f(m-1) (-1)^{2m}-f(m-2)-(-1)^{2(m-1)}=f(m-1)-f(m-2)

显然对于 $m\geq 3$ 都有 $f(m)=(f(m-2)-f(m-3))-f(m-2)=-f(m-3)$ 高中数学告诉我们这是一个周期为6的函数。我们把它前6项找出来，分别是1,1,0,-1,-1,0.

那么对于 $2^n$ 当 $n=0$ 时， $f(2^n)=1$ . 当 $n$ 为奇数时， $f(2^n)=0$ . 当 $n$ 为偶数时， $f(2^n)=-1$

右边的式子解决了，我们来看左边的式子。

$LHS=\sum_{k=0}^{n}k\binom{m-k-1}{m-n-1}$

我们把 $k$ 换成 $\binom{k}{1}$

那么我们有 $LHS = \sum_{k=0}^n\binom{k}{1}\binom{m-k-1}{m-n-1}$

我们考虑一个这样的式子 $\sum_{k=-q}^l\binom{l-k}{m}\binom{q k}{n}$ 它实际上等于 $\binom{l q 1}{m n 1}$ 考虑他的组合意义易证。

那么 $LHS = \sum_{k=0}^n\binom{k}{1}\binom{m-k-1}{m-n-1}$ 是满足上面的形式的，所以 $LHS=\binom{m}{m-n 1}$

那么左右两边我们都已经可以得到封闭形式了。 $Ans=\binom{m}{m-n- 1}*g(n)$

其中 $g(n)=1*[n=0] -1*[n>0 \and 2|n]$

我们发现 $p$ 很小，并且是个素数，考虑 $Lucas$ 定理，时间复杂度 $\mathcal{O}(p Tlog_pn)$

举报

收藏

赞

评论加载中...