2020 年 9 月刷题日志

CF1384B2 Koa and the Beach

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

海里每一个位置都有一个深度，而且水里随着时间有锯齿状周期为 $2k$ 的潮汐。

当潮汐与深度之和大于给定值 $l$ 时 Koa 会溺水，游泳、海岸、岛上永远是安全的。

在任意时间 Koa 可以选择游到 $x+1$ 或停留在 $x$，试问 Koa 是否能够安全的从海岸 $0$ 到达岛上 $n+1$。

开始的想法是随着时间 DP，更好的解法是贪心。

若一个位置在水位最高时仍不会溺水，则称这个位置是安全的，并且可以任意选择出发时机。

即安全位置之间是相互独立的，我们只需判断可达性，尽量到达每一个安全位置。若之后 $2k$ 个位置没有安全位置，必死。

Koa 的最优决策是在刚退潮时出发，如果能走就尽量往前走，不能走就等，等到涨潮就说明不存在通过方法。

洛谷 P1004 方格取数

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

在 $n\times n$ 的方格（$n⩽9$）中存在一些正整数，经过格子时获得格子上的数，但只能获得一次，第二次走过不获得。

某人只能向右或向下走，从格子的左上角走到到右下角，共走两次，求最大能取得的数字。

考虑把先走后走转化为两个人同时走，只需要处理遇到两次的值即可。

考虑四维 DP，用 $dp[x_1,y_1,x_2,y_2]$ 表示第一个人走到 $(x_1,y_1)$ 和第二个人走到 $(x_2,y_2)$。

再考虑转移，每一个位置仅可能从其左面或上面转移来，于是可以写出（$x_1\ne y_1$ 或 $x_2\ne y_2$ 时）

$$dp[x_1,y_1,x_2,y_2]=max\left\{\begin{array}{c}dp[x_1-1,y_1,x_2-1,y_2]\\ dp[x_1,y_1-1,x_2-1,y_2]\\ dp[x_1-1,y_1,x_2,y_2-1]\\ dp[x_1,y_1-1,x_2,y_2-1]\end{array}\right\}+a[x_1,y_1]+a[x_2,y_2]$$

当 $x_1=y_1,x_2=y_2$ 时，只加一次即可。到这里 $O(n^4)$ 其实已经可以过题了，但还可以优化。

注意到一些状态是不可达的，因为 $x_1+y_1=x_2+y_2$，因此存在 $O(n^3)$ 的 DP。

考虑当前已走长度 $h=x_1+y_1=x_2+y_2$，于是可以把两个人的座标表示为 $(x_1,h-x_1)$ 和 $(x_2,h-x_2)$。

于是记状态为 $dp[h,x_1,x_2]$，当 $x_1\ne x_2$ 时有

$$dp[h,x_1,x_2]=max\left\{\begin{array}{c}dp[h-1,x_1,x_2]\\ dp[h-1,x_1,x_2-1]\\ dp[h-1,x_1-1,x_2]\\ dp[h-1,x_1-1,x_2-1]\end{array}\right\}+a[x_1,h-x_1]+a[x_2,h-x_2]$$

再注意到可以使用滚动数组。

洛谷 P2181 对角线

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

凸 $n$ 边形中，任意三条对角线不共点，求所有对角线交点的个数。

注意到一个交点对应凸多边形 $4$ 个定点，于是等价于 $n$ 个点任选 $4$ 个点的选法种数，即

$$(\genfrac{}{}{0ex}{}{n}{4})=\frac{n(n-1)(n-2)(n-3)}{24}$$

注意爆 long long，需要写成 n * (n-1) / 2 * (n-2) / 3 * (n-3) / 4。

洛谷 P1042 乒乓球

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

赢 11 分并且压对手两分以上则一局结束，否则要追分至压对手两分。

给定 $\mathtt{\text{WL}}$ 序列，分别求 11 分制和 21 分制下每场比分，$\mathtt{\text{E}}$ 是结束符。

这是一道比较烦的模拟题，很绕。