CFR-745-Div.2解题报告

没打比赛，赛后做出3道。
这场比赛题目质量很高，非常巧妙。

A. CQXYM Count Permutations

$Problem$

求有多少 $2n$ 的排列满足存在超过 $n$ 个 $i$ 使得 $p_i<p_{i+1}$，答案对 $10^9+7$ 取模。

$\sum n\le 10^5$

$Solution$

这题就非常巧妙了，当我们使劲想想不出来时，正难则反，考虑有多少 $2n$ 的排列满足存在超过 $n$ 个 $i$ 使得 $p_i>p_{i+1}$，这时候我们就会发现：这不是一样吗？没错，答案就是 $\frac{(2n)!}{2}$。

B. Diameter of Graph

$Problem$

每次给定 $n,m,k$ 问能不能构造一个 $n$ 个点，$m$ 条边的简单无向图使得图的直径小于 $k-1$。

一张图的直径定义为最短路最长的两个点的最短路长度。

$t\le 10^5,n,m,k\le 10^9$

$Solution$

始终没有明白为什么要“小于 $k-1$”，直接 k-=2 后变成 $\le k$。

考虑这道题可以转化为构造一个 $n$ 个点，$m$ 条边的直径尽可能小的图。

首先判断能否连通，即 $m<n-1$，然后判断是否必须有重边，即 $m>\frac{n(n-1)}{2}$，如果出现这两种情况则为不合法，直接排除。而且，如果 $k<1$，也直接排除，因为不可能存在两个点的距离 $<1$。

然后考虑能否构造出直径为 $1$ 的图。我们发现只有完全图的直径为 $1$，因为任意两个点都可以直径过 $1$ 条边到达。所以，如果 $k=1$，只有完全图才成立，否则不成立。接着在考虑能否构造出直径为 $2$ 的图。我们会发现只要图连通，就一定能构造出来直径为 $2$ 的图，因为菊花图的直径为 $2$，而在菊花图上加边不会让直径变大，所以只要 $k>1$ 就一定能构造出来。

C. Portal

$Problem$

给定一张 $n\times m$ 的矩阵，每个格子有空和黑曜石两种状态，你可以花费一步操作将空格子变成黑曜石或将黑曜石变成空格子。一个子矩阵可以形成传送门需要具备以下条件：

1. 高度 $\ge 5$，宽度 $\ge 4$。注意，传送门不能横过来看，宽就是宽，高就是高。
2. 中间部分必须全是空格子。
3. 四周边框必须全是黑曜石。
4. 四角不限。

问至少需要几次操作才能搭建一个传送门。

$\sum n\le 400,\sum m\le 400$

$Solution$

这道题我从9月30号读题一直到10月8号才做出来，历尽了千辛万苦。

记输入的矩阵为 $a$，用 $0$ 表示空格，$1$ 表示黑曜石。

首先预处理出每一行的前缀和，以便我们 $O(1)$ 查询一段横向区间里有多少块黑曜石，我们用 $s[i][j]$ 表示。

然后，枚举合法的左右边界（$r-l\ge 3$），我们记 $len=r-l-1$ 表示中间部分的宽度，对于每一个左右边界，记 $t[i]$ 表示前 $i$ 行全变成 $100...001$ 的格式需要花费的步数，本质上是竖向的前缀和：$t[i]=t[i-1]+(s[i][r-1]-s[i][l])+(2-a[i][l]-a[i][r])$。然后我们考虑如何 $O(1)$ 计算搭建一段以 $u$ 为上边界，$d$ 为下边界的传送门的步数：首先让中间和左右边框合法（$t[d-1]-t[u]$），再让上边框合法（$len-(s[u][r-1]-s[u][l])$），同理再让下边框合法（$len-(s[d][r-1]-s[u][l])$）。加起来，则为：

$t[d-1]-t[u]+(len-(s[d][r-1]-s[d][l]))+(len-(s[u][r-1]-s[u][l]))$

将与 $u,d$ 有关的项分开，方便处理：

$2len+(t[d-1]-s[d][r-1]+s[d][l])-(t[u]+s[u][r-1]-s[u][l])$

我们记 $f[i]=t[i-1]-s[i][r-1]+s[i][l],g[i]=t[i]+s[i][r-1]-s[i][l]$，则上式可简化为 $2len+f[d]-g[u]$。

现在考虑从上到下扫下边界，对于每一个下边界，我们要使步数尽可能小，即让 $2len+f[d]-g[u]$ 尽可能小，就要让 $g[u]$ 尽可能大，于是我们从上到下扫的时候，记录以下当前扫过的 $g[u]$ 的最大值 $maxn[i]=\max(maxn[i-1],g[i])$，那么对于每一个下边界 $d$，最小步数就为 $2len+f[d]-maxn[d-4]$，整个算法的时间复杂度就可以做到 $O(m^2n)$。