WHEZOJ Easy Round 2 题解

Sengxian 于 2016-11-14 13:40:09 发表,2017-04-07 21:35:38 最后更新

挖金矿

40 分

n,m5n, m\le 5

暴力 DFS 每列挖的深度。

复杂度 O(nm+mnm)O(nm + mn^m)

80 分

m=1m = 1

由于只有一列,枚举挖的深度即可。

复杂度 O(nm+n)O(nm + n)

结合上面的算法可以获得 80 分。

100%

n,m300n, m\le 300

考虑二分答案 xx,那么答案不小于 xx 的充要条件就是(设 hih_iii 列下挖的深度,si,js_{i, j} 为第 jj 列前 ii 个数的和):

1imshi,i1imhix \frac{\sum_{1\le i\le m}s_{h_i, i}}{\sum_{1\le i\le m}h_i}\ge x

考虑将分母的和式乘过去:

1imshi,ix1imhi \sum_{1\le i\le m}{s_{h_i, i}}\ge x\sum_{1\le i\le m}h_i

移项:

1imshi,ixhi0 \sum_{1\le i\le m}{s_{h_i, i} - x\cdot h_i}\ge 0

于是对于每一列,贪心选择最大的 shi,ixhis_{h_i, i} - x\cdot h_i,即可在 O(nm)O(nm) 的时间内判断出答案。

复杂度:O(nmlogV)O(nm\log V)

标程

std

切割字符串

40 分

n,m20,k=1n, m\le 20, k = 1

由于 k=1k = 1,那么枚举 ss 的所有子串,判断是否在 tt 中出现即可。

复杂度 O(n2(n+m))O(n^2(n + m))

80 分

n,m20,k=2n, m\le 20, k = 2

由于 k=2k = 2,枚举 ss 的两个不相交子串即可。

复杂度 O(n4(n+m))O(n^4(n + m))

结合上面的算法可以获得 80 分。

100 分

这个形式,很像最长公共子序列,我们考虑 DP。

f[i][j][k]f[i][j][k] 为考虑 ss 的前 ii 个,tt 的前 jj 个,选出 kk 个相等的字符串的最大长度和。

我们考虑转移,f[i][j][k]f[i][j][k] 显然可以从 max(f[i1][j][k],f[i][j1][k])\max (f[i - 1][j][k], f[i][j - 1][k]) 转移。

考虑 f[i][j][k]f[i][j][k] 与之前状态的异同点,如果 ,那么这个状态与 max(f[i1][j][k],f[i][j1][k])\max (f[i - 1][j][k], f[i][j - 1][k]) 没有任何不同。

如果 si=tjs_i = t_j 的话,那么 f[i][j][k]f[i][j][k] 就可以从 f[i1][j1][k1]f[i - 1][j - 1][k - 1] 转移。再考虑 si=tjs_i = t_j 不做新字符串开头的情况,这时我们需要 si1,tj1s_{i - 1}, t_{j - 1} 也能对上,所以定义 g[i][j][k]g[i][j][k] 为在 f[i][j][k]f[i][j][k] 的基础上,强制使 sis_itjt_j 对上号。

转移十分清晰:

f[i][j][k]=max{f[i1][j][k]f[i][j1][k]max(f[i1][j1][k1],g[i1][j1][k])+1si=tj f[i][j][k] = \max\begin{cases}f[i-1][j][k]\\f[i][j-1][k]\\\max(f[i -1][j-1][k-1], g[i-1][j-1][k]) + 1& s_i = t_j\end{cases} g[i][j][k]={max(f[i1][j1][k1],g[i1][j1][k])+1si=tjotherwise g[i][j][k] = \begin{cases}\max(f[i -1][j-1][k-1], g[i-1][j-1][k]) + 1 & s_i= t_j\\-\infty &\text{otherwise}\end{cases}

标程

std

消灭敌人

30 分

n20n\le 20

枚举需要开炮的敌人,然后判断是否所有敌人都能被消灭。

复杂度:O(n2n)O(n\cdot 2^n)

50 分

由于所有敌人都会在同个时间存在,那么只需要向最远的敌人开一炮即可。

结合上面的算法可获得 50 分。

100 分

我们把敌人 ii 出现的时间看做线段 [ai,bi][a_i, b_i],分析可知一定存在最优方案,使得开炮只需要在端点处开炮,所以可以离散化 ai,bia_i, b_i

对于最远的敌人来说,必须要向它开一炮,所以我们可以考虑枚举消灭最远的敌人的开炮位置,然后递归处理就可以了。

dp[i][j]dp[i][j] 为处理所有被包含在 [i,j][i, j] 内的敌人所需要的最小代价,如果离散化出 mm 个节点,则 dp[0][m1]dp[0][m - 1] 为答案。如果 [i,j][i, j] 无完整的线段,则 dp[i][j]=0dp[i][j] = 0

xx[i,j][i, j] 内距离最远的敌人,则:

dp[i][j]=minaxkbx(dp[i][k1]+dp[k+1][i]+dx) dp[i][j] = \min_{a_x \le k \le b_x}(dp[i][k - 1] + dp[k + 1][i] + d_x)

显然所有包含 kk 这个时间点的线段全部被武器打死(因为我们是使用的威力最大的武器),而 dp[i][k1],dp[k+1][i]dp[i][k - 1], dp[k + 1][i] 不会完整包含这些被武器打死的线段,所以这个转移是正确的。

复杂度:O(n3)O(n^3)

标程

std

迷宫

30 分

n,m30n, m\le 30

模拟一下人走的情况。

60 分

n,m2000n, m\le 2000

注意到,由于每次只能删除一个人,所以加入的总人数一定是 O(m+n)O(m + n) 的。

我们考虑将每个点连出的边按照到达的点的标号从小到大排序,那么,nn 个人依次进入,最后到达的点的顺序就应该是这棵树的后序遍历。

考虑加入一个人,我们应该找到后序遍历中第一个空位,将人放入这个空位。

考虑删除位置 uu 上的人,删除后,由于后面的人会补上去,所以实际上是删除了 uu 到根的路径上,深度最小的有人的位置,我们暴力的找到这个位置即可。

上面两个操作复杂度都是 O(n)O(n),总复杂度 O(n(n+m))O(n(n + m))

100 分

考虑优化加入一个人,只需要用优先队列维护空位置即可,复杂度降为 O(logn)O(\log n)

考虑优化删除位置 uu 上的人,uu 到根的路径上有人的位置一定是连续的,所以我们只需要知道 uu 到根的路径上有多少个有人的位置即可,假设到根的路径上有 xx 个人,那么实际上删除的位置是 uu 向上 x1x - 1 个位置。找这个位置可以采用树上倍增,复杂度 O(logn)O(\log n)

总复杂度 O((n+m)logn)O((n + m)\log n)

标程

std