CF719 (Div. 3) 题解

[toc]

AC代码

A. Do Not Be Distracted!

B. Ordinary Numbers

定义普通数为：数位上所有数字相同的数。多组询问，询问 $N$ 以内的普通数数量。

$N\leq 10^9$ 。

这样的数字显然很少，直接暴搜出数据范围内的所有普通数，每个询问二分查找即可。

C. Not Adjacent Matrix

构造一个 $N\times N$ 的矩阵，将 $1,2,\cdots, N^2$ 填入该矩阵，使得该矩阵中不存在任意两个相邻单元（四联通）中的数差值大于一。

$N\leq 100$ 。

显然 $N=2$ 无解，其他情况构造按照奇偶染色的方法进行即可，以 $N=4$ 为例：

1 9 2 10
11 3 12 4
5 13 6 14
15 7 16 8

D. Same Differences

给定一个大小为 $N$ 的数列 $A$ ，求满足 $a_j-a_i=j-i(j>i)$ 的 $(i,j)$ 对数。

$\sum N\leq 10^6$ 。

移项后得到 $a_j-j=a_i-i$ ，令 $p_i=a_i-i$ ，答案就是 $\sum \binom{cnt(p_i)}{2}$ ，$cnt(p_i)$ 表示 $p_i$ 的个数。

E. Arranging The Sheep

给定一个长度为 $N$ 的字符串 $S$ ，有两种字符：* 表示羊，. 表示空格。你可以让每只羊向左或右移动一个单位到他相邻的空格单元，询问最少移动几次能让所有羊在一个连续的相邻线段上。

$\sum N\leq 10^6$ 。

由于最后所有的羊是连续的，因此最少代价是 $\sum_{i=0}^{n-1}|a_i-i-d|$ ，$a_i$ 代表羊的初始位置， $d$ 代表移动后第一只羊的位置。由于 $a_i-i$ 是一个定值，因此本题实际上就是求 $\sum_{i=0}^{n-1}|p_i-d|$ 的最小值（$p_i=a_i-i$）。这是一个经典的绝对值不等式问题，结论就是取中点时最小。

F1. Guess the K-th Zero (Easy version)

F2. Guess the K-th Zero (Hard version)

交互题，有一个长度为 $N$ 的 $01$ 串，每次你可以询问 $[l,r]$ 区间内的 $1$ 的数量，询问第 $K$ 个 $0$ 的位置？

Easy Version：$N\leq 2\times 10^5$，询问次数 $\leq 20$。

Hard Version：$N\leq 2\times 10^5$ ，有 $T(T\leq 10^4)$ 次询问，询问次数 $\leq 6\times 10^4$ ，每次询问过后，当前询问的第 $K$ 个零会变成一。

$Easy Ver$ 是个明显的二分搜索，不再赘述。

$HardVer$ 乍一看没什么想法，但是观察一下数据范围感觉就是二分加点记忆化的剪枝。实际上官方题解也就是证明了我们直接二分每个询问并记忆化一下进行剪枝的询问次数是不会超过 $6\times 10^4$ 的，我自己就懒得证明了。

G. To Go Or Not To Go?

给定一个 $N\times M$ 的网格图，每个方格上有一个数字 $X$ ，有以下三类格子：

1. X=-1 的格子是障碍物，无法通行；
2. X=0 的格子是一般格子，可以花费 $w$ 点代价移动至四联通方向上的任意一个格子（非障碍物）；
3. X>0 的格子是传送门，你可以从一个传送门直接移动至任意一个传送门，花费的代价是两个传送门的权值之和，但你也可以无视传送门花费 $w$ 点代价移动至四联通方向上的任意一个格子（非障碍物）。

询问从 $(0,0)$ 移动至 $(N-1,M-1)$ 的最小代价。

$N,M\leq 2000$ 。

由于传送一次的代价是两端传送门的权值，因此我们最多只会进行一次传送（$A\rightarrow B$ 的权值显然小于 $A\rightarrow C,C\rightarrow B$）。

因此本题有两种情况：

1. 不走传送门：直接BFS就行。
2. 走一次传送门：最优方案一定是从起点走到权值最小的传送门+从终点走到权值最小的传送门，某个传送门的权值是 传送门本身的权值+从起点/终点到达这个传送门的花费 。因此只需要BFS两次，然后取出最小值就行。

上述两种方案取 $\min$ 即可。