题目列表
- 「Prefix Sum」
- 「Bead」
- 「Train」
- 「监视 G 房」
A. 「Prefix Sum」
很容易推出答案的式子 $C_{n+m-1}^{n-1}$
考虑证明答案的正确性:对于一个数,每次做前缀和时会对后面的数做出贡献,那么问题转化为:一个数向后跳 $m$ 次(做 $m$ 次前缀和),也可以不跳,总共要跳 $n$ 步(对后面所有数字做出贡献),求方案数。(当然也可以像我一样打表找规律)
则有 $\sum_{i=1}^m x_i=n\quad(x_i\geqslant 0)$,用插板法可以求解。如果暴力计算组合数,时间复杂度为 $O(m)$ 可以得到 $60$ 分。
其实正解只是优化了答案的式子。
上述式子的分子分母项数都是 $O(n)$ 级别的。
时间复杂度:$O(n)$
代码
1 |
|
B. 「Bead」
显然此题为动态规划,$f[i][j]$ 表示已经分了 $i$ 段,最后一次分割在 $j$ 的后面,状态转移方程为:
$f[i][j]=\min(f[i][j],f[k][j-1]+res[k+1][i])\quad(0\le k<i)$
其中 $res[i][j]$ 表示 $i\sim j$ 的价值。初始化为 $f[0][0]=0$ 其余为 $\infty$。
很显然状态已经无法优化了,考虑转移优化。其实这个状态转移方程满足决策单调性,因此我们可以整体二分求解。
记 $nl$ 和 $nr$ 为当前状态 $l$ 和 $r$ 的最优决策段,当 $l=r$ 时直接在 $f[k-1][nl\sim nr]$ 转移即可,否则求出 $mid=(l+r)/2$ 的在当前决策的最优决策点,接下来递归求解 $[l,mid-1]$ 和 $[mid+1,r]$。
时间复杂度:$O(n\log n)$
代码
1 |
|
C. 「Train」
对于每列火车,我们可以将其路线拆成 $x\rightarrow LCA\rightarrow y$。若我们在 $x\sim LCA$ 这部分上车,那么肯定不是最优的(在到达 $x$ 之前,$x\sim LCA$ 肯定都到达过)。故我们可以将所有线路变成 $LCA\rightarrow y$,即为许多向下的链。
我们又可以把线路转化为从 $1$ 出发到 $y$(虽然 $1\sim LCA$ 并不存在,但是这样方便排序),根据新的出发时间排序(如果时间相同则按照深度排序),如果当前时间是可达的则说明这列火车可以被乘坐,于是我们把 $LCA$ 到 $y$ 的点都标记为可达的。标记时从下到上标记,遇到已经标记过的点就退出(如果 $x$ 被标记,那么 $1\sim x$ 肯定都被标记了)。
时间复杂性:$O(m\log n)$
代码
1 |
|
D. 「监视 G 房」
树形 $\text{DP}$,记 $f[i][0,1,2]$ 分别表示第 $i$ 个结点 只有父亲、只有儿子、只有自己 放摄像头的最小数量,$g[i][0,1,2]$ 为其方案数。
对于树形 $\text{DP}$ 的具体实现见下方代码(虽然没有注释,但是所有代码的含义都是字面意思)。
时间复杂度:$O(n)$
代码
1 |
|