AtCoder Beginner Contest 189 题解

AC Codes

A – Slot

B – Alcoholic

C – Mandarin Orange

寻找直方图的最大矩形。

单调栈经典问题。

D – Logical Expression

给定一个长度为 $n$ 且只含有 AND 和 OR 的逻辑序列 $S$ ，询问满足：

\begin{aligned}x_0\ S_1, x_1\ S_2\ x_2\cdots S_n\ x_n=1\end{aligned}

的 $01$ 序列 $x$ 的数量（$x_i\ S_i\ x_{i+1}$ 表示 $x_i\ \text{AND}\ x_{i+1}$ 或者 $x_i\ \text{OR}\ x_{i+1}$）。

$n\leq 60$ 。

有一个比较显然的dp：假设 $dp[i][0/1]$ 表示到第 $i$ 位时逻辑表达式 $=0$ 或 $1$ 的合法逻辑序列数，转移方程如下：

1. $S_i=AND$ 时：
   \begin{aligned}
   dp[i][1] &= dp[i – 1][1]\\
   dp[i][0] &= dp[i – 1][0] \times 2 + dp[i – 1][1]
   \end{aligned}
2. $S_i=OR$ 时：
   \begin{aligned}
   dp[i][1] &= dp[i – 1][0] \times 2 + dp[i – 1][1]\\
   dp[i][0] &= dp[i – 1][1]
   \end{aligned}

E – Rotate and Flip

二维平面上有 $N$ 个点，现在有四种不同操作：

1. 将所有点绕坐标原点顺时针旋转 $90^\circ$。
2. 将所有点绕坐标原点逆时针旋转 $90^\circ$。
3. 给定 $p$ ，将所有点移动到关于 $x=p$ 的对称点。
4. 给定 $p$ ，将所有点移动到关于 $y=p$ 的对称点。

一共进行 $M$ 次操作，然后进行 $Q$ 次询问，每次询问第 $B_i$ 个点在第 $A_i$ 次操作后所在的坐标。

$N,M,Q\leq 2\times 10^9; -10^9\leq X_i,Y_i\leq 10^9$ 。

如果知道线性代数的话，就不难发现上述四种操作都可以看作是矩阵变换，假设初始某个点的坐标为 $(x,y)$ ，一共有如下四类矩阵变换：

1. 将所有点绕坐标原点顺时针旋转 $90^\circ$：
   $$ \begin{bmatrix} 0 & 1 \\ -1 & 0 \\ \end{bmatrix} \begin{bmatrix} x \\ y \\ \end{bmatrix}$$
2. 将所有点绕坐标原点逆时针旋转 $90^\circ$：
   $$\begin{bmatrix} 0 & -1 \\ 1 & 0 \\ \end{bmatrix} \begin{bmatrix} x \\ y \\ \end{bmatrix}$$
3. 给定 $p$ ，将所有点移动到关于 $x=p$ 的对称点：这种情况比较特殊，如果仅仅是对 $y$ 坐标轴做对称点的话，很容易写出：
   $$\begin{bmatrix}-1 & 0 \\0 & 1 \\ \end{bmatrix}\begin{bmatrix}x \\y \\ \end{bmatrix}$$

   但是由于现在是对 $x=p$ 作对称点，因此我们还需要加上一个偏移量，这个偏移量不难求出是 $2p$ ，因此最终结果为：

   $$\begin{bmatrix} -1 & 0 \\ 0 & 1 \\ \end{bmatrix} \begin{bmatrix} x \\ y \\ \end{bmatrix} + \begin{bmatrix} 2p \\ 0 \\ \end{bmatrix}$$
4. 给定 $p$ ，将所有点移动到关于 $y=p$ 的对称点：
   $$\begin{bmatrix} 1 & 0 \\ 0 & -1 \\ \end{bmatrix} \begin{bmatrix} x \\ y \\ \end{bmatrix} + \begin{bmatrix} 0 \\ 2p \\ \end{bmatrix}$$

然后我们就可以根据上述分析，建立一个结构体描述矩阵操作后点 $(x,y)$ 的变化（上述所有操作都只会将点 $(x,y)$ 改变为 $(a_0x+b_0y+c_0,a_1x+b_1y+c_1)$ ，因此我们只需要维护系数 $(a_0,b_0,c_0),(a_1,b_1,c_1)$ 在每次操作后的变化），就能够实现 $O(1)$ 查询了。

F – Sugoroku2

有 $N+1$ 个方格，下标为 $0,1,2,\ldots,N$ ，初始位于方格 $0$ 。现在有一个 $M$ 面的骰子，每一轮都会掷出一次，每一面朝上的概率相等，假设当前位于第 $j$ 个方格，骰子朝上的一面数值为 $i(1\leq i\leq M)$ ，那么就会跳跃到第 $j+i$ 个方格。当跳到了第 $N$ 个方格，或者跳出了边界后结束。

但是这些方格中有 $K$ 个特殊方格会直接将你传送回方格 $0$ ，询问跳跃结束的期望轮数。

$N,M\leq 10^5,K\leq 10$ 。

虽然很容易看出本题是吸收型马尔可夫链的典型模型，但是由于 $N$ 的范围较大，因此不可能建立矩阵求解。因此我们从传统的期望dp角度入手，设 $dp[i]$ 表示从方块 $i$ 出发结束跳跃的期望轮数，可以列出以下转移方程：

如果我们从 $i=N-1$ 开始逆推，不难发现最后一定会化作一个 $dp[0]=adp[0]+b$ 的方程，只需要一路维护系数 $a,b$ 即可解决本题。