ABC203 题解

[toc]

AC代码

A – Chinchirorin

B – AtCoder Condominium

C – Friends and Travel costs

D – Pond

给定一个 $N\times N$ 的矩阵，寻找一个中位数最小的 $K\times K$ 大小的子矩阵，求出这个最小的中位数。

$K\leq N\leq 800,a_i\leq 10^9$ 。

根据中位数的性质：至少有一半的数 $\geq$ 中位数，因此我们二分答案中位数 $mid$ ，将大于 $mid$ 的所有 $A_{i,j}$ 置为 $1$ ，然后每次利用二维前缀和 $O(N^2)$ 检查是否存在某个子矩阵的和超过 $\frac{K^2}{2}$ 。

E – White Pawn

有一个 $(2N+1)\times (2N+1)$ 的网格图，网格图上有 $M$ 个黑色单元格，其余格子为白色。你的起点在 $(O,N)$ ，有以下三种移动方式：

• 从 $(i,j)$ 移动到 $(i+1,j+1)$ ，此时必须满足 $(i+1,j+1)$ 是白格。
• 从 $(i,j)$ 移动到 $(i+1,j-1)$ ，此时必须满足 $(i+1,j-1)$ 是白格。
• 从 $(i,j)$ 移动到 $(i+1,j+1)$ ，此时必须满足 $(i+1,j)$ 是黑格。

你只能在网格图内部按照上述规则移动，当你移动到 $x=2N$ 时结束移动，此时你的坐标可以表示为 $(2N,y)$ ，询问所有合法的 $y$ 构成的集合大小。

$N\leq 10^9,M\leq 2\times 10^5$ 。

注意到我们只能从左向右前进，并且合法的 $y$ 数量不会超过 $2M+1$ ，因此可以直接模拟从左到右这一流程。

将所有黑格按照x坐标为第一关键字存入map，假设 $x=i$ 时，当前合法 $y$ 的集合为 $(y_0,y_1,\ldots,y_k)$ ，那么往 $i+1$ 走时我们只需要检查：

1. 单元格 $(i+1,y_i)$ 是否是黑色格，如果是，则从集合中移除 $y_i$ 。
2. 单元格 $(i+1,z_i)$ 如果是黑色格，同时 $(i,z_i-1)$ 和 $(i,z_i+1)$ 是合法的（$z_i-1\in y$ 或 $z_i+1\in y$），就在集合中加入 $z_i$ 。

由于黑色格子数量较少，因此上述模拟的复杂度是 $O(M\log M)$ ，可以通过本题。

F – Weed

给定一个大小为 $N$ 的数列 $A$ ，Aoki最多能从该数列中拿走 $K$ 个数，Aoki拿走一些数后Takahashi将重复进行以下操作，直到数列为空：

• 设当前数列中最大的数字是 $A_i$ ，拿走所有大小严格大于 $\lfloor\frac{A_i}{2}\rfloor$ 的数。

请问Takahashi的最少操作次数，同时询问在Takahashi最少操作的情况下，Aoki最少取走几个数。

$K\leq N\leq 2\times 10^5,1\leq A_i\leq 10^9$ 。

本题最关键的地方是注意到Takahashi每次都会将当前数列的上限折半，因此他的操作次数上限是 $O(\log(\max A_i))$ 量级的，经计算后可知最多30次操作。

因此通过dp解决本题，设 $dp[i][j]$ 表示前 $i$ 个数，Takahashi操作 $j$ 次后结束的情况下，Aoki最少取走几个数，不难得出转移有两种情况：

上式中 $pos(\frac{A_i}{2})$ 表示数列 $A$ 中 $\frac{A_i}{2}$ 的下标（如果不存在 $\frac{A_i}{2}$ 则返回小于 $\frac{A_i}{2}$ 的最大值下标）。显然pos数组可以通过排序+二分的方法预处理。

dp的初值是 $dp[i][0]=i,dp[0][i]=0$ 。