2020 年 10 月刷题日志

P1095 守望者的逃离

2020-10-09 | 题目链接 | </> 代码

守望者的可以在一秒逃出 $17\mathrm{m}$，或者消耗 $10$ 点魔法值闪现 $60\mathrm{m}$。原地休息时每秒回复 $4$ 点魔法值。

守望者开始有 $M$ 点魔法，需要在 $T$ 秒内逃离距离 $S$。若能逃离则求最短逃离时间，否则求最远距离。

设 $s_1$为一直走路，$s_2$ 为一直闪现恢复。当 $s_2$ 快了就把 $s_1$ 更新为 $s_2$。

P5143 攀爬者

2020-10-13 | 题目链接 | </> 代码

在三维空间中，HKE 只能往上走，求攀爬总长。

对所有座标的 $z$ 分量排序即可。

P1923 求第 $k$ 小的数

2020-10-16 | 题目链接 | </> 代码

给定数列，求第 $k$ 小的数。

模板题。考虑分治，随便选一个数 $x$，然后把比 $x$ 大的数移到右边，比 $x$ 小的数移到左边。因此得到了数 $x$ 的排位，若恰为第 $k$ 个则返回，否则根据大小在左右寻找。

该算法是不稳定的，期望复杂度 $O(n)$，最坏复杂度 $O(n^2)$。

实际上存在最坏复杂度为 $O(n)$ 的 BFPTR 算法，但因为其常数过大实现复杂而很少应用。

P1928 外星密码

2020-10-16 | 题目链接 | </> 代码

我们将重复的 $n$ 个字符串 S 压缩为 [nS]，且存在多重压缩。给定一个压缩结果，展开它。

我考虑用类似状态机的方式解析字符串。

• 当读到正常字符时，把它添到 $s$ 末尾
• 读到左括号时，则递归 read()，重复 $n$ 遍添到 $s$ 末尾
• 右括号或文本结束则返回 $s$

写成 BNF 更直观一点

<pwd> ::= <EMPTY>
  | {<ALPHA>}
  | <pwd> "[" <NUMBER> <pwd> "]" <pwd>

P1990 外星密码

2020-10-16 | 题目链接 | </> 代码

有 I 形和 L 形两种砖头，分别能覆盖 2 个单元和 3 个单元。求 $2\times n$ 的墙有多少不重复的覆盖方式，结果对 ${10}^4$ 取模。

其中 I 形砖块仅有横放和竖放两种。关键在于 L 形，两个 L 形之间可以用 I 形填充，这让情况变得复杂起来。

对于 $F_n$ 的递推，我们可以想到

• 在 $F_{n-1}$ 后放一个 I 形砖块。
• 在 $F_{n-2}$ 后放两个横着的 I 形砖块。
• 对于更前面的递推，较为复杂。
  • 两个 L 形砖块对齐，上下翻转也可以，即 $2F_{n-3}$。
  • 两个 L 形砖块可以对顶放，空缺恰用一个 I 填充，即 $2F_{n-4}$。
  • 类似 $2F_{n-3}$，中间可以再插入两个 I 形，即 $2F_{n-5}$。
  • ……
  • 直到 I 形和 L 形砖块恰好铺满墙壁，即 $2F_0$。

容易得到我们的递推式

$$F_n=F_{n-1}+F_{n-2}+2\sum _{i=0}^{n-3}{F}_i$$

利用错位相减法，不难化简得到

$$F_n=2F_{n-1}+F_{n-3}$$

P1090 合并果子

2020-10-16 | 题目链接 | </> 代码

可以合并两堆果子成一堆新果子，消耗两堆果子数目之和的体力。给定 $n$ 堆果子的数目 $a_i$，求体力耗费最小的方案。

很容易猜到贪心结论，不断选取两个最小的堆进行合并。

本质上是证明 Huffman 树的构造的正确性，有点复杂。

P4995 跳跳

2020-10-16 | 题目链接 | </> 代码

给定石头的高度 $h$，从第 $i$ 块石头跳到第 $j$ 块上耗费体力 $(h_i-h_j{)}^2$ ，求最耗体力的路径。

容易猜到贪心结论，是不断的在剩余石头中最大最小的来回跳。

考虑证明结论，设 $h_i$ 是将要跳的序列，展开求和式

$$S=\sum _{k=1}^{n-1}(h_k-h_{k+1}{)}^2=\sum _{k=1}^n{h}_k^2-2\sum _{k=1}^{n-1}{h}_k{h}_{k+1}$$

注意到平方和为一个定值，重点在后半式。记 $H_k=h_{k+1}$，有

$$\sum _{k=1}^{n-1}{h}_k{H}_k$$

利用高中时学的排序不等式，有

$$\text{反序和}⩽\text{乱序和}⩽\text{顺序和}$$

于是有反序最小。双指针维护即可。

P1077 摆花

2020-10-16 | 题目链接 | </> 代码

要从 $n$ 种花中挑出 $m$ 盆展览，其中第 $i$ 种花不得多于 $a_i$ 种。求有几种选法。

考虑动态规划，记状态 $dp[i,j]$ 为摆完前 $i$ 种花，共 $j$ 盆时的方案数。容易得到递推式

$$dp[i,j]=\sum _{k=j-min(a_i,j)}^{j}dp[i-1,k]$$

边界条件是 $dp[0,0]=1$。可以用滚动数组、前缀和优化。